低密度校驗碼之信度傳播排程及其性能分析

Abstract

低密度校驗碼最常用的解碼方式是信度傳播演算法，它利用遞迴的方式達到近似最佳的效能，但缺點是需要大量的遞迴次數，而且，硬體的實現也是一大困難。信度傳播演算法很適合採用完全平行的處理，但若要達到此目的，則需要大量的記憶體、處理器及複雜的連接繞線網路，目前的技術尚無法解決此問題，硬體實作仍須採取分群來進行串連式處理。因此，學術上提出了兩種新的演算法去增加收斂的速度以及減少記憶體的使用，一為垂直式重組信度傳播演算法，另一為水平式重組信度傳播演算法。然而，這兩種演算法並未考慮低密度校驗碼本身既有的迴圈效應，為了解決此問題，我們提出一套新的排程，盡可能地降低迴圈的影響。根據模擬的結果，在IEEE 802.11n這套標準下，此排程的確讓錯誤率減少了0.5 ~ 0.2 dB，其優點在遞迴次數少的情況下更加顯而易見。此外，我們亦提出了一套分析解碼演算法收斂行為的方法，並將分析結果與電腦模擬的解碼效能做比較，進而利用這套方法來解釋不同的解碼排程及不同碼的收斂行為與框錯誤率性能表現。

Low density parity check (LDPC) codes form a class of sparse graph codes that offer powerful error-correcting capability. For decoding LDPC codes, the belief propagation (BP) or sum-product algorithm (SPA) is usually used. However, implementation of a BP-based LDPC decoder often requires large memory space and very high degree of parallelism using many component soft-in soft-output (SISO) decoding units and complex interconnect network to perform message passing from variable nodes to check nodes or vice versa. An obvious solution for a relatively long code is to divide a decoding iteration into several serial sub-iterations in which a sub-iteration performs only part of the complete parallel message-passing operation.

There are several architectures and decoding schedules for serial implementation of LDPC decoders. We are interested in two of the more popular ones, namely, the horizontal shu²ed BP (HSBP) and the vertical shuffed BP (VSBP) algorithms. It has been shown that, with a proper architecture and scheduling, such parallel-serial decoding methods not only require less storage space but also give faster convergence and, sometimes, better performance. A shortcoming of these existing schedules is that they are more concerned with reduction of memory and interconnect complexities and do not consider the short cycle effect which is the dominant factor limiting a BP-based algorithm's bit error rate (BER) performance.

We propose a simple scheduling approach for reducing the short-cycle effect in a BP-based decoding algorithm. The impact of a short cycle can be lessened if one alternates the decoding schedule so that the cycle length can be effectively extended. The HSBP and VSBP algorithms partition the check or variable nodes into several groups where a group consists of (almost) the same number of consecutive nodes according to the natural order of the parity-check matrix and carry out the BP process group-by-group. Our algorithm groups the check nodes according to the number of short cycles a node is involved. Message-passing to a group with more short cycles is given lower priority in our decoding schedule. The resulting decoding algorithm is referred to as the cycle-based HSBP (or VSHP) algorithm.

Another major contribution of this thesis is the development of a convenient and effective method to explain and predict both the performance and the convergence be- havior of a candidate LDPC code and the corresponding decoding algorithm/schedule.We define a function called message profile that describes the composition of the ex- trinsic information associated with a bit node. This function measures how much each bit node has contributed to the extrinsic information of a bit from the beginning of the decoding process up to the end of a given iteration. The normalized correlation spread (NCS) of a bit, defined as the mean-to-root-mean-squared ratio of its message profile, is then used to evaluate the degree of local flooding uniformity of a bit node in a particular iteration. The NCS of a bit node usually converge in just a few iterations and more importantly, all NCS' converge to the same steady-state value though not uniformly. Numerical results indicate that a BP-based algorithm converges when the NCSs of all bits converge, i.e., the convergence of the message-profile functions is consistent with convergence of the decoder. Furthermore, it is found that the decoder performance is directly related to the common steady state value{the larger it is, the better the BER performance becomes.