低複雜度與高效能之低密度奇偶校驗碼解碼演算法、解碼器架構與合作式編解碼之研究設計

Abstract

本論文針對低密度奇偶校驗碼(low-density parity-check code, LDPC code)的解碼演算法，硬體架構與其在合作式編解碼技術(cooperative coding and decoding scheme)之應用做完整的討論與改進。並且在論文的最後進一步提出結合渦輪碼(turbo codes)與低密度奇偶校驗碼概念的新編解碼技術。 在低密度奇偶校驗解碼演算法方面，本論文提出了數個權衡效能與複雜度(performance and complexity tradeoff)與一個以高效能為取向的改良演算法。雖然位元翻轉(bit-flipping, BF)解碼演算法相較於訊息傳遞(message passing, MP)解碼演算法有較低的運算複雜度，但卻有著解碼效能較差與遞迴(iteration)次數較高的缺點。本論文所提出的低度相關禍首位元測試多位元翻轉(low-correlation culprit-bit-test multi-bit flipping, LCCBT-MBF)解碼演算法與MP解碼演算法相比，所提出的解碼演算法在相同的遞迴次數條件下不僅有著近似的效能同時亦具有較低的運算複雜度。此外，為了進一步拉近MP演算法與最大概似(maximum likelihood, ML)解碼演算法之效能差距，本論文提出了一個利用基因協助訊息傳遞(genet-ics-aided message passing, GA-MP)解碼演算法，利用基因演算法的概念來進一步提升MP解碼演算法之效能，其複雜比現有方法小且效能更好。 在低密度奇偶校驗解碼器設計方面，本論文也提出了數個針對不同面向的改進。首先，由於在低密度奇偶校驗碼的解碼過程中，校驗節點單元(Check Node Unit, CNU)的延遲時間過長往往是硬體高速設計的瓶頸。因此本論文針對自我訊息排除校驗結點單元(self-message-excluded CNU, SME-CNU)與兩個最小值校驗結點單元(two-minimum CNU, TM-CNU)架構提出了數個系統化比較演算法。接著，本論文提出了一個解碼進程、解碼器架構與記憶體結構的共同最佳化設計得以同時處理兩筆不同的碼字(codeword)並保持100%的硬體使用率。此外，為了降低固定點(fixed-point)硬體實現所造成的量化誤差，本論文也提出了一個利用新定義的三項測試指標來消除量化所造成的錯誤。接著本論文提出之一個針對分層解碼的奇偶校驗矩陣重新排序(reordering)技術來進一步提高硬體的利用率並採用所提出的遞迴式TM-CNU比較架構與非均勻量化技巧來同時達到減少量化位元與維持解碼效能的效果。此外，在解碼器設計部分的最後，本論文針對所有提出的解碼演算法進行解碼器實現設計。 由於渦輪碼與低密度奇偶校驗碼同為現今效能最佳的兩種通道編碼技術，本論文提出了一個結合兩者解碼概念的新的編解碼技術，稱為渦輪低密度奇偶校驗碼(Turbo-LDPC code)。與區塊渦輪-BCH(block turbo coding-BCH, BTC-BCH)碼相比，所提出的Turbo-LDPC碼不但有著較高的效能與更低的運算複雜度。有鑑於Turbo-LDPC的高效能增益，本論文更進一步延伸Turbo-LDPC碼的二維區塊碼結構到三維的立方碼結構，命名為三重低密度奇偶校驗碼(Triple-LDPC)碼。與Turbo-LDPC碼相比，Triple-LDPC碼在近似的運算複雜度下有更佳的解碼效能。此外，根據我們的分析，我們也發現所提出的Turbo-LDPC與Triple-LDPC codes非常適合應用在分散式中繼網路(Relay network)架構中的合作式編碼(cooperative coding)技術，可以大幅降低中繼站(Relay station)的硬體複雜度並且有較佳的錯誤更正能力。

This dissertation conducts a thorough investigation on various technology aspects of low-density parity check (LDPC) codes, and then proposes corresponding efficient techniques for effective decoding and realization of LDPC codes. The investigated issues include decoding algorithms, hardware architectures of LDPC codes, and application of LDPC codes to cooperative coding and decoding. Furthermore, new coding schemes based on the joint concepts of LDPC and Turbo codes have been proposed in the end of the dissertation. Bit-flipping (BF) LDPC decoding algorithms have lower complexity compared with message passing (MP) algorithms, but have the drawbacks of lower decoding performances and higher iteration counts. In order to significantly enhance BF algorithms, a performance-boosting algorithm, called low-correlation culprit-bit-test multi-bit flipping (LCCBT-MBF) algorithm, has been proposed and integrated with BF algorithms. Besides, this work proposes a genet¬ics-aided message passing (GA-MP) algorithm by applying a new genetic algorithm to further improve the decoding performance of MP algorithm. Long delay time of the check node units are usually the major bottleneck in LDPC decoders for high-speed applications. Hence, this dissertation proposes several improved comparison algorithms for self-message-excluded CNU (SME-CNU) and two-minimum CNU (TM-CNU) architectures. Next, in order to eliminate the idling time and hardware complexity in conventional partially-parallel decoders, this work proposes a decoder architecture which can handle two different codewords simultaneously with 100% hardware utilization. Since LDPC decoding operations can be conducted very effectively with layered decoding schemes (LDS), a decoder architecture with an optimized execution reordering scheme for LDS is also proposed. In the final part of decoder designs, we implement the corresponding LDPC decoders for all the proposed decoding algorithms. Next, we propose an efficient coding scheme, called Turbo-LDPC code, which combines the merits of both the turbo code and LDPC code. The decoding performance is significantly improved by utilizing turbo decoding process, while the major part of the decoder is basically the same as a conventional LDPC decoder. Compared to combined block turbo code and BCH codes, the proposed Turbo-LDPC code also has much better decoding performance as well as lower computational complexity. Due to the significant improvements of the proposed Turbo-LDPC codes in decoding performance, the 2D coding scheme is extended to a new 3D codes, named Triple-LDPC codes. Finally, both proposed coding schemes are applied to cooperative coding in relay networks. Some cooperative coding and decoding schemes are devised based on these two codes. From analysis and simulations, the new cooperative coding/decoding techniques can significantly reduce the hardware complexity in relay stations, while obtain better error-correction capabilities.