Low Density Parity Check Code Decoder Architecture Study and Design

文探討一種錯誤更正碼的技術，低密度同位元檢查碼(Low-Density Parity- Check Code, LDPC)，其中包含碼的組成、碼的編解碼、及其遞迴解碼演算法，進而引入硬體設計的概念，分別探討完全平行式解碼架構、序列解碼架構、部份平行式解碼架構。不同的方式應用於不同的實際情況中。有quasi-cyclic半循環特性的同位元檢查矩陣有 個子矩陣，每一個子矩陣為單位矩陣或是其circulant矩陣，以上通稱為circulant 矩陣，其特點為每一個列為上一列的右移。此種矩陣可以建構出一系列的(QC_LDPC) 碼，可藉由定義每一個子矩陣的第一列的第一個一的位置，可找出適合的低密度同位元檢查碼且具有好的解碼效能。種半循環低密度同位元檢查碼亦適合部份平行式的解碼器實作，此部份平行式解碼器具有很高的彈性。此外介紹解碼器中主要的運算功能單元，諸如位元點單元及檢查點單元。部份平行式的解碼器結合完全平行式及序列式低密度同位元檢查碼解碼器優點，提供非常好硬體的方案，諸如可避免完全式解碼器大量繞線的問題，及序列式速度慢且需要大面積的記憶體，因此部份平行式的同位元檢查碼解碼器已成為現今低密度同位元檢查碼解碼器設計主流。終探討及實作部份平行式的同位元檢查碼解碼器，此架構之解碼器之同位元檢查矩陣具有特殊規律的結構，其優點為方便編碼器實作於移位暫存器。而解碼器之負責運算功能單元間的訊息的傳遞控制邏輯，可藉由簡單的累加器來產生所需要的記憶體位址，大幅降低以完全平行式設計方式所需的大量繞線。This Thesis discusses an error correction technology, Low-Density Parity Check (LDPC) code, as well as its code constructions, encoding methods and decoding algorithms.artially parallel decoder design methodology provides appropriate trade-off between hardware complexity and decoding throughput. Partially parallel decoder also combines the advantages from both the LDPC fully parallel decoder and serial decoder. Many Quasi-Cyclic LDPC codes have been studied and developed. These kinds of QC_LDPC codes not only reduce the memory addressing complexity in a decoder design but also the encoding complexity. Other compatible QC_LDPC codes have also been proposed. In this Thesis, we choose a code construction method similar to [27] to implement a partially parallel decoder suitable for the family of (3, 6)-regular LDPC codes. array of circulant sub-matrices can be used to represent the parity check matrix Hqc of a QC_LDPC code. A family of structured QC_LDPC codes can be constructed by shifting the identity sub-matrix into different circulant sub-matrices. These kinds of QC_LDPC codes are suitable for partially parallel decoder. And its construction provides flexibility in hardware design.TABLE OF CONTENTSBSTRACT iIST OF FIGURES viiIST OF TABLES ixHAPTER 1 INTRODUCTION 1.1 LDPC Code Encoding 1.2 LDPC Code Decoding 2.3 Interesting Issues in VLSI Implementation of LDPC Decoder 2.3.1 Code Constructions 2.3.2 Functional Units of Decoder 3.3.3 Decoding Algorithms 3.3.4 Toward Good Performance 3.4 Thesis Organization 4HAPTER 2 BACKGROUND INFORMATION 5.1 Low-Density Parity Check Codes 5.2 Quasi-Cyclic LDPC Codes 9.3 Quasi-Cyclic LDPC Constructions 9.3.1 Array Based LDPC Constructions 10.4 Efficient LDPC Code Encoding 10.4.1 Quasi-Cyclic LDPC Encoding 12HAPTER 3 DECODING ALGORITHMS 13.1 LDPC Code Decoding Overview 13.2 Message Passing Algorithm 15.2.1 Summary of Log -Message Passing Algorithm 17.3 Tanh Rules 18.3.1 Multitiplicative Form 19.3.2 Additive Form 20.4 Min-Sum Algorithm 23.4.1 Summary of Min-Sum Algorithm 24.5 Modified Min-Sum Algorithm 25.5.1 Summary of Modified Min-Sum Algorithm 26.6 Summary of Decoding Algorithms 26HAPTER 4 LDPC DECODER ARCHITECTURES 31.1 LDPC Decoder Architectures Overview 31.2 Partially Parallel Based LDPC Decoder Architectures 34.2.1 Partially Parallel Based LDPC Decoder Architectures Processing 36.2.2 Memory Addressing 37.3 Key Functional Units in LDPC Decoder 38.3.1 Bit-Node-Unit 39.3.2 Check-Node Unit 41.4 Partially Parallel LDPC Decoder Diagram 45.4.1 A Prototype Partially Parallel LDPC Decoder 45HAPTER 5 DECODER PROTOTYPING IMPLEMENTATION AND DISCUSSION 47.1 Prototype (3, 6) Partially Parallel LDPC Decoder Specification 47.2 Simulation Results 48.3 Evaluation 56.3.1 Finite State Machine Design 57.3.2 Synthesis Results and Discussions 59HAPTER 6 CONCLUSION AND FUTURE WORK 65.1 Conclusion 65.2 Future Work 65.2.1 Encoding Methods 66.2.2 Code Constructions 66.2.3 Functional Units 66.2.4 Decoding Process 67EFERENCE 6