Arikah Map

Low-density parity-check code

A low-density parity-check code (LDPC code) is an error correcting code, a method of transmitting a message over a noisy transmission channel[1][2]. While LDPC and other error correcting codes cannot guarantee perfect transmission, the probability of lost information can be made as small as desired. LDPC was the first code to allow data transmission rates close to the theoretical maximum, the Shannon Limit.Impractical to implement when developed in 1963, LDPC codes were forgotten[3]. The next 30 or so years of information theory failed to produce anything one-third as effective and LDPC remains, in theory, the most effective developed to date (2006).

The explosive growth in information technology has produced a corresponding increase of commercial interest in the development of highly efficient data transmission codes as such codes impact everything from signal quality to battery life. Although implementation of LDPC codes has lagged that of other codes, notably the turbo code, the absence of encumbering software patents has made LDPC attractive to some and LDPC codes are positioned to become a standard in the developing market for highly efficient data transmission methods. In 2003 an LDPC code beat six turbo codes to become the new standard for the satellite transmission of digital television.

LDPC codes are also known as Gallager codes, in honor of Robert G. Gallager, who developed the LDPC concept in his doctoral dissertation at MIT in 1960.


Contents

Function

LDPC uses a sparse parity-check matrix, similar to those used for decoding Hamming codes. This sparse matrix is randomly generated, subject to the sparsity constraints. Decoding them is an NP-complete problem, but there are good approximate decoders. These codes were first designed by Gallager in 1962. See sparse graph code.

Below is a graph fragment of an example LDPC code using Forney's factor graph notation. A message is encoded by placing bits on theT's at the top such that the graphical constraints aresatisfied. Specifically, all lines connecting to an <math>=</math>box have the same value, and all values connecting to a<math>+</math> box must sum, modulo two, to zero (in other words, they must sum to an even number).

Low-density parity-check code:Ldpc code fragment factor graph

If we ignoreconstraints for lines going out of the picture, then there are 8possible 6 bit strings which correspond to valid codewords: (i.e.,000000, 011001, 110010, 111100, 101011, 100101, 001110, 010111). Thusthis LDPC code fragment represents a 3-bit message with 6 bits. Thepurpose of this redundancy is to aid in recovering from channel errors.

Again, if we ignore lines going out of the picture, then the parity-check matrix representing this graph fragment is

<math>

\mathbf{H} = \begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0 \\0 & 0 & 1 & 1 & 0 & 1 \\1 & 0 & 0 & 1 & 1 & 0 \\\end{pmatrix}</math>

In this matrix, each row represents one of the three parity-check constraints, whereas each column represents one of the six bits in the received codeword.

Imagine that the 5th message, 101011, is transmitted across a binary erasure channeland received with the 1st and 4th bit erased to yield ?01?11. We knowthat the transmitted message must have satisfied the code constraintswhich we can represent by writing the received message on the top ofthe factor graph as shown below.

Low-density parity-check code:Ldpc code fragment factor graph w erasures

We can now solve for the missing bits using an algorithm which iscommonly referred to as belief propagation. In this case, thefirst step of belief propagation is to realize that the 4th bit mustbe 0 to satisfy the middle constraint.Now that we have decoded the 4th bit, we realize that the 1st bit mustbe a 1 to satisfy the leftmost constraint.

Low-density parity-check code:Ldpc code fragment factor graph w erasures decode step 2

Thus we are able to iteratively decode the message encoded with ourLDPC code.

We can validate this result by multiplying the corrected codeword r by the parity-check matrix H:

<math>\mathbf{z} = \mathbf{Hr}

= \begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0 \\0 & 0 & 1 & 1 & 0 & 1 \\1 & 0 & 0 & 1 & 1 & 0 \\\end{pmatrix}

\begin{pmatrix}1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\\end{pmatrix}

=\begin{pmatrix}0 \\ 0 \\ 0 \\\end{pmatrix}</math>

Because the outcome z of this operation is the 3 x 1 zero vector, we have successfully validated the resulting codeword r.

References

  1. ^ David J.C. MacKay (2003) Information theory, inference and learning algorithms, CUP, ISBN 0-521-64298-1, (also available online)
  2. ^ Todd K. Moon (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, ISBN 0-471-64800-0 (Includes code)
  3. ^ David J.C. MacKay and Radford M. Neal, Near Shannon Limit Performance of Low Density Parity Check Codes, Electronics Letters, July 1996

See also

People

Theory

Applications

Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations.

Categories


Error detection and correction | Information theory

Find

Find

Find