In Chapter 4, we introduce low-density parity-check (LDPC) codes, a class of powerful and efficient channel codes which admit a graphical representation based on sparse bipartite graphs. This chapter introduces fundamental concepts in LDPC coding theory and guides the reader through unstructured and structured LDPC code ensembles, including the important case of protograph-based LDPC code ensembles.
In Chapter 4, we introduce low-density parity-check (LDPC) codes, a class of powerful and efficient channel codes which admit a graphical representation based on sparse bipartite graphs. This chapter introduces fundamental concepts in LDPC coding theory and guides the reader through unstructured and structured LDPC code ensembles, including the important case of protograph-based LDPC code ensembles.
Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.
Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
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.
Generalizations of LDPC codes: In Chapter 9, we present code ensembles that may be regarded as special instances, generalization, or modifications of LDPC code ensembles introduced in Chapter 4. This chapter starts with spatially coupled LDPC codes, introduced within a protograph-based framework, then addresses generalized LDPC codes, where some of the CNs impose multiple linear constraints, and finally describes low-density generator matrix codes. Erasure decoding algorithms are described for all code classes.
The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.