A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed numberj \geq 3of l's and each row contains a small fixed numberk > jof l's. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixedj. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixedj. A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length. Forj > 3and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound.
A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed numberj \geq 3of l's and each row contains a small fixed numberk > jof l's. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixedj. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixedj. A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length. Forj > 3and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound.
This is a complete presentation of all important theoretical and experimental work done on low-density codes. Low-density coding is one of the three techniques thus far developed for efficient communication over noisy channels with an arbitrarily low probability of error. A principal result of information theory is that if properly coded information is transmitted over a noisy channel at a rate below channel capacity, the probability of error can be made to approach zero exponentially with the code length. Any practical use of this theorem, however, requires a coding scheme in which the cost of storage and computation equipment grows slowly with code length. The present book analyzes a class of coding schemes for which costs grow approximately linearly with code length. It demonstrates that error probability approaches zero exponentially with a root of the block length and cites experimental evidence that this coding scheme has profitable aplicability in many communications situations.
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.
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.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.
We introduce fair-density parity-check (FDPC) codes targeting high-rate applications. In particular, we start with a base parity-check matrixHbof dimension2n×n, wherenis the code block length, and the number of ones in each row and column ofHbis equal tonand 2, respectively. We propose a deterministic combinatorial method for picking the base matrixHb, assumingn=4t2for some integert⩾2. We then extend this by obtaining permuted versions ofHb(e.g., via random permutations of its columns) and stacking them on top of each other leading to codes of dimensionk⩾n−2sn+s, for somes⩾2, referred to as order-s FDPC codes. We propose methods to explicitly characterize and bound the weight distribution of the new codes and utilize them to derive union-type approximate upper bounds on their error probability under Maximum Likelihood (ML) decoding. For the binary erasure channel (BEC), we demonstrate that the approximate ML bound of FDPC codes closely follows the random coding upper bound (RCU) for a wide range of channel parameters. Also, remarkably, FDPC codes, under the low-complexity min-sum decoder, improve upon 5G-LDPC codes for transmission over the binary-input additive white Gaussian noise (B-AWGN) channel by almost 0.5dB (forn=1024, and rate = 0.878). Furthermore, we propose a new decoder as a combination of weighted min-sum message-passing (MP) decoding algorithm together with a new progressive list (PL) decoding component, referred to as the MP-PL decoder, to further boost the performance of FDPC codes. This paper opens new avenues for a fresh investigation of new code constructions and decoding algorithms in high-rate regimes suitable for ultra-high throughput (high-frequency/optical) applications.
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.