臺灣博碩士論文加值系統

在本論文中，我們採取以對數領域和積演算法(Log-Domain Sum-Product
Algorithm ,Log-SPA)作為基準，改良低密度奇偶校驗碼中檢查節點(Check Node)部
份。經研究發現，傳統檢查節點硬體實現，最常用到的是查表電路。而本論文以
降低硬體成本為主要考量，再從檢查節點查表動作中發現改良地方，進而提出新
型獨立行運算技巧。這創新的電路是利用優先編碼器觀念，建立二進制權位查表
電路，將表格查出後的值，每個位元單獨搭配上精簡加法器做獨立行加法運算，
最後再經由還原查表電路進行還原動作。整個低密度奇偶校驗碼解碼器使用全平行架構，硬體實現結果證明在IEEE 802.16e 標準下矩陣大小為(1248,624)，碼率為1/2，使用TSMC 0.18μm 製程下，與傳統解碼器面積比較下，可降低28%，而效能與對數領域和積演算法切割出來查表電路3-bit 轉5-bit 表格相差不到0.1dB，且晶片操作頻率可高達111MHz。如採
用UMC 90nm 製程，同樣實現在IEEE 802.16e 標準奇偶校驗矩陣大小為
(1248,624)，解碼器架構面積大約可以省下22%左右。本論文除了解碼器硬體外，
在測試晶片裡，還設計了有可自我測試用的＂附加白高斯雜訊＂通道產生器，及
相關的模式控制單元電路。在論文最後，我們使用TSMC 0.18μm 技術之細胞元電
路實現一顆晶片，實際佐證本研究所提的新解碼器架構具低成本及高效能特性。

In this thesis, we adopt Log-Domain Sum-Product Algorithm (Log-SPA) to implement a modified low-density parity check code decoder in its check node part. From the prior art studies, we found that the look-up table is the most commonly use circuit being implemented in a traditional check-node hardware, and the main goal of this thesis is to propose a low hardware cost LDPC decoder, therefore we start from the traditional look-up table. Then, we propose a new independent column-wise operation skill to reduce the adder operations. It uses simply the concept of priority encoder which establishes a new binary weighting look-up table, so that a new simplified adder can be used for independent column-wise operation. The exact downing to valuable node value can be obtained by a recovery look-up table.
The proposed new decoder is realized in the fully parallel architecture under the IEEE 802.16e standard that the matrix size is (1248, 624) and the code rate is 1/2. When compare with the traditional LDPC decoder hardware, the total chip area reduces about 28%, and the operational speed can reach up to 111MHz with only 0.1dB BER difference under TSMC 0.18um cell-based technology. In the same condition, the proposed decoder can save about 22% hardware by using UMC 90nm cell-based technology. The implemented test chip equipped with real-time on-chip self-test circuits which have an Additional White Gaussian Noise generator, and associated mode control circuits. The implemented chip, in TSMC 0.18um cell-base technology, shows that our new LDPC decoder architecture has low-cost and high-performance characteristics.

中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章 序論 1
1.1 研究背景與動機 1
1.2 研究方法 3
1.3 錯誤更正碼概述 5
1.4 論文組織介紹 5
第二章 低密度奇偶校驗碼介紹 6
2.1 低密度奇偶校驗碼基本概念 6
2.1.1 線性區塊碼 6
2.1.2 低密度奇偶校驗碼結構 7
2.1.3 低密度奇偶校驗碼之編碼 8
2.1.4 Tanner 圖 11
2.1.5 Cycle 與 Girth 12
2.1.6 訊息傳遞演算法概念 13
2.2 低密度奇偶校驗碼解碼演算法 14
2.2.1 和積演算法原理 14
2.2.2 和積演算法(Sum-Product Algorithm) 17
2.2.3 對數領域和積演算法(Log-Domain Sum-Product Algorithm) 22
2.2.4 最小和演算法(Min-Sum Algorithm) 26
2.2.5 改良式最小和演算法(Modified Min-Sum Algorithm) 28
2.2.6 補償式最小和演算法(Offset Min-Sum Algorithm) 30
2.2.7 正規化最小和演算法(Normalized Min-Sum Algorithm) 31
2.3 各種低密度奇偶校驗碼解碼演算法分析與比較 33
第三章 新型獨立行運算技巧之低密度奇偶校驗碼解碼器架構 35
3.1 傳統對數領域和積演算法低密度奇偶校驗碼硬體架構 35
3.2 傳統查表電路介紹 38
3.3 新型獨立行運算技巧之低密度奇偶校驗碼解碼器架構 48
A 二進制權位查表電路 48
B 本論文所提之精簡加法器 50
C 還原查表電路 56
3.4 位元錯誤率效能分析比較 60
3.5 硬體效能分析比較 63
第四章 低密度奇偶校驗碼硬體實現 66
4.1 低密度奇偶校驗碼編碼器 67
4.2 含自我測試低密度奇偶校驗碼解碼器硬體實現 68
4.2.1 附加白高斯雜訊通道產生器 70
4.2.2 串列並出(Serial Input Parallel Output, SIPO)暫存器 73
4.2.3 並列串出(Parallel Input Serial Output, PISO)暫存器 73
4.2.4 晶片測試架構 74
4.3 整個晶片模擬與實現 75
4.4 晶片與其他電路綜合測試考量 80
第五章 結論 83
參考文獻 84

[1]T. J. Richardson and R. L. Urbanke, “The capacity of low-density paritycheck codes under message-passing decoding,” IEEE Trans. Inform Theory, vol.47, pp. 599-618, Feb. 2001.
[2]http://www.ieee802.org/16/tge
[3]http://grouper.ieee.org/groups/802/11
[4]R. G. Gallager, “Low-density parity-check code,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1962.
[5]D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp.399-431, Mar. 1999.
[6]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.
[7]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.
[8]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.
[9]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, Sep. 2005.
[10]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.
[11]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.
[12]J. Chen and M.P.C. Fossorier, "Density evolution for two improved BP-based decoding algorithms of LDPC codes," IEEE Commun. Lett., vol.4, no.2, pp. 208–210, 2002.
[13]Jinghu Chen, Dholakia, A., Eleftheriou, E., Fossorier, M.P.C., Xiao-Yu Hu, " Reduced-complexity Decoding of LDPC Codes," IEEE Trans. Commun., vol. 53, no. 8, pp. 1288-1299, Aug. 2005.
[14]Jinghu Chen and Marc Fossorier, Density evolution for BP-based decoding algorithms of LDPC codes and their quantized versions, Globecom2002, Taipei, Nov. 2002.
[15]Pandya ,N. and Honary,B., "Low-complexity decoding of LDPC codes," Electron. Lett.,43,pp. 990-991, 2007
[16]S. Papaharalabos and P.T. Mathiopoulos, "Simplified sum-product algorithm for decoding LDPC codes with optimal performance," Electron. Lett., vol. 45, pp. 116-117,2009
[17]Draft Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems (Revision of IEEE Std 802.16-2004 and consolidates material from IEEE Std 802.16e-2005, IEEE Std 802.16 -2004 / Cor1-2005, IEEE Std 802.16f-2005 and IEEE Std 802.16g-2007)
[18]R. M. Tanner, "A recursive apptoach to low complexity codes," IEEE Trans. Inform. Theory, vol. IT-42, pp. 533-547, Sep. 1981.
[19]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, Feb. 1998.
[20]M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. Commun., vol. 47, pp. 673-680, May 1999.
[21]Qi WANG, Kazunori SHIMIZU, Takeshi IKENAGA, and Satoshi GOTO, "Efficient Fully-Parallel LDPC Decoder Design with Improved Simplified Min-Sum Algorithms," Trans Electron IEICE, vol. 90, no. 10, pp. 1964-1971, Oct. 2007.
[22]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.
[23]Jean-Luc Danger, “Efficient FPGA implementation of Gaussian noise generator for communication channel emulation,” Proc. 7th IEEE Int. Conf. on Elect., Circuits & Systemes (ICECS 2K), Dec. 2000.
[24]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.
[25]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.
[26]http://www.idt.com