臺灣博碩士論文加值系統

低密度奇偶校驗碼(Low-Density Parity-Check Code)最早是由R.G. Gallager博士在1962於其博士論文發表，此種編碼方式有著非常優越的性能，且其更正能力更遠超其他的編碼技術，使得其解碼效能十分的逼近向農極限 (Shannon limit)。本論文分別針對LDPC的解碼演算法以及硬體的架構上做討論與改進。
在解碼演算法方面，有鑑於在低量化位元數的fixed-point設計中，MP (Message Passing) algorithm family 的效能很差。本篇論文提出了一個新的演算法稱為Fixed-window Ranging and Voting (FRV)演算法，可以在MP演算法解碼過程之後，進一步的找出錯誤的位元並加以更正，而不需要做病徵(Syndrome)測試，使得效能得以增進約0.5dB並且延後了error floor 的出現，且只需要增加非常少量的硬體。和直接提高量化精確度的方法比較，FRV algorithm是更有效率的選擇。
另外，本論文又探討了BF (Bit-flipping) 演算法的效能與潛力，並且提出了一個全新的演算法，稱為Low-Correlation Multi-Bit Flipping (LCMBF) 演算法。此方法在相同的iteration number之下可以大幅的提升BF family演算法的效能達1~2dB以上，而且由於BF family 演算法並非訊息傳遞類型的演算法，並不需要儲存解碼過程中的訊息，也就是可以大大減少記憶體的需求，因此在考慮硬體實現的因素，LCMBF演算法有很大的可能性取代MP 演算法成為LDPC decoder的新主流。
在硬體架構上，由於現今的CNU (Check Node Unit)架構只針對特定的輸入數目並且是以手工的方式做最佳化，而並無一個有系統化的架構設計。因此本論文提出了三個演算法，並可依據演算法的結果建構出相應的CNU架構。這些演算法適用於不同的設計要求，但皆有著非常短的運算時間與非常低的複雜度。除此之外，每個演算法皆是適用於任何輸入數目的CNU，並且可以輕易的程式化。
最後，本論文針對802.16e的標準，利用更有效率的記憶體架構，設計了一個新的partial-parallel、high-throughput且 area-efficient的LDPC decoders，並且採用本論文提出的系統化CNU架構。在802.16e的標準之下，採用(576, 288)的LDPC code 可以達到1.45 Gbps 的data throughput。採用UMC 0.18 製程，其chip gate count為884k，功率消耗為565 mW。本論文也實作了FRV演算法的硬體設計及其比較，結果顯示使用FRV演算法的設計只會微量的增加約3k gate count及12mW的功率消耗，即可獲得超過0.5dB的效能增益。相較於直接提高量化精確度的方法，採用FRV演算法 可以節省約127k chip gate count和 77mW的功率消耗。

Low-Density parity check (LDPC) code was first introduced by Gallager, which can achieve performance close to Shannon bound. This thesis focuses on the improvement of decoding algorithms and efficient designs of decoder hardware architectures.
In improving decoding algorithms, in order to the better performances, LDPC decoding processes often use the family of Message Passing (MP) algorithms. However, this thesis finds out that performances of MP algorithms would degrade seriously in fixed-point designs with short word lengths. To alleviate this problem, this thesis proposes a novel algorithm, called Fixed-window Ranging and Voting (FRV) Algorithm which can further identify error bits after each decoding iteration process in fixed-point design when using MP algorithms. Based on the algorithm, fixed-point decoding performances are much closer to floating-point results than conventional MP algorithms, only at the cost of very little hardware area. In [7:5] fixed-point quantized configuration, this algorithm can improve the performance by 0.5dB and delay the onset point of the error floor occurrence over the conventional algorithms.
Furthermore, in order to totally avoid the fixed-point implementation problem, this thesis rediscovers the potential of Bit-flipping (BF) algorithm family and presents a novel multi-bit flipping algorithm, called Low-Correlation Multi-Bit Flipping (LCMBF) algorithm. This algorithm can improve performance of BF algorithms by 1 to 2 dB. Since BF algorithms are not based on message passing, it does not need to storage all messages in the iteration processes. It means LCMBF algorithm has very high potential to replace MP algorithm family as the new main decoding method particularly in hardware realization.
In hardware implementation, since existing CNU design techniques only do customized optimization case by case for a specific CNU’s comparator architecture with a prescribed input number, but do not propose a systematic and generalized design approach for arbitrary input numbers. For cases with long code lengths, it will be impractical to optimize the designs by hand. Thus, this thesis presents three CNU comparison algorithms to solve this problem for the ease of the hardware design. These algorithms are based on different design concepts and all have very short delay time and very low complexity. Besides, each proposed algorithm suits for CNU with arbitrary input number which is easy to program.
Finally, this thesis presents a LDPC decoder design for 802.16e standard which is a more efficient LDPC decoder architecture (based on a proposed message reordering scheme) than existing designs. The decoder, which adopts the mentioned proposed CNU comparison algorithm, is partial parallel, high throughput and area efficient. The design for (576,288) LDPC codes can achieve a throughput of 1.45Gbps. It adopts UMC 0.18 process; its gate count is 884k and power consumption is 556mW. This thesis also realizes the FRV algorithm and does some comparison. By applying FRV algorithm one can gain 1dB performance improvement over the conventional algorithms, at the cost of only 3k gate count and power consumption of 12mW. Compared with the design of directly increasing quantized wordlength, the design due to FRV algorithm can reduce about 127k gates and power consumption of 72mW.

中文摘要 Ⅰ
ABSTRACT Ⅲ
ACKNOWLEDGEMENT VI
CONTENTS VII
LIST OF TABLES X
LIST OF FIGURES XI

Chapter 1 Introduction 1
1.1 Background of LDPC Codes 1
1.2 Thesis Organization 3

Chapter 2 Low-Density Parity-Check Code 4
2.1 Fundamental Concept of LDPC Code 4
2.2 Constructions of LDPC Codes 7
2.2.1 Random Code Construction 7
2.2.1.1 Gallager Codes 7
2.2.1.2 MacKay Codes 8
2.2.2 Deterministic Code Construction 9
2.2.2.1 Block LDPC code 9
2.2.2.2 Quasi-Cyclic Code 10
2.3 Encoding of LDPC Codes 11
2.3.1 Conventional Method 12
2.3.2 Quasi-Cyclic Code 13
2.3.3 Richardson’s Method 14

Chapter 3 Decoding Algorithms 17
3.1 Message Passing Algorithm 17
3.1.1 Decoding Procedure in Tanner Graph Form 18
3.1.1.1 Probability Form 19
3.1.1.2 LLR Form 22
3.1.1.3 Decoding Procedure in Matrix Form 25
3.1.1.4 Iterative Decoding Procedure 26
3.1.2 Sum-Product Algorithm 29
3.1.3 Min-Sum Algorithm 29
3.1.4 Modified Normalization Min-Sum Algorithm 29
3.2 Bit Flipping Algorithm 34
3.2.1 Standard Bit-Flipping Algorithm 35
3.2.2 Weighted Bit-Flipping Algorithm 36
3.2.3 Modified Weighted Bit-Flipping Algorithm 37
3.2.4 Improved Modified Weighted Bit-Flipping Algorithm 38
3.2.5 Liu-Pados Weighted Bit-Flipping Algorithm 39
3.2.6 Weighted-Sum Bit-Flipping Algorithm 40
3.2.7 Reliability Ratio Weighted Bit-Flipping Algorithm 41
3.3 Comparison of MP and BF Algorithm 43
3.3.1 Floating-point Simulation 47
3.3.2 Fixed-point Simulation 48
3.4 Summary 53

Chapter 4 The Proposed FRV Algorithm for MPA Family 54
4.1 Motivation and Goal 54
4.2 Concept of the Proposed FRV Algorithm 55
4.3 Detailed flows of the Proposed FRV Algorithm 56
4.4 Comparison and Simulation Results 58
4.5 Operation Requirement Analysis 68
4.5.1 Operation Requirement of R part 68
4.5.2 Operation Requirement of V part 69
4.5.3 Operation Requirement of F part 69
4.6 Summary 70

Chapter 5 The Proposed LCMBF Algorithm for BFA Family 71
5.1 Motivation and Goal 71
5.2 The Bottleneck of Multi Bit-Flipping Algorithm 72
5.3 Concept of the Proposed LCMBF Algorithm 75
5.4 Detailed Flows of the Proposed LCMBF Algorithm 76
5.5 Formation of Directly Correlative Set 78
5.6 Comparison and Simulation Results 79
5.6.1 Floating-point Simulations 80
5.7 Proposed Low-Correlative Comparison Algorithm 86
5.8 Summary 88

Chapter 6 The Proposed CNU Comparison Algorithms for MPA Family 89
6.1 Motivation and Goal 89
6.2 BNU and CNU Architecture 90
6.2.1 BNU Architecture 90
6.2.2 CNU Architecture 91
6.2.2.1 Conventional CNU Architecture 92
6.2.2.2 Exclusive CNU Architecture 93
6.3 The Proposed Comparison Algorithms for CNU 94
6.3.1 Shortest Delay Time consideration 94
6.3.1.1 The Proposed Cyclic Comparison Algorithm 95
6.3.1.2 The Proposed VHC Comparison algorithm 97
6.3.2 Time-Area Trade off consideration 104
6.3.2.1 The Proposed Set Comparison Algorithm 104
6.4 Performance of the Proposed Designs 106
6.5 Summary 109

Chapter 7 The Proposed High Speed Decoder Architecture for 802.16e Standard with Modified MSA 110
7.1 Motivation and Goal 110
7.2 Decoder Architecture 111
7.2.1 Input Buffer 114
7.2.2 MMU 115
7.2.3 CNU 117
7.2.4 BNU 118
7.3 Decoder Architecture with the Proposed FRV Algorithm 119
7.3.1 FRV Unit 120
7.4 Implementation 121
7.5 Summary 123

Chapter 8 Conclusion and Future Work 125
8.1 Conclusions 125
8.2 Future Work 127

Appendix A: LDPC Codes Specification in IEEE 802.16e OFDMA 129

Appendix B: Pseudo Codes of Proposed Systematic Optimized Comparison Algorithms 132

References 137

Autobiography 140

[1] R. G. Gallager, Low-density parity-check codes, Cambridge, MA: MIT Press, 1963.
[2] D. J. C. Mackay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., Vol. 32, pp. 1645-1646, Aug. 1996.
[3] D. J. C. Mackay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, Vol. 45, pp. 399-431, Mar. 1999.
[4] X. Y. Hu, E. Eleftheriou, D. M. Arnold, and A. Dholakia, “Efficient implementation of the sum-product algorithm for decoding LDPC codes,” IEEE GLOBECOM’01, Vol. 02, pp. 1036-1036E, Nov. 2001.
[5] J. Chen and M. P.C. Fossorier, “Near Optimum Universal Belief Propagation Based Decoding of Low-Density Parity Check Codes,” IEEE Trans. on Commun., Vol. 50, pp. 583-587, NO.3 Mar. 2002.
[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, 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,” IEEE Proceedings of ESSCIRC, Grenoble, Feb, 2005.
[8] M. Karkooti and J. R. Cavallaro, “Semi-Parallel Reconfigurable Architectures for Real-Time LDPC Decoding,” IEEE Proceedings of ITCC, Vol.1, pp.579-585, April 2004.
[9] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann, “Practical loss-resilient codes,” IEEE Trans. Inform. Theory, Vol. 47, pp. 569-584, Feb. 2001.
[10] R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory, Vol. 27, pp. 533-547, Sep. 1981.
[11] M. G. Luby , M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman, “Improved Low-Density Parity-Check Codes Using Irregular Graphs,” IEEE Trans. on Inform. Theory, Vol. 47, pp. 585–598, Feb. 2001..
[12] H. Zhong and T. Zhang, ”Block-LDPC: A Practical LDPC Coding System Design Approach,” IEEE Trans. on circuits and systems, Vol. 52, pp. 766-775, April. 2005.
[13] S. J. Johnson and S. R. Weller, “A family of irregular LDPC codes with low encoding complexity,” IEEE Comm. Letter., Vol. 7, pp. 79-81, Feb. 2003.
[14] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inform. Theory, Vol. 47, pp. 498-519, Feb. 2001.
[15] H. Futaki and T. Ohtuski, “Low-density parity-check (LDPC) coded OFDM systems,” IEEE VTS, Vol. 1, pp. 82-86, Fall. 2001.
[16] R. G. Gallager, “Low density parity check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21–28, Jan. 1962.
[17] Y. Kou, S. Lin, and, M.P.C. Fossorier, “Low-Density parity check codes based on finite geometries: a rediscovery and more,”IEEE Trans. Inform. Theory, pp. 2711-2736, 2001.
[18] J. Zhang, M.P.C. Fossorier,“A Modified Weighted Bit-Flipping Decoding of Low-Density Parity-Check Codes,”IEEE Commun. Lett., vol. 8, pp. 165-167,March 2004.
[19] M. Jiang, C. Zhao, Z.Shi, and Y. Chen,“An Improvement on the Modified Weighted Bit Flipping Decoding algorithm for LDPC Codes,”IEEE Commum. , Vol. 9, No.9, pp.814-816, Sept. 2005.
[20] Z. Liu and D.A. Pados, “Low complexity decoding of finite geometry LDPC codes,”Communications, pp. 2713-2717, April 2003.
[21] M. Shan, C.M. Zhao and M. Jiang, ”Improved weighted bit-flipping algorithm for decoding LDPC codes,”IEE Pro.- Commun., Vol. 152, No. 6, pp. 919-922, December 2005.
[22] F. Guo, and L. Hanzo, “Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes”, Electron. Lett., pp. 1356-1358, 2004.
[23] I.C. Park and S.H. Kang, “Scheduling algorithm for partially parallel architecture of LDPC decoder by matrix permutation,” in proc. IEEE ISCAS, pp. 5778-5781, May 2005.
[24] C.C. Lin, C.Y. Lee and H.C. Chang, Channel Decoder Design and Implementation, Ph.D. diss., NCTU, 2006.