顧孟愷臺灣大學：資訊工程學研究所簡義興Chien, Yi-hsingYi-hsingChien2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/53927Low-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 461644889 bytesapplication/pdfen-US錯誤更正碼低密度奇偶校驗編碼遞迴解碼編碼增益Low-density Parity CheckLDPCIterative DecodingChannel CodingSum-product AlgorithmSPAMin-sum algorithmMSAScaling min-sum algorithmSMSACoding Gainthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53927/1/ntu-94-R92922049-1.pdf