Low-density parity-check (LDPC) lattices are introduced by Sadeghi et al. (2006). The construction method of such lattices and the decoding algorithm based on the min-sum algorithm are also proposed in [1]. In this paper we apply two iterative message passing algorithms, the sum-product algorithm and the max-product algorithm, to the Tanner graph representation of LDPC lattices. We evaluate the performance of two iterative message passing algorithms.
Low-density parity-check (LDPC) lattices are introduced by Sadeghi et al. (2006). The construction method of such lattices and the decoding algorithm based on the min-sum algorithm are also proposed in [1]. In this paper we apply two iterative message passing algorithms, the sum-product algorithm and the max-product algorithm, to the Tanner graph representation of LDPC lattices. We evaluate the performance of two iterative message passing algorithms.
Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands
The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule". Unlike flooding, the probabilistic schedule operation is based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268, 456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.
We study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.
The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule." Unlike flooding, the probabilistic schedule operates based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268,456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.
Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.
Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes.