Open Access System for Information Sharing

Login Library


Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Design of Low-Density Parity-Check Codes and Their Decoding Algorithms

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


  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Views & Downloads