Following Poulliat et al.'s design of (2, dc) nonbinary LDPC (NB-LDPC) codes, this paper designs high-rate irregular NB-LDPC codes by addressing the problem of minimum symbol distance. The design procedure first identifies all stopping sets up to weight five in an LDPC code and enumerates them via a message passing algorithm. For each identified stopping set, careful labeling forces its corresponding parity-check sub-matrix to be full rank, thereby preventing the stopping set from being a sub-code and ensuring a minimum distance of at least six symbols. Simulation results for codes designed through this procedure show a significant improvement in the error-floor region over randomized labeling.
Following Poulliat et al.'s design of (2, dc) nonbinary LDPC (NB-LDPC) codes, this paper designs high-rate irregular NB-LDPC codes by addressing the problem of minimum symbol distance. The design procedure first identifies all stopping sets up to weight five in an LDPC code and enumerates them via a message passing algorithm. For each identified stopping set, careful labeling forces its corresponding parity-check sub-matrix to be full rank, thereby preventing the stopping set from being a sub-code and ensuring a minimum distance of at least six symbols. Simulation results for codes designed through this procedure show a significant improvement in the error-floor region over randomized labeling.
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.
Abstract: Small stopping sets have been proved to be harmful to the error floor performance of a finite-length irregular low-density parity-check (LDPC) code over the binary erasure channel (BEC). On the additive white gaussian noise (AWGN) channel, small stopping sets are expected to have a similar effect. This paper proposes an algorithm that iteratively removes the small-stopping-set-inducing patterns from the graph of a randomly generated irregular LDPC code by means of node exchange, aiming at enlarging the average size of stopping sets in this code. Computer simulation results show that the short-length LDPC codes after our processing achieve a considerable performance improvement in the low-BER region compared to the randomly generated codes. Key words: Error floor, irregular LDPC codes, iterative processing, small stopping set 1
In this paper, we present a construction method based on the progressive edge-growth (PEG) algorithm to design irregular low-density parity-check (LDPC) codes without small stopping sets. We show how to choose the connections in the PEG algorithm when having multiple choices to connect a variable node with a check node. Since preventing small stopping sets also prevents a low minimum distance, our construction method also leads to LDPC codes with a higher minimum distance. Furthermore, we show by simulation that our construction method improves the performance over the binary erasure channel and over the additive white Gaussian noise channel for a low erasure probability and a high signal-to-noise ratio, respectively.
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
…
Low-density parity-check (LDPC) codes in conjunction with iterative decoding based on message-passing algorithms have been shown to achieve excellent performance over a variety of communication channels. In this dissertation, we investigate LDPC codes under two scenarios which present different challenges for providing robust communications. First, LDPC codes are analyzed and designed for time-selective, frequency-nonselective complex-fading channels where both the amplitude and the phase of the transmitted signal are altered by the channel. To combat the fading, we use a pilot symbol-assisted scheme where known pilot symbols are added to the LDPC code and used to help estimate the channel at the receiver. Using asymptotic, infinite-length analysis, we investigate several iterative, message-passing, joint-estimation-and-decoding strategies; optimal energy distribution between pilot and data symbols; and LDPC code design. Several interesting results are obtained regarding unification of analysis and code design. Next, we address the issue of achieving very low error rates with practical, finite-length LDPC codes for binary erasure channels. Finite-length LDPC codes suffer from error floors which limit the achievable error rate, and this error-floor performance is determined by stopping sets. Asymptotic analysis of weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with lower error floors but does not reflect the behavior of sublinearly-sized stopping sets, which can dominate the iterative-decoding, error-floor performance. Thus, we provide a perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, advantages of protograph structure, and effects of precoding. We show for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly-growing stopping sets, and this polynomial relationship can be approximately captured by a single parameter. Further, we begin to address the question, Given finite stopping-set sizes and finite codelengths, do the stopping sets follow the behavior predicted by linear or sublinear analysis?
Abstract — In this paper, a method to design regular (2, dc)-LDPC codes over GF(q) with both good waterfall and error floor properties is presented, based on the algebraic properties of their binary image. First, the algebraic properties of rows of the parity check matrix H associated with a code are characterized and optimized to improve the waterfall. Then the algebraic properties of cycles and stopping sets associated with the underlying Tanner graph are studied and linked to the global binary minimum distance of the code. Finally, simulations are presented to illustrate the excellent performance of the designed codes. Index Terms — channel coding, error correction coding, nonbinary LDPC codes, iterative decoding, binary image. I.