Design of Low-Density Parity-Check Codes and Their Decoding Algorithms
조성혜
Abstract
In this thesis, we propose low-complexity designing algorithms for non-binary low-density \nparity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding \nalgorithms for binary LDPC codes. \nWe first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) \nbased on message-passing algorithms. Short cycles in an NB-LDPC code may be even \nmore harmful to its performance if they do not satisfy the so-called full rank condition \n(FRC). This is because they may induce low-weight codewords or absorbing sets in that \ncase. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as \nthe number of short cycles for analyzing the performance of an NB-LDPC code. In order to \ncount those cycles, we first develop a novel message-passing algorithm and identify how it \nis related to the FRC.We then propose a low-complexity algorithmfor counting the number \nof short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short \ncycles. The proposed algorithm is not only theoretically validated, but its computational \nand storage complexities are also computed. It does not require cycle enumeration with \nhigh complexity, and therefore is still feasible even in the case of large code length, say \n≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal \nrule to choose a nonzero element for a given edge and propose a low-complexity algorithm \nfor designing an NB-LDPC code with low error floor. Furthermore, several design examples \nare presented to verify the validity of the proposed design algorithm. \nSecondly, we propose a low-complexity decoding algorithm for binary LDPC codes over \nthe binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding \nalgorithm for binary LDPC codes and has lower computational complexity than the \nsum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it \nhas performance degradation. Furthermore, reducing the number of bits for representing \nmessages to two in a decoding algorithm for further reducing computational and storage \ncomplexities, causes significant performance losses. In order to minimize the performance \ndegradation and computational and storage complexities, we propose a low-complexity \ndecoding algorithm which uses several decoders with two-bit precision for binary LDPC \ncodes over the BSC. The proposed algorithm adaptively changes decoders according to \nthe number of unsatisfied check nodes at each iteration. Compared with the SPA using \nfloating-point operations, the proposed decoding algorithm greatly reduces computational \nand storage complexities with negligible performance losses. Numerical results show that \nthe proposed decoding algorithm has similar performance to the SPA with floating-point \noperations over the BSC. \nIn the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes \nfor the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms \nB (GDB) and E (GDE) for binary LDPC codes have much lower computational \ncomplexity and much less required memory size than the SPA. This is because GDB and \nGDE only use binary or integer operations, while the SPA requires real operations and \na look-up table. However, they are hardly used in commercial communication systems \nsince they have poorer performance than the SPA. Layered-division multiplexing (LDM) \nis considered in ATSC 3.0 in order to deliver multiple broadcasting streams with distinct \nrobustness in a single radio frequency channel. Due to the unique characteristic of the \nLDM, we propose to use GDB or GDE rather than the SPA for decoding the core layer signal \nat fixed receivers. Numerical results show that the computational complexity and the \nrequired memory size can be reduced without any performance loss by about 50 percent \nand 80 percent, respectively, when GDB and GDE are employed.