The confidence in the reliability of a codeword output by some (not necessarily optimal) decoding algorithm is discussed. A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced to address this issue as follows. First, the channel output vector is decoded by some symmetric decoder D, e.g., belief propagation or min-sum algorithm decoding. Second, the channel output vector is decoded by LP decoding. Third, if the decoding result of D is a codeword, its LP value is compared to the LP value of the LP decoding result (the latter need not be a codeword). If these two values are close, the AMLC holds. Using upper bounding techniques, we show that the conditional frame error probability given that the AMLC holds, is with some degree of confidence below a threshold. In channels with low noise, this threshold is orders of magnitude lower than the simulated frame error rate, and our bound holds with a very high degree of confidence. This is in stark contrast with standard Monte Carlo simulation, which would require excessively long runs to demonstrate like performance. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

A method which obtains a tight lower bound on the fractional distance of LDPC codes is proposed. This algorithm exhibits complexity which scales quadratically with the block length, and thus less than currently-known methods. We also show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced. When the belief propagation decoder outputs a codeword, this property is satisfied if this codeword is close to the LP solution. Using upper bounding techniques, it is demonstrated that the conditional frame error probability given that the AMLC holds is, with some degree of confidence, below a threshold. In channels with low noise, this threshold is several orders of magnitude lower than the simulated frame error rate, and our bound holds with very high degree of confidence. In contrast, showing this error performance by simulation would require very long Monte Carlo runs. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.

The error performance of the ensemble of typical low-definition parity-check (LDPC ) codes transmitted over the binary erasure channel (BEC) is analyzed. In the past, lower bounds on the error exponents were derived. In this paper, a probabilistic upper bound on this error exponent is derived. This bound holds with some confidence level.

The transmission of coded communication systems is widely modeled to take place over a set of parallel channels. This model is used for transmission over block-fading channels, rate-compatible puncturing of turbo-like codes, multicarrier signaling, multilevel coding, etc. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived in the parallel-channel setting. We focus on the generalization of the Gallager-type bounds and discuss the connections between some versions of these bounds. The tightness of these bounds for parallel channels is exemplified for structured ensembles of turbo codes, repeat-accumulate (RA) codes, and some of their recent variations (e.g., punctured accumulate-repeat-accumulate codes). The bounds on the decoding error probability of an ML decoder are compared to computer simulations of iterative decoding. The new bounds show a remarkable improvement over the union bound and some other previously reported bounds for independent parallel channels. This improvement is exemplified for relatively short block lengths, and it is pronounced when the block length is increased. In the asymptotic case, where we let the block length tend to infinity, inner bounds on the attainable channel regions of modern coding techniques under ML decoding are obtained, based solely on the asymptotic growth rates of the average distance spectra of these code ensembles.