臺灣博碩士論文加值系統

Low-density parity check (LDPC) codes have been shown that it is a strong competitor of Turbo codes. LDPC codes offer excellent coding gain and provide elegant low computation complexity when comparing with Turbo codes. The complex routing nature of LDPC decoder and low hardware utilization efficiency are the major implementation challenges.
In this thesis we design an elitist scheduling algorithm called “Jump-Reset Scheduling Algorithm” to boost hardware utilization efficiency (HUE) of low-density parity check (LDPC) decoder. This algorithm supports a scalable pipeline decoding architecture. The architecture is a semi-parallel decoder with a scalability factor. It offers flexible tradeoff between hardware cost and throughput. A high HUE and scalable decoding architecture is implemented. This architecture is decoding algorithm independent from decoding algorithm. Sum-product algorithm and min-sum algorithm can be applied to this architecture. We use a modified min-sum algorithm as decoding algorithm in this decoder. This algorithm only contains additions and comparisons. There are no large LUTs for non-linear function in bit-to-check functional units. The modified min-sum algorithm can improve BER performance extremely close to sum-product algorithm. Word length effect on BER performance is analyzed. This thesis presents a scalable pipelined architecture with single size of memory and extremely high hardware utilization efficiency. This architecture can offer double throughput of traditional architecture without increasing memory requirement.

1. CHAPTER 1 — INTRODUCTION 1
1.1. COMMUNICATION SYSTEM 1
1.2. HISTORY AND INDUSTRY STANDARD 2
1.3. CODE AND HARDWARE CO-DESIGN 2
1.4. SCALABLE ARCHITECTURE 3
1.5. HUE 3
1.6. ORGANIZATION OF THESIS 4
2. CHAPTER 2 — DECODING ALGORITHM AND PERFORMANCE 5
2.1. RELATED WORK 5
2.2. TANNER GRAPH AND PARITY CHECK MATRIX 6
2.3. ITERATIVE DECODING & MESSAGE PASSING ALGORITHM 8
2.3.1. Sum-Product Algorithm 8
2.3.2. Min-Sum Algorithm 9
2.3.3. Scaling Min-sum algorithm 10
2.4. LOGARITHM DOMAIN ALGORITHM 11
2.5. CODE LENGTH, CODE RATE AND ITERATION VERSUS BER PERFORMANCE 13
2.5.1. Code Length 13
2.5.2. Code Rate 13
2.5.3. Decoding Iterations 14
2.6. FINITE WORD LENGTH 16
2.6.1. Quantization 16
2.6.2. Non-linear Quantization 16
2.6.3. SPA Finite Word Length Simulation 17
2.6.4. Log-domain SPA Finite Word Length Simulation 18
2.6.5. Scaling MSA Finite Word Length Simulation 19
2.7. HARDWARE AWARE QC-LDPC CODE DESIGN 19
2.7.1. QC-LDPC Codes and Parity Check Matrix 19
3. CHAPTER 3 — SCHEDULING ALGORITHM 21
3.1. PROCESSING UNIT 21
3.2. TRADITIONAL DECODING SEQUENCE 21
3.3. CONSTRAINT FOR SCHEDULING ALGORITHM 21
3.4. MESSAGE STORAGE 22
3.5. JUMP-RESET SCHEDULING ALGORITHM 23
3.5.1. Core Algorithm 23
3.5.2. Algorithm Principle 25
3.5.3. Algorithm Advantages 26
3.5.3.1. High HUE 26
3.5.3.2. Thread Set and Scalability 26
3.5.3.3. Simple Addressing 26
3.5.3.4. Memory and Computation Efficient 27
3.6. ADAPTIVE SYNDROME TEST 27
4. CHAPTER 4 — ARCHITECTURE DESIGN 28
4.1. DECODING ARCHITECTURE 28
4.1.1. FSM for Scheduling Algorithm 28
4.1.2. Functional Units 29
4.1.2.1. Check Functional Unit 29
4.1.2.2. Check Functional Unit Optimization 30
4.1.2.3. Bit Functional Unit 31
4.1.2.4. Bit Functional Unit Optimization 32
4.2. EFFICIENT ARCHITECTURE 33
4.3. MULTITHREAD ARCHITECTURE 34
5. CHAPTER 5 — EXPERIMENTAL RESULT 35
5.1. RESULT 35
5.2. CONCLUSION AND FUTURE WORK 35
6. APPENDIX 36
6.1. DESIGN HIERARCHY AND GENERICS 36
6.1.1. Simulation Waveform of Control Unit for Jump-Reset Algorithm 37
6.2. ITERATION ANALYSIS 43
6.2.1. Sun-Product Algorithm 43
6.2.2. Min-Sum Algorithm 43
6.2.3. Scaling Min-Sum Algorithm 44
6.2.4. Average Iterations 44
6.2.5. Iteration Statistics 45
7. REFERENCE 46

[1]David J.C MacKay, ”Near Shannon Limit Performance of Low Density Parity Check Codes,” Electronics Letters, vol. 33, pp. 457-458, 13 March 1997
[2]Blanksby, A.J.; Howland, C.J “A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder”, IEEE Journal, Solid-State Circuits, vol. 37, pp.404-412, March 2002
[3]Howland, C.; Blanksby, A “Parallel decoding architectures for low density parity check codes”, ISCAS, Circuits and Systems, vol. 4, pp.742-745, May 2001
[4]Mauro Cocco, John Dielissen, Marc Heijligers, Andries Hekstra, and Jos Huisken, “A Scalable Architecture for LDPC Decoding,”Design, Automation and Test in Europe Conference and Exhibition, vol.3, pp.88-93, Feb 2004
[5]Xiao-Yu Hu, Evangelos Eleftheriou, Dieter-Michael Arnold, and Aholakia, “Efficient Implementation of the Sum-Product Algorithm for Decoding LDPC Codes”, 2001
[6]Engling Yeo, Boriveje Nikolic, and Venkat Anatharam, “Architectures and Implementations of Low-Density Parity Check Decoding Algorithms”, 2002
[7]Jinghu Chen, Marc P.C Fossorier, “Near Optimum Universal Belief Propagation Base Decoding of Low-Density Parity check Codes”, 2002
[8]Decoder Architecture for Array-Code-Based LDPC Codes
[9]Tong Zhang, and Keshab K. Parhi, “Joint (3, k)-Regular LDPC Code and Decoder/Encoder Design”, 2004
[10]Marjan Karkooti and Joseph R. Cavallaro, “Semi-Parallel Reconfigurable Architectures for Real-Time LDPC Decoding,” ITCC Proceeding of International Conference, Information Technology: Coding and Computing, vol.1, pp.579-585, April 2004
[11]R. G. Gallager, “Low-Density Parity-Check Codes”, IEEE Trans., Information Theory, vol. 8, pp.21-28, Jan. 1962
[12]Mohammad M. Mansour and Naresh R. Shanbhag, “Memory-Efficient Turbo Decoder Architecture for LDPC Codes”, 2002
[13]Mauro Cocco, John Dielissen, Marc Heijligers, Andries Hekstra, and Jos Huisken, “A Scalable Architecture for LDPC Decoding,”Design, Automation and Test in Europe Conference and Exhibition, vol.3, pp.88-93, Feb 2004
[14]Niclas Wiberg, “Codes and Decoding on General Graphs”, PhD thesis, Linkoping University, 1996
[15]Yanni Chen and Keshab K. Parhi, “Overlapped Message Passing for Quasi-Cyclic Low-Density Parity Check Codes”, IEEE Trans., Circuits and Systems, vol. 51, pp.1106-1113, June 2004
[16]Sang-Min Kim and Parhi, K.K. “Overlapped decoding for a class of quasi-cyclic LDPC codes”, IEEE Workshop, Signal Processing Systems, pp.113-117,13-15 Oct 2004
[17]Jun Heo “Analysis of scaling soft information on low density parity check code”, Electronics Letters, vol 39, pp219-221, Jan 2003
[18]Jun Heo and Keith M. Chugg, “Optimization of Scaling Soft Information in Iterative Decoding Via Density Evolution Methods”, IEEE Trans., Communications, vol. 53, pp957-961, June 2005