Low-density Parity-check codes
An Introduction to LDPC Codes
This FAQ is meant to provide an informal introduction to the field of LDPC codes. It is written by Jeremy Thorpe (henceforth "I" or "me") who is currently a 4th year grad-student at Caltech doing research in the design of LDPC codes at Caltech and JPL.
What Is an LDPC Code?
An LDPC code is a linear error-correcting code that has an parity check matrix H with a small number of nonzero elements in each row and column. Although LDPC codes can be defined over any finite field, the majority of research is focused on LDPC codes over GF(2), in which "1" is the only nonzero element. The code is the set of vectors x such that Hx' = 0.
How can LDPC codes be encoded?
Since LDPC codes are linear codes, they can be encoded in the following way. Given a particular parity-check matrix, rearrange by Gauss-elimination so that H = [I_r|h], that is, so that H begins with an r by r identity matrix. (If H is singular, first remove redundant rows until it is non-singular.) A message m, of length k = n - r can be encoded as x = m[h'|I_(n - r)]'.
Many specific constructions can be encoded in time approximately or exactly linear in the code size. For example, Repeat-Accumulate (RA) or serial-repeat-accumulate codes have an explicit linear-time encoding method.
How are LDPC codes usually decoded?
LDPC codes are often decoded using some type of iterative iterative message-passing decoding algorithm such as Belief Propagation (BP). Many other message-passing algorithms can be viewed as approximations to BP.
What is an ensemble of LDPC codes?
An ensemble of LDPC codes is a randomized construction for an LDPC code of arbitrarily large size and particular rate. The analytical advantage of code ensembles over particular constructions is that often the "ensemble average" performance (under particular decoding methods) can be precisely calculated. For example, the technique known as density evolution (DE) can be used to determine the asymptotic bit-error probability of certain ensembles of LDPC codes under any of a certain class of decoding algorithm that includes BP.
What Types of Ensembles of LDPC codes have been studied?
Regular Ensembles -- A regular ensemble is characterized by the number of nonzero elements in each row, and the number in each column.
Irregular Ensembles (unstructured) -- An unstructured irregular ensemble can be characterized by polynomials λ(x) and ρ(x), which determine the variable and check degree distributions. The code graph is a random graph having this degree distribution.
Base Matrix/Protograph Ensembles -- Protograph ensembles are characterized by a protograph. The code graph is a random "lift" or "finite cover" of the protograph.
Multi-Edge-Type Ensembles (Richardson Ensemles) -- Multi-Edge-Type ensembles are characterized by a certain table. They are a generalization of both unstructured irregular and protograph ensembles. Unstructured irregular ensembles are MET ensembles with a single type. Protograph ensembles are MET ensembles in which every edge in the protograph is its own type.
What is Density Evolution?
Density Evolution (DE) is a technique to analyze the performance of BP decoding of a certain ensemble of LDPC code transmitted over a particular (static, memoryless, symmetric) channel. DE computes, at each iteration starting with 0, the message distribution along each class of edge relative to the value of the variable associated with each edge.
For given channel, DE can determine whether the bit error probability approaches 0 as block length and number of iterations goes to infinity.
What is the Density Evolution threshold?
The DE threshold is the value of a channel parameter p* such that message-passing decoding of a particular ensemble has error-probability tending towards 0 for all channels with fidelity higher than p* and bounded away from 0 for all channels with fidelity lower than p*.
How is performace of LDPC codes measured?
Given a specific channel, the performance of LDPC codes is measured in terms of either bit-error probability or block-error probability. From a practical perspective, block-error probability is a more useful measure although, perhaps for historical reasons, bit error probability is widely quoted.
Often, the error probability is plotted on a log scale against a parameter that specifies one of a class of channels ranging from low-fidelity to high-fidelity. For example, error probability is often plotted against the SNR of an Additive White Gaussian Noise (AWGN) channel, or against the probility of crossover on a Binary Symmetric Channel (BSC) or probability of erasure on an erasure channel.
What is an error floor?
An error floor is a region in which the error probability does not approach 0 as fast as it might be expected to. For example, if error probability is plotted on a log scale against the SNR of an AWGN channel, an error floor might be defined as a region where the slope has decreased relative to the slope at lower SNR.
Do LDPC Codes exhibit error floors?
Many LDPC codes, especially those that have been designed to perform very close to channel capacity, do exhibit error floors.
What causes Error Floors in LDPC codes?
Error floors in LDPC codes can be caused low-weight codewords. For the erasure channel, BP decoding will be successful if and only if the set of channel erasures does not contain a stopping set, which is a set of the code symbols such that every row has either 0 or at least 2 nonzero elements in the set. It is conjectured that stopping sets are a source of error floors even in codes that do not have.