Non-binary low-density parity-check (NB-LDPC) codes can offer promising performance advantages but suffer from high decoding complexity. To tackle this challenge, in this paper, we consider NB-LDPC codes over finite fields as codes over subfields as a means of reducing decoding complexity. In particular, our approach is based on a novel method of expanding a non-binary Tanner graph over a finite field into a graph over a subfield. This approach offers several decoding strategies for a single NB-LDPC code, with varying levels of performance-complexity trade-offs. Simulation results demonstrate that in a majority of cases, performance loss is minimal when compared with the complexity gains.
Non-binary low-density parity-check (NB-LDPC) codes can offer promising performance advantages but suffer from high decoding complexity. To tackle this challenge, in this paper, we consider NB-LDPC codes over finite fields as codes over subfields as a means of reducing decoding complexity. In particular, our approach is based on a novel method of expanding a non-binary Tanner graph over a finite field into a graph over a subfield. This approach offers several decoding strategies for a single NB-LDPC code, with varying levels of performance-complexity trade-offs. Simulation results demonstrate that in a majority of cases, performance loss is minimal when compared with the complexity gains.
NB-LDPC codes, a class of codes well-known for their exceptional error correcting performance, are not yet used widely in practice due to the high complexity of decoding algorithms. In this paper, we propose a low complexity decoder for these codes by means of a novel graph expansion. We view the finite field over which the code is constructed as the quadratic extension of one of its subfields, and then expand the Tanner graph of the code into a graph over that particular field. Decoding algorithm, which is tailored for this larger graph, presents significant complexity gains while the performance loss is minimal.
Non-binary low-density parity-check (NB-LDPC) codes are known to offer several advantages over their binary counterparts, but the higher complexity, and the resource-hungry nature of decoding algorithms have so far restricted their practical usage. In this paper, we propose a new decoding algorithm for NB-LDPC codes over finite fields of characteristic 2, based on a novel binary expansion of the Q-ary Tanner graph. While it offers substantial complexity gains, simulation results demonstrate that the performance loss of the new algorithm, in comparison to the best known decoder, is quite small. Furthermore, due to being based on a binary graph, it is particularly attractive for hardware implementations. We also suggest a simplified version of the algorithm, which offers even higher gains in complexity.
Low-density parity-check (LDPC) codes defined over non-binary (NB) finite field GF(2q)(q >1) achieve better error-correcting performance than binary LDPC codes when the codeword length is moderate. The decoder complexity increases very fast with the order of the field, 2q, although the error-correcting performance also improves. To reduce the complexity for practical applications, NB-LDPC codes over lower-order finite fields are of great interest. Previous designs have been focusing on decoders over either the smallest NB field GF (4) or much larger fields, such as GF (32) or higher. Prior optimization techniques are either not applicable or do not lead to efficient designs for codes over GF (8) or other lower-order fields. In this paper, an efficient architecture is developed for the check node processing, which is the most complicated step in NB-LDPC decoding, for the Min-max algorithm over lower-order fields. By utilizing the properties of finite field elements, the max/min comparison results are shared and the number of comparators needed is reduced significantly. Compared to the best prior design, the proposed check node processing has 18.5% smaller area and shorter critical path for an example code over GF (8).
Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, the coding gain of NB-LDPC codes comes from the expense of computational complexity. \n \nIn this thesis, we consider the problem of a trade-off between reasonable complexity and good error-rate performance of decoding nonbinary LDPC codes over GF(q). We first introduce the existing decoding algorithms of nonbinary LDPC codes and compare with decoding algorithms of binary LDPC codes. Second, low-complexity decoding algorithms of nonbinary LDPC codes is considered and two low-complexity symbol-flipping algorithms based on D-SFDP is proposed. These algorithms outperform the existing D-SFDP algorithm by improving the flipping metric. Proposed algorithms provide good trade-off between complexity and error performance.
Compared to binary low-density parity-check (LDPC) codes, nonbinary (NB) LDPC codes can achieve higher coding gain when the codeword length is moderate, but at the cost of higher decoding complexity. One major bottleneck of NB-LDPC decoding is the complicated check node processing. In this paper, a novel relaxed check node processing scheme is proposed for the min-max NB-LDPC decoding algorithm. Each finite field element of GF(2p) can be uniquely represented by a linear combination of p independent field elements. Making use of this property, an innovative method is developed in this paper to first find a set of the p most reliable variable-to-check messages with independent field elements, called the minimum basis. Then, the check-to-variable messages are efficiently computed from the minimum basis. With very small performance loss, the complexity of the check node processing can be substantially reduced using the proposed scheme. In addition, efficient VLSI architectures are developed to implement the proposed check node processing and the overall NB-LDPC decoder. Compared to the most efficient prior design, the proposed decoder for a (837, 726) NB-LDPC code over GF(25) can achieve 52% higher efficiency in terms of throughput-over-area ratio.
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.