Trapping sets with short cycles are known to give a detrimental effect on the error floor performance of a low-density parity-check (LDPC) code. Unlike in binary LDPC codes., short cycles in a nonbinary low-density parity-check (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 this paper, we first develop a novel message-passing algorithm and identify how it is related to the FRC. We then propose a low-complexity algorithm for counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles.
Trapping sets with short cycles are known to give a detrimental effect on the error floor performance of a low-density parity-check (LDPC) code. Unlike in binary LDPC codes., short cycles in a nonbinary low-density parity-check (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 this paper, we first develop a novel message-passing algorithm and identify how it is related to the FRC. We then propose a low-complexity algorithm for counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles.
Short cycles in a nonbinary low-density parity-check (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 important 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 this paper, we first develop a novel message-passing algorithm and identify how it is related to the FRC. We then propose a low-complexity algorithm for counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles. Finally, we propose a low-complexity algorithm for designing an NB-LDPC code with low error floor. Depending on the modulation scheme, the codes constructed by the proposed design algorithm have similar or slightly worse performance, compared with those constructed via the method by Poulliat et al. However, the proposed design algorithm does not require a cycle enumeration algorithm with high complexity, and therefore is feasible even in the case of large code length, say ≥5000.
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.
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or as a tool to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes, and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find a variety of graphical objects, such as absorbing sets and Zyablov-Pinsker trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. This algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. The algorithm is initiated with a set of short cycles as the input. The cycles are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
Short or moderate-length non-binary low-density parity-check (NB-LDPC) codes have the potential applications in future low latency and high-reliability communication thanks to the strong error correction capability and parallel decoding. Because of the existence of the error floor, the NB-LDPC codes usually cannot satisfy very low bit error rate (BER) requirements. In this paper, a low-complexity method is proposed for optimizing the minimum distance of the NB-LDPC code in a progressive chord edge growth manner. Specifically, each chord edge connecting two non-adjacent vertices is added to the Hamiltonian cycle one-by-one. For each newly added chord edge, the configuration of non-zero entries corresponding to the chord edge is determined according to the so-called full rank condition (FRC) of all cycles that are related to the chord edge in the obtained subgraph. With minor modifications to the designed method, it can be used to construct the NB-LDPC codes with an efficient encoding structure. The analysis results show that the method for designing NB-LDPC codes while using progressive chord edge growth has lower complexity than traditional methods. The simulation results show that the proposed method can effectively improve the performance of the NB-LDPC code in the high signal-to-noise ratio (SNR) region. While using the proposed scheme, an NB-LDPC code with a quite low BER can be constructed with extremely low complexity.
It is well-known that the presence of cycles in a factor graph degrades the performance of message-passing algorithms due to the violation of the assumption of statistical independence of messages.While finding and counting all cycles in a graph is a very hard problem, efficient algorithms have been proposed recently to find all short cycles up to some maximum length.For the message-passing decoding of Low-Density Parity-Check (LDPC) codes, these short cycles are the main cause for the existing performance gap to optimal Maximum Likelihood (ML) decoding.In this paper, we exploit this observation in the proposed novel method of realizing rate-compatible (RC) LDPC codes with short block lengths by inserting known dummy bits into the information bit sequence before encoding.This technique can be seen as a special case of traditional code shortening and allows to achieve lower code rates using one fixed rate mother code.The novelty of the proposed method lies in the selection of the specific dummy bit positions in a way that "breaks" a significant number of short cycles in the mother code's graph which, thus, no longer degrade the decoding performance.