This paper presents new FEC codes for the erasure channel, LDPC-Band, that have been designed so as to optimize a hybrid iterative-Maximum Likelihood (ML) decoding. Indeed, these codes feature simultaneously a sparse parity check matrix, which allows an efficient use of iterative LDPC decoding, and a generator matrix with a band structure, which allows fast ML decoding on the erasure channel. The combination of these two decoding algorithms leads to erasure codes achieving a very good trade-off between complexity and erasure correction capability.
LDPC codes are another class of binary codes providing good level of decoding performance with extremely fast encoding decoding algorithms @cite_1 @cite_4 . Indeed, the classical iterative decoding algorithm for the erasure channel, based on the work of Zyablov @cite_9 , has a linear decoding complexity. The drawback of this algorithm is that it does not reach the performance of ML decoding. Moreover, the sparsity of the matrices also reduces the ML performance compared to full random matrices.
@cite_9 @cite_1 @cite_4
2949560198 1602682102 2172190188 2123119950
We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous nonasymptotic results for LDPC codes, and in particular, exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on the Tanner graph of the code. An interesting by-product of our analysis is to establish the existence of ldquoprobabilistic expansionrdquo in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst case setting. This work focuses on the decoding algorithm of the LDPC large block FEC codes for the packet erasure channel, also called AL-FEC (Application-Level Forward Error Correction). More specifically this work details the design and the performance of a hybrid decoding scheme, that starts with the Zyablov iterative decoding algorithm, a rapid but suboptimal algorithm in terms of erasure recovery capabilities, and, when required, continues with a Gaussian elimination algorithm. For practical reasons this work focuses on two LDPC codes for the erasure channel, namely LDPC-staircase and LDPC-triangle codes. Nevertheless the decoding scheme proposed can be used with other LDPC codes without any problem. The performance experiments carried out show that the erasure recovery capabilities of LDPC-triangle codes are now extremely close to that of an ideal code, even with small block sizes. This is all the more true with small code rates: whereas the Zyablov iterative decoding scheme becomes unusable as the code rate decreases, the Gaussian elimination makes the LDPC-triangle codes almost ideal. In all the tests, when carefully implemented, the LDPC-triangle codec featuring the proposed decoding scheme is fast, and in particular always significantly faster than the reference Reed-Solomon on GF( @math ) codec. The erasure recovery capabilities of LDPC-staircase codes are also significantly improved, even if they remain a little bit farther from an ideal code. Nevertheless, a great advantage is the fact that LDPC-staircase codes remain significantly faster than LDPC-triangle codes, which, for instance, enables their use with larger blocks. All these results make these codes extremely attractive for many situations and contradict the common belief that using Gaussian elimination is not usable because of a prohibitive processing load. Moreover the proposed approach offers an important flexibility in practice, and depending on the situation, one can either choose to favor erasure recovery capabilities or the processing time. The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes. An iterative decoding threshold analysis for terminated regular LDPC convolutional (LDPCC) codes is presented. Using density evolution techniques, the convergence behavior of an iterative belief propagation decoder is analyzed for the binary erasure channel and the AWGN channel with binary inputs. It is shown that for a terminated LDPCC code ensemble, the thresholds are better than for corresponding regular and irregular LDPC block codes.