New non-asymptotic random coding theorems (with error probability ϵ and finite block length n) based on Gallager parity check ensemble are established for binary input arbitrary output channels. The resulting non-asymptotic achievability bounds, when combined with non-asymptotic equipartition properties, can be easily computed. Analytically, these non-asymptotic achievability bounds are shown to be asymptotically tight up to the second order of the coding rate as n goes to infinity with either constant or sub-exponentially decreasing ϵ. Numerically, they are also compared favourably, for finite n and ϵ of practical interest, with existing non-asymptotic achievability bounds in the literature in general.
New non-asymptotic random coding theorems (with error probability ϵ and finite block length n) based on Gallager parity check ensemble are established for binary input arbitrary output channels. The resulting non-asymptotic achievability bounds, when combined with non-asymptotic equipartition properties, can be easily computed. Analytically, these non-asymptotic achievability bounds are shown to be asymptotically tight up to the second order of the coding rate as n goes to infinity with either constant or sub-exponentially decreasing ϵ. Numerically, they are also compared favourably, for finite n and ϵ of practical interest, with existing non-asymptotic achievability bounds in the literature in general.
This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.
Asymptotic iterative decoding performance is analyzed for several classes of iteratively decodable codes when the block length of the codes N and the number of iterations I go to infinity. Three classes of codes are considered. These are Gallager's regular low-density parity-check (LDPC) codes, Tanner's generalized LDPC (GLDPC) codes, and the turbo codes due to Berrou et al. It is proved that there exist codes in these classes and iterative decoding algorithms for these codes for which not only the bit error probability P/sub b/, but also the block (frame) error probability P/sub B/, goes to zero as N and I go to infinity.
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.
A variety of communication scenarios can be modeled by a set of parallel channels. Upper bounds on the achievable rates under maximum-likelihood (ML) decoding, and lower bounds on the decoding complexity per iteration of ensembles of low-density parity-check (LDPC) codes are presented. The communication of these codes is assumed to take place over statistically independent parallel channels where the component channels are memoryless, binary-input, and output-symmetric. The bounds are applied to ensembles of punctured LDPC codes where the puncturing patterns are either random or possess some structure. Our discussion is concluded by a diagram showing interconnections between the new theorems and some previously reported results.