The previous chapter examined code properties responsible for the floor region (high-SNR region) of LDPC and turbo codes. Specifically, the emphasis was on the computation of various weight enumerators for LDPC and turbo code ensembles because a poor weight spectrum leads to poor performance in a code's floor region both for iterative decoders and for maximum-likelihood decoders. That chapter also introduced ensemble enumerators for trapping sets and stopping sets, both of which can lead to poor floor performance in iterative decoders. In this chapter we examine the iterative decoding performance of LDPC and turbo code ensembles in the complementary low-SNR region, the “waterfall” region. We show that the iterative decoding of long LDPC and turbo codes displays a threshold effect in which communication is reliable beyond this threshold and unreliable below it. The threshold is a function of code ensemble properties and the tools introduced in this chapter allow the designer to predict the decoding threshold and its gap from Shannon's limit. The ensemble properties for LDPC codes are the degree distributions which are typically the design targets for the code-design techniques presented in subsequent chapters. The ensemble properties for turbo codes are the selected constituent codes. Our development borrows heavily from the references listed at the end of the chapter and our focus is on the binary-input AWGN channel. The references and the problems consider other channels. Density Evolution for Regular LDPC Codes We first summarize the main results of [1] with regard to iterative (message passing) decoding of long, regular LDPC codes.
The previous chapter examined code properties responsible for the floor region (high-SNR region) of LDPC and turbo codes. Specifically, the emphasis was on the computation of various weight enumerators for LDPC and turbo code ensembles because a poor weight spectrum leads to poor performance in a code's floor region both for iterative decoders and for maximum-likelihood decoders. That chapter also introduced ensemble enumerators for trapping sets and stopping sets, both of which can lead to poor floor performance in iterative decoders. In this chapter we examine the iterative decoding performance of LDPC and turbo code ensembles in the complementary low-SNR region, the “waterfall” region. We show that the iterative decoding of long LDPC and turbo codes displays a threshold effect in which communication is reliable beyond this threshold and unreliable below it. The threshold is a function of code ensemble properties and the tools introduced in this chapter allow the designer to predict the decoding threshold and its gap from Shannon's limit. The ensemble properties for LDPC codes are the degree distributions which are typically the design targets for the code-design techniques presented in subsequent chapters. The ensemble properties for turbo codes are the selected constituent codes. Our development borrows heavily from the references listed at the end of the chapter and our focus is on the binary-input AWGN channel. The references and the problems consider other channels. Density Evolution for Regular LDPC Codes We first summarize the main results of [1] with regard to iterative (message passing) decoding of long, regular LDPC codes.
The field of error correcting codes was revolutionized by the introduction of turbo codes [7] in 1993. These codes demonstrated dramatic performance improvements over any previously known codes, with significantly lower complexity. Since then, much progress has been made towards understanding the performance of these codes, as well as in using this understanding to design even better codes.
This thesis takes a few more steps in both these directions. We develop a new technique, called the typical set bound, for analyzing the asymptotic performance of code ensembles based on their weight enumerators. This technique yields very tight bounds on the maximum-likelihood decoding threshold of code ensembles, and is powerful enough to reproduce Shannon's noisy coding theorem for the class of binary-input symmetric channels.
We also introduce a new class of codes called irregular repeat-accumulate~(IRA) codes, which are adapted from the previously known class of repeat-accumulate~(RA) codes. These codes are competitive in terms of decoding performance with the class of irregular low-density parity-check~(LDPC) codes, which are arguably the best class of codes known today, at least for long block lengths. In addition, IRA codes have a significant advantage over irregular LDPC codes in terms of encoding complexity.
We also derive an analytical bound regarding iterative decoding thresholds of code ensembles on general binary-input symmetric channels, an area in which theoretical results are currently lacking
Low-density parity-check (LDPC) codes in conjunction with iterative decoding based on message-passing algorithms have been shown to achieve excellent performance over a variety of communication channels. In this dissertation, we investigate LDPC codes under two scenarios which present different challenges for providing robust communications. First, LDPC codes are analyzed and designed for time-selective, frequency-nonselective complex-fading channels where both the amplitude and the phase of the transmitted signal are altered by the channel. To combat the fading, we use a pilot symbol-assisted scheme where known pilot symbols are added to the LDPC code and used to help estimate the channel at the receiver. Using asymptotic, infinite-length analysis, we investigate several iterative, message-passing, joint-estimation-and-decoding strategies; optimal energy distribution between pilot and data symbols; and LDPC code design. Several interesting results are obtained regarding unification of analysis and code design. Next, we address the issue of achieving very low error rates with practical, finite-length LDPC codes for binary erasure channels. Finite-length LDPC codes suffer from error floors which limit the achievable error rate, and this error-floor performance is determined by stopping sets. Asymptotic analysis of weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with lower error floors but does not reflect the behavior of sublinearly-sized stopping sets, which can dominate the iterative-decoding, error-floor performance. Thus, we provide a perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, advantages of protograph structure, and effects of precoding. We show for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly-growing stopping sets, and this polynomial relationship can be approximately captured by a single parameter. Further, we begin to address the question, Given finite stopping-set sizes and finite codelengths, do the stopping sets follow the behavior predicted by linear or sublinear analysis?
The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)
Channel coding is a key component of artificial communication systems, allowing reliable communication using unreliable channels. In the last decade, iteratively decoded channel codes have become or clearly will become standards in a wide range of applications where large amounts of information must be communicated using unreliable media. Of the class of iteratively decoded codes, Low-density parity check (LDPC) codes are arguably the simplest class to describe, and indeed were described more than four decades ago in 1963 by Robert Gallager. The current understanding of LDPC codes has progressed in several significant ways beyond what had been expressed by 1963 by Gallager. Importantly, irregular LDPC codes, whose parity check matrices do not have constant row and column sums, have been shown to significantly outperform their regular counterparts explicitly considered by Gallager. By 1999, researchers had defined a class of irregular ensembles, each characterized by a pair of polynomials. Along with this new class of ensemble, they defined an analytical technique, density evolution, that accurately predicted the channel coding performance of a typical code under iterative message-passing decoding. The pair of polynomials could be effectively be designed by optimizing the coefficients of the polynomial for density evolution threshold threshold. This thesis concerns a different class of ensembles, namely protograph ensembles. Protograph ensembles are characterized by a template graph called, intuitively, a protograph. The Tanner-graph representation of a code in the ensemble is a random lift of the protograph. Protograph-based codes have significant advantages over unstructured irregular codes in regard to implementation of their encoders and decoders. In the decoder, this structure can be used in at least two distinct ways to organize the computations defined by any message-passing algorithm. If, in addition to the protograph structure, circulant structure is imposed on each "section" of the matrix then a quasi-cyclic code results, bestowing even mores advantages, especially in the possible implementation of the encoder. A central difficulty in using protograph ensembles is finding a suitable protograph. Since graphs are discrete objects, there is no obvious correspondence to any optimization model using vectors of real numbers. Instead, the technique of simulated annealing has been applied with a remarkable degree of success. For example, on the AWGN channel, given a constraint on the node degrees, protograph ensembles can be found that achieve a threshold only half as far (measured in dB) from the Shannon limit as unstructured irregular ensembles. This simultaneously illustrates an inherent performance advantage of protograph codes over unstructured codes as well as the efficacy of simulated annealing as an optimization technique. A persistent problem which appears to be common in all codes optimized for density evolution threshold is that of error floors. On a superficial level, this is explained by the maxim that "There's no such thing as a free lunch." In some contexts, such as in codes designed for the erasure channel, the phenomenon can be explained on a much deeper level, though it is not clear why the phenomenon should persist so universally. Still, even without a detailed understanding the cause of this problem, there are techniques that can mitigate error floors. An important tool toward this end is weight enumerators, which are discussed in chapter 3. Codeword and stopping set enumerators can be efficiently computed if a certain (non-concave) function can be efficiently maximized. Protographs that are selected on the basis of their enumerators have shown some success in reducing error floors.
Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.
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.