臺灣博碩士論文加值系統

本論文提出新的低成本高效能低密度奇偶校驗碼解碼器的架構設計，本新架構是在Log sum-product algorithm (Log-SPA)解碼演算法之下採用邏輯或閘運算(OR Operation)取代傳統二進位加法器。同時提出本論文pseudo-carry電路，在OR Operation架構，用以大幅改善本論文之OR Operation架構位元錯誤率(BER)效能。此外，我們還在新的OR Operation架構中，採用全二補數數系的訊息傳遞的技術，來簡化硬體複雜度，而此更進一步的降低新解碼電路的硬體成本。
本論文主要有兩款新型低密度奇偶校驗碼解碼器架構，與傳統電路相比，在矩陣大小為504×1008時，並採用TSMC 0.18μm標準細胞元硬體合成，結果顯示可減少硬體成本可以達到32%與26%。在效能比較上和傳統Log-SPA解碼器架構上，約只相差0.1dB ~ 0.3dB BER效能。若與Sign-Min架構比較，則改善0.3dB ~ 0.1dB BER效能。將我們所提出的OR Operation以及OR Pseudo-carry Operation的低密度奇偶校驗碼解碼器，搭配AWGN Generator、串列並出暫存器、並列串出暫存器以及控制單元的電路設計，在矩陣大小為102×204 使用FPGA驗證解碼成功。

A low hardware cost LDPC decoder, using logical OR operation on the check-nodes for Log sum-product algorithm (Log-SPA) decoding algorithm, is presented in this thesis. A pseudo-carry circuit is proposed for OR operation architecture in this thesis, to improve the Bit Error Rate (BER) performance. In addition, we had proposed a simplified messaging passing technique in our OR operation architecture, using two’s complement values, that reduced hardware compleity and decoding efforts.
We design two new architectures in this thesis to compare with the traditional LDPC decoder by using the matrix size 504×1008 and targeting with TSMC 0.18μm standard cell library, the synthesized results show that new proposed architectures achieve up to 32% and 26% total hardware reduction, and 0.1dB ~ 0.3dB BER lose, when comparing with the traditional Log-SPA decoder architecture, There is 0.1dB ~ 0.3dB BER improvement while comparing with the Sign-Min architecture. Our new LDPC decoder has verified by FPGA, consisting with AWGN generator, SIPO, PISO, control unit, in a 102×204 matrix. The measurement results show that our new LDPC architecture can decode successfully.

摘要
Abstract
致謝
目錄
表目錄
圖目錄
第一章 緒論
1.1 研究動機
1.2 研究方法
1.3 相關研究探討
1.4 預期成果
1.5 本論文各章節之安排
第二章 低密度奇偶校驗碼介紹
2.1 低密度奇偶校驗碼的基本概念
2.1.1 低密度奇偶校驗碼的結構
2.1.2 Tanner Graph
2.1.3 Cycle與Girth
2.1.4 Message Passing 演算法概念
2.2 低密度奇偶校驗碼解碼演算法
2.2.1 Sum-Product 演算法原理
2.2.2 傳統改良之低密度奇偶校驗碼解碼演算法演進
2.3 傳統改良型演算法之效能分析
第三章 Look-Up Table (LUT)分析及簡化補數運算之低密度奇偶校驗碼解碼器架構
3.1 Look-Up Table (LUT)分析
3.2 簡化補數運算之低密度奇偶校驗碼解碼器架構
3.2.1 傳統低密度奇偶校驗碼解碼器架構問題
3.2.2 新型全二補數數系運算之低密度奇偶校驗碼解碼器架構
3.2.3 效能分析比較
第四章 新型以邏輯或閘取代加法運算之硬體架構
4.1 傳統架構之硬體複雜度問題
4.2 新型簡易邏輯或閘運算架構之低密度奇偶校驗碼解碼器
4.2.1 Check Node之OR Operation架構
4.2.2 Check Node之OR Pseudo-carry Operation架構
4.3 新架構與傳統架構之效能分析比較
4.3.1 BER效能分析比較
4.3.2 硬體效能分析比較
第五章 硬體實現
5.1 AWGN Generator
5.2 串列並出(Serial Input Parallel Output)暫存器
5.3 並列串出(Parallel Input Serial Output)暫存器
5.4 晶片測試架構
5.5 Whole Chip使用FPGA驗證
5.6 ASIC實現
結論
參考文獻
附錄
簡歷

[1] R. G. Gallager, "Low-density parity-check code", IRE Trans. Inform.Theory, vol.IT-8, pp. 21-28, Jan. 1962.
[2] D. J. C. MacKay, "Good error-correcting codes based on very sparse matrices", IEEE Trans. Inform. Theory, vol. 45, pp. 399-43 1, Mar. 1999.
[3] S. -Y. Chung, G. D. Forney, Jr., T, J. Richardson, and R. Urbanke, "On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit", IEEE Commun. Lett, vol. 5, pp. 58-60, Feb. 2001.
[4] X. -Y Hu, E. Eleftheriou, D. -M. Arnold, and A. Dholakia, "Efficient implementations of the sum-product algorithm for decoding LDPC codes", Proc. IEEE Globecom, pp. 1036-1036E, Nov. 2001.
[5] S. Papaharalabos, P. Sweeney, B. G. Evans, G. Albertazzi, A. Vanelli-Coralli and G. E. Corazza, "Performance evaluation of a modified sum-product decoding algorithm for LDPC codes", IEEE International Symposium on Wireless Communication Systems, pp. 800 – 804, Sept. 2005.
[6] A. J. Blanksby and C. J. Howland, "A 690-mW 1 Gb/s 1024-b rate-1/2 low-density parity-check code decoder", IEEE J. Solid-State Circuits, vol. 37, no. 3, pp. 404–412, Mar. 2002.
[7] C. C. Lin, K. L. Lin, H. C. Chang and C. Y. Lee, "A 3.33Gb/s (1200,720) low-density parity check code decoder", Proc.of the 31st European IEEE Solid-State Circuits Conference, pp. 211 – 214, Sept. 2005.
[8] Y. Zhang, Z. Wang and K. K. Parhi, "Efficient high-speed quasi-cyclic LDPC decoder architecture", IEEE ACSSC, Vol.1, pp. 540-544, Nov. 2004.
[9] A. Darabiha, A. C. Carusone and F. R. Kschischang, "Multi-Gbit/sec low density parity check decoders with reduced interconnect complexity", IEEE International Symposium on Circuits and Systems, Vol. 5, pp. 5194-5197, May 2005.
[10] R. M. Tanner, "A recursive apptoach to low complexity codes," IEEE Trans. Inform. Theory, vol. IT-42, pp. 533-547,1981.
[11] F. R. Kschischang and B. J. Frey, “Iterative decoding of compound codes by probability propagation in graphical models,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 219-230, February 1998.
[12] W. E. Ryan, An introduction to LDPC codes, in CRC Handbook for coding and signal processing for recording systems (B. Vasic ed.), CRC Press, 2004.
[13] D. J. C. Mackay, Online database of low-density parity-check codes, available at http://www.inference.phy.cam.ac.uk/mackay/CodesFiles.html.
[14] S. Tong, P. Wang, D. Wang and X. Wang, " Box-minus operation and application in sum-product algorithm", IEE Electronics Letters, vol. 41, pp. 197-198, Feb. 2005.
[15] M. Fossorier, et al. "Reduced complexity iterative decoding of low-density parity-check codes based on belief propagation," IEEE Trans. Comm., pp. 673-680, May 1999.
[16] E. Eleftheriou, T. Mittelholzer and A. Dholakia, "Reduced-complexity decoding algorithm for low-density parity-check codes," IEE Electronics Letters, vol. 37, pp. 102-104, Jan. 2001.
[17] J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier and X.-Y. Hu, " Reduced-complexity decoding of LDPC codes," IEEE Trans. Comm., vol. 53, pp. 1288-1299, Aug. 2005.
[18] IEEE 802.16e. Air interface for fixed and mobile broadband wireless access systems. IEEE P802.16e/D12 Draft, Oct 2005.
[19] A. Gazel, E. Boutillon, J.L. Danger, G. Gulak, “Design and performance analysis of a high speed AWGN communication channel emulator”, IEEE PACRIM conference, Victoria, B.C., Canada, Aug. 2001.
[20] J.L. Danger et al., “Efficient FPGA implementation of Gaussian noise generator for communication channel emulation”, Proc. 7th IEEE Int. Conf. on Elect., Circ. and Syst. (ICECS 2K), 2000.
[21] D. Lee, W. Luk, J. Villasenor, and P. Cheung, “A Gaussian noise generator for hardware-based simulations,” IEEE Trans. Comput., vol. 53, no. 12, pp. 1523–1534, Dec. 2004.
[22] Y. Fan and Z. Zilic, "A novel scheme of implementing high speed AWGN communication channel emulators in FPGAs", IEEE Proc. of the 2004 International Symposium on Circuits and Systems, 2004. ISCAS ''04.
[23] Donald E. Knuth, "The art of computer programming", ADDISON-WESLEY, 1998.
[24] S. Boubezari, E. Cerny, B. Kaminska, B. Nadeau-Dostie, ”Testability analysis and test-point insertion in RTL VHDL specifications for scan-based BIST ” IEEE Transactions on CAD of Integrated Circuits and Systems, Volume: 18, Sept. 1999.
[25] J. Rajski, N. Tamarapalli, J. Tyszer, ” Automated synthesis of phase shifters for built-in selftest applications”, IEEE Transactions on CAD of Integrated Circuits and Systems, Volume: 19, pp. 1175 -1188, Oct. 2000.