IEEE Transactions on Communications

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Eirik Rosnes, Øyvind Ytrehus

Published Nov 6, 2018• 5 citations

Abstract

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

DOI: 10.1109/tcomm.2018.2879107

Related papers

ML and Near-ML Decoding of LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles. Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the upper bounds on the ML decoding performance.

arXiv:1709.01455Sep 5, 20171 citation

Wrap-around sliding-window near-ML decoding of binary LDPC codes over the BEC

Irina E. Bocharova, Boris D. Kudryashov, Eirik Rosnes +2 more

A novel method of low-complexity near-maximum-likelihood (ML) decoding of quasi-cyclic (QC) low-density parity-check (LDPC) codes over the binary erasure channel is presented. The idea is similar to wrap-around decoding of tail-biting convolutional codes. ML decoding is applied to a relatively short window which is cyclically shifted along the received sequence. The procedure is repeated until either all erasures have been corrected, or no new erasures are corrected at a certain round. A new upper bound on the ensemble-average ML decoding error probability for a finite-length row-regular LDPC code family is derived and presented. Furthermore, a few examples of regular and irregular QC LDPC codes are studied by simulations and their performance is compared with the ensemble-average performance. Finally, the impact of the codeword weight and stopping set size spectra on the ML and belief-propagation decoding performance is discussed.

International Symposium on Turbo Codes and Iterative Information ProcessingSep 1, 20162 citations

Performance of ML decoding for ensembles of binary and nonbinary regular LDPC codes of finite lengths

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek

The Gallager ensembles of binary regular LDPC codes and binary images of nonbinary regular LDPC codes are studied. Recurrent procedure for computing average spectra for these two ensembles is presented. By using the existing bounding techniques, estimates on the error probability of the maximum-likelihood (ML) decoding over an AWGN channel with BPSK signaling for short codes from different ensembles of LDPC codes are obtained. The numerical results show performance of the ML decoding for different code ensembles. Conclusions drawn based on the average code spectra are then verified by near-ML decoding simulations for both randomly selected and the best known short codes. The asymptotic ML decoding thresholds for AWGN and BSC channels are calculated. As expected, codes with the ML decoding performance superior to that of the average code in the ensemble, are easy to find. However, comparison of the the presented results with simulation results for belief propagation (BP) decoding shows that the ML decoding performance should not be used as a target for searching for good iteratively decodable codes.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20178 citations

BP-LED Decoding Algorithm for LDPC Codes Over AWGN Channels

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +1 more

A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation-list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes.

arXiv:1705.09507IEEE Transactions on Information TheoryAug 24, 201814 citations

A decoding algorithm for LDPC codes over erasure channels with sporadic errors

Gianluigi Liva, Enrico Paolini, Balázs Matuz +1 more

An efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes.

Allerton Conference on Communication, Control, and ComputingSep 1, 201011 citations

Design and Analysis of LDPC Convolutional Codes

Arvind Sridharan

Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.

Sep 15, 202230 citations