Low-density parity-check code

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In information theory, 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; but in 1996 they were rediscovered.[3] Turbo codes, discovered in 1993, became the coding scheme of choice in the late 1990s, used for applications such as deep-space satellite communications. However, in the last few years, the advances in low density parity check codes have developed them past turbo codes, and LDPC is the most efficient scheme discovered as of 2009. LDPC is finding use in practical applications such as 10GBase-T ethernet, which sends data at 10 gigabits per second over noisy CAT6 cables.

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 error correcting code in the new DVB-S2 standard for the satellite transmission of digital television.[4] In 2008, LDPC beat Convolutional Turbo Codes as the FEC scheme for the ITU-T G.hn standard[5]. G.hn chose LDPC over Turbo Codes because of its lower decoding complexity (especially when operating at data rates close to 1 Gbit/s) and because the proposed Turbo Codes exhibited a significant error floor at the desired range of operation.

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

[edit] Function

LDPC codes are defined by a sparse parity-check matrix. This sparse matrix is often randomly generated, subject to the sparsity constraints. These codes were first designed by Gallager in 1962.

Below is a graph fragment of an example LDPC code using Forney's factor graph notation. In this graph, n variable nodes in the top of the graph are connected to (n–k) constraint nodes in the bottom of the graph. This is a popular way of graphically representing an (n, k) LDPC code. The bits of a valid message, when placed on the T's at the top of the graph, satisfy the graphical constraints. Specifically, all lines connecting to a variable node (box with an '=' sign) have the same value, and all values connecting to a factor node (box with a '+' sign) must sum, modulo two, to zero (in other words, they must sum to an even number).

By ignoring any lines going out of the picture, there are 8 possible 6 bit strings corresponding to valid codewords: (i.e., 000000, 011001, 110010, 101011, 111100, 100101, 001110, 010111). This LDPC code fragment represents a 3-bit message encoded as 6 bits. Redundancy is used here to increase the chance in recovering from channel errors. This is a (6,3) linear code with n = 6 and k = 3.

Once again, ignoring lines going out of the picture, the parity-check matrix representing this graph fragment is

\mathbf{H} = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ \end{pmatrix}.

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.

In this example, the 8 codewords can be obtained by putting the parity-check matrix H into this form \begin{bmatrix} -P^T | I_{n-k} \end{bmatrix} through basic row operations:

\mathbf{H} = \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 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix}.

From this, the generator matrix G can be obtained as \begin{bmatrix} I_k | P \end{bmatrix} (noting that in the special case of this being a binary code P = − P), or specifically:

\mathbf{G} = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ \end{pmatrix}.

Finally, by multiplying all 8 possible 3 bit strings by G, all 8 valid codewords are obtained. For example the codeword for the bitstring '101' is obtained by:

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

[edit] Decoding

 This section is in need of attention from an expert on the subject. WikiProject Telecommunications may be able to help recruit one. (November 2008)

Optimally decoding an LDPC code is an NP-complete problem, but suboptimal techniques based on belief propagation are used in practice and lead to good approximations.

For example, consider that the valid codeword, 101011, from the example above is transmitted across a binary erasure channel and received with the 1st and 4th bit erased to yield ?01?11. Since the transmitted message must have satisfied the code constraints, the message can be represented by writing the received message on the top of the factor graph as shown below.

Belief propagation is particularly simple for the binary erasure channel and consists of iterative constraint satisfaction. In this case, the first step of belief propagation is to realize that the 4th bit must be 0 to satisfy the middle constraint. This means that the 1st bit must be a 1 to satisfy the leftmost constraint.

Thus the message can be decoded iteratively. For other channel models, the messages passed between the variable nodes and check nodes are real numbers which express probabilities and likelihoods of belief.

This result can be validated by multiplying the corrected codeword r by the parity-check matrix H:

\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}.

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

[edit] Updating Node Information

In recent years, there has also been a great deal of work in studying the effects of alternative schedules for variable and constraint node update. The original technique that was used for decoding LDPC codes was known as flooding. This type of updates required that before updating a variable node, all constraint nodes needed to be updated and vice-versa. In later work by Vila Casado et al. [6], alternative update techniques are studied in which variable nodes are updated with the newest available check-node information.

The intuition behind these algorithms is that variable nodes whose value varies the most, are the ones that need to be updated first. Updating the value of highly reliable nodes whose Log-likelihood ratio (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency of other nodes whose sign and magnitude fluctuate. These scheduling algorithms show great speed of convergence and lower-error floors than when the flooding is used. These lower error floors are achieved due to the ability of the Informed Dynamic Scheduling (IDS) [6] algorithm to overcome trapping sets or near codewords [7].

When non-flooding scheduling algorithms are used, an alternative definition of iteration is used. For an (n,k) LDPC code of rate k/n, a full iteration occurs when n variable and n-k constraint nodes have been updated, no matter the order in which they were.

[edit] Code construction

For large block sizes, LDPC codes are commonly constructed by first studying the behaviour of decoders. As the block-size tends to infinity, LDPC decoders can be shown to have a noise threshold below which decoding is reliably achieved, and above which decoding is not achieved.[8] This threshold can be optimised by finding the best proportion of arcs from check nodes and arcs from variable nodes. An approximate graphical approach to visualising this threshold is an EXIT chart.

The construction of a specific LDPC code after this optimisation falls into two main types of techniques:

  • Pseudo-random techniques
  • Combinatorial approaches

Construction by a pseudo-random approach builds on theoretical results that, for large block-size, a random construction gives good decoding performance.[3] In general, pseudo-random codes have complex encoders, however pseudo-random codes with the best decoders also can have simple encoders.[9] Various constraints are often applied to help the good properties expected at the theoretical limit of infinite block size to occur at a finite block size.

Combinatorial approaches can be used to optimise properties of small block-size LDPC codes or create codes with simple encoders.

One more way of constructing LDPC codes is to use finite geometries. This method was proposed by Y. Kou et al. in 2001.[10]

[edit] See also

[edit] People

[edit] Theory

[edit] Applications

  • DVB-S2 (Digital video broadcasting)
  • WiMAX (IEEE 802.16e standard for microwave communications)
  • 10GBase-T Ethernet (802.3an)
  • G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable)

[edit] 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. ^ a b David J.C. MacKay and Radford M. Neal, Near Shannon Limit Performance of Low Density Parity Check Codes, Electronics Letters, July 1996
  4. ^ Presentation by Hughes Systems
  5. ^ HomePNA Blog: G.hn, a PHY For All Seasons
  6. ^ a b A.I. Vila Casado, M. Griot, and R.Wesel, “Informed scheduling for belief propagation decoding of LDPC codes,” Proc. IEEE Int. Conf. on Comm. (ICC), June 2007.
  7. ^ T. Richardson, “Error floors of LDPC codes,” in Proc. 41st Allerton Conf. Comm., Control and Comput. ,Monticello,IL, 2003.
  8. ^ Thomas J. Richardson and M. Amin Shokrollahi and Rüdiger L. Urbanke Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes, IEEE Transactions in Information Theory, 47(2), February 2001
  9. ^ Thomas J. Richardson and Rüdiger L. Urbanke, Efficient Encoding of Low-Density Parity-Check Codes, IEEE Transactions in Information Theory, 47(2), February 2001
  10. ^ Y. Kou, S. Lin and M. Fossorier, “Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results”, IEEE Transactions on Information Theory, vol. 47, no. 7, Nov. 2001, pp. 2711- 2736.

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Low-density_parity-check_code"
Personal tools