Entropy

Error Exponents of LDPC Codes under Low-Complexity Decoding

Pavel S. Rybin, Kirill Andreev, Victor Zyablov

Published Feb 22, 2021• 5 citations

Abstract

This paper deals with the specific construction of binary low-density parity-check (LDPC) codes. We derive lower bounds on the error exponents for these codes transmitted over the memoryless binary symmetric channel (BSC) for both the well-known maximum-likelihood (ML) and proposed low-complexity decoding algorithms. We prove the existence of such LDPC codes that the probability of erroneous decoding decreases exponentially with the growth of the code length while keeping coding rates below the corresponding channel capacity. We also show that an obtained error exponent lower bound under ML decoding almost coincide with the error exponents of good linear codes.

DOI: 10.3390/e23020253

Related papers

On the Error Exponents of Capacity Approaching Construction of LDPC code

Pavel S. Rybin, Alexey Frolov

In this paper we consider low-density parity-check (LDPC) codes with special construction. We obtain the lower-bounds on the error exponents for these codes under proposed low-complexity decoding algorithm and under a well known maximum likelihood decoding algorithm. We show that such LDPC code with special construction exists, that the error probability of the low-complexity decoding algorithm exponentially decreases with the code length for all code rates below the channel capacity. We also show that obtained lower-bound on the error exponent under the maximum likelihood decoding almost reaches the lower-bound on the error exponent of good linear codes under the maximum likelihood decoding. The error exponents are computed numerically for different code parameters.

International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)Nov 1, 20181 citation

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information TheoryJan 1, 2001157 citations

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)Nov 7, 20027 citations

On Estimation of the Error Exponent for Finite Length Regular Graph-Based LDPC Codes

Pavel S. Rybin, Fedor I. Ivanov

Abstract The error exponent of the regular graph-based binary low-density parity-check (LDPC) codes under the maximum likelihood (ML) decoding algorithm in the binary symmetric channel (BSC) is analyzed. Unlike most other papers where error exponents are considered for the case when the length of LDPC codes tends to infinity (asymptotic analysis), the finite length case (finite length analysis) is considered. In this paper, a method of deriving the lower bound on the error exponent for a regular graph-based LDPC code with finite length under ML decoding is described. Also we analyze Dependences of the error exponent on various LDPC code parameters are also analyzed. The numerical results obtained for the considered lower bound are represented and analyzed at the end of the paper.

Journal of Communications Technology and ElectronicsDec 1, 20181 citation

LP Decoding of Regular LDPC Codes in Memoryless Channels

Nissim Halabi, Guy Even

We study error bounds for linear programming decoding of regular low-density parity-check (LDPC) codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of σ = 0.735 (upper bound of [(Eb)/(N0)]=2.67 dB) on the threshold of (3, 6)-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.

IEEE Transactions on Information TheoryJan 21, 201122 citations

On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes: A New Perspective

Weiyu Xu, Babak Hassibi

Abstract — The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes—expander codes—over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probability p in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding length n while admitting exact ML decoding in average-case polynomial time.As p approaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization.In this process, we propose an efficient O(n 2) new ML certificate algorithm based on the maxflow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities. I.

Sep 24, 20076 citations