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.
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.
Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.
Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.
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
The growing popularity of a class of linear block codes called the low-density parity-check (LDPC) codes can be attributed to the low complexity of the iterative decoders, and their potential to achieve performance very close to the Shannon capacity. This makes them an attractive candidate for ECC applications in communication systems. This report proposes methods to systematically construct regular and irregular LDPC codes.A class of regular LDPC codes are constructed from incidence structures in finite geometries like projective geometry and affine geometry. A class of irregular LDPC codes are constructed by systematically splitting blocks of balanced incomplete block designs to achieve desired weight distributions. These codes are decoded iteratively using message-passing algorithms, and the performance of these codes for various channels are presented in this report.The application of iterative decoders is generally limited to a class of codes whose graph representations are free of small cycles. Unfortunately, the large class of conventional algebraic codes, like RS codes, has several four cycles in their graph representations. This report proposes an algorithm that aims to alleviate this drawback by constructing an equivalent graph representation that is free of four cycles. It is theoretically shown that the four-cycle free representation is better suited to iterative erasure decoding than the conventional representation. Also, the new representation is exploited to realize, with limited success, iterative decoding of Reed-Solomon codes over the additive white Gaussian noise channel.Wiberg, Forney, Richardson, Koetter, and Vontobel have made significant contributions in developing theoretical frameworks that facilitate finite length analysis of codes. With an exception of Richardson's, most of the other frameworks are much suited for the analysis of short codes. In this report, we further the understanding of the failures in iterative decoders for the binary symmetric channel. The failures of the decoder are classified into two categories by defining trapping sets and propagating sets. Such a classification leads to a successful estimation of the performance of codes under the Gallager B decoder. Especially, the estimation techniques show great promise in the high signal-to-noise ratio regime where the simulation techniques are less feasible.
Recently, a new class of Low-Density Parity-Check (LDPC) codes constructed from a template was introduced. This kind of codes were called protograph codes. The protograph serves as a blueprint for constructing LDPC codes of arbitrary size whose performance can be predicted by analyzing the protograph. Protograph LDPC codes perform very well and suit for high-speed encoding and decoding. However, there are few researches on expansion and encoding algorithms for them. In this paper, using isomorphism between matrix ring and polynomial ring, we propose efficient quasi-cyclic expansion and encoding algorithms for protograph LDPC codes. Simulation results show that the protograph LDPC codes which were constructed by the algorithm proposed in this paper, outperform the best known unstructured irregular LDPC codes with the same maximum node degrees.
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?