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 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. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.
Low-density parity-check (LDPC) codes are a class of linear block codes which provide near-capacity performance on a large collection of data transmission and storage channels while simultaneously admitting implementable decoders. LDPC codes were first proposed by Gallager in his 1960 doctoral dissertation [1] and were scarcely considered in the 35 years that followed. One notable exception is the important work of Tanner in 1981 [2] in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called Tanner graphs. The study of LDPC codes was resurrected in the mid1990s with the work of MacKay, Luby, and others [3-5] who noticed, apparently independently of the work of Gallager, the advantages of linear block codes which possess 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.
Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.