低複雜度部份平行搭配排層解碼的低密度奇偶校驗碼解碼器架構之設計

Abstract

低密度奇偶校驗碼(Low-Density Parity-Check Code)最早是由R.G. Gallager博士在1962於其博士論文發表，此種編碼方式有著非常優越的性能，且其更正能力更遠超其他的編碼技術，其解碼效能十分逼近向農極限(Shannon limit)。因此近幾年來，許多通訊標準逐漸將LDPC列為選擇性或者指定採用的錯誤更正碼技術。 有鑑於LDPC碼與其他編碼技術相比，擁有高效能卻高複雜度，因此本論文主要研究LDPC解碼器在硬體設計上的簡化複雜度之做法，而本文是採用802.15.3c通訊標準，Code rate為1/2的LDPC碼，實做了一個LDPC解碼器。考量到解碼器效能與複雜度的取捨，此解碼器採用CNU (Check Node Updating Unit)部份平行，BNU (Bit Node Updating Unit)完全平行的設計，此種設計搭配排層解碼(Layered Decoding Scheme)，可獲得降低解碼所需的疊代次數(Required iteration counts)與減少約50%的訊息儲存記憶體的好處。 在進行電路設計之前，本文首先將15.3c規格下之奇偶校驗矩陣重新編排(Parity-Check Matrix Reordering)，使其可用最少的CNU與BNU功能單元和繞線網路(Routing Network)，來完成整個奇偶校驗矩陣的訊息傳遞解碼，由EDA合成軟體結果得知，使用奇偶校驗矩陣重新編排可以減少約30%的組合邏輯電路面積。 在CNU架構上，本論文提出一個新的排序演算法結合了目前存在的Double-elimination (DE) 演算法與Trace-back (TB) 演算法，此一演算法擁有高速且低複雜度的優點，針對某些特定的輸入數目，此演算法有最短的延遲時間與最低的硬體複雜度。實驗結果也顯示，在相同的時間限制下，本論文提出的做法有最小的硬體面積。採用此種演算法，可更進一步降低CNU的面積約26%。 最後，本論文也實驗了非均勻量化 (Non-uniform quantization) 的LDPC解碼器，從模擬結果得知，相較於一般均勻量化的LDPC解碼器，會損失輕微的效能，在10-6的錯誤率約0.1dB，而解碼器的面積比一般均勻量化的LDPC解碼器小了約2%。

Low-Density parity check (LDPC) code was first introduced by Dr. Gallager in 1962. This code has very much better error detection and error correction performances than other codes. It can achieve performance close to Shannon bound. In the recent years, LDPC codes have been adopted by many communication systems. Since LDPC codes have good performance but high complexity, this thesis focuses on the complexity reduction in the hardware implementation. In this thesis, we proposed the LDPC decoder architecture for the code construction of 1/2-rate in the 802.15.3c communication standard. Considering the trade-off between performance and hardware complexity, we adopt partially-parallel CNU architecture and fully-parallel BNU architecture, and use layered decoding scheme for the decoding procedure. By using layered decoding scheme, the required iteration number is reduced and the required message memory is reduced by about 50%. Before implementing the decoder hardware, we reorder the parity-check matrix in order to reduce the required number of CNUs, BNUs, and routing networks. We found that the combinational-logic area in the LDPC decoder is reduced by about 30% after reordering the parity-check matrix. In the CNU architecture, we proposed a new comparison scheme and named it Iterative 2-Min Modular (IMM) comparison scheme, which can be viewed as the compromise design between the existing Double-elimination (DE) scheme and Trace-back (TB) scheme. It has the advantage of high speed and low complexity. For some specific number of CNU inputs, it takes the shortest latency and the least required comparators. By using this comparison scheme, we can further reduce the CNU area. According to the synthesis result, the IMM comparison scheme provides the smallest area than the other comparison schemes in the same time constrain. By adopting the IMM comparison scheme, the CNU area is reduced by about 26%. At the end, we implement the non-uniform quantization scheme in the decoder architecture. As a result, compared with the general uniform quantization architectures, it has a slight performance loss which is about 0.1dB at BER 10-6, and it can reduce the overall decoder area by about 2%.