Low-density parity-check code

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]. Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information. In Mathematics, Computer science, Telecommunication, and Information theory, error detection and correction has great practical importance in In Science, and especially in Physics and Telecommunication, noise is fluctuations in and the addition of external factors to the stream of target 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. In Information theory, the Shannon–Hartley theorem is an application of the Noisy channel coding theorem to the archetypal case of a continuous-time analog communications 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 (2007). Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information.

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 Electrical engineering and Digital communications, turbo codes (originally in French Turbocodes) are a class of high-performance error correction Software patent does not have a universally accepted definition 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]. Digital Video Broadcasting - Satellite - Second Generation ( DVB-S2) is an enhanced specification to replace the DVB-S standard developed in 2003 and ratified Digital television (DTV is the sending and receiving of moving images and sound by discrete ( digital) signals in contrast to the analog signals used by

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. Robert G Gallager (born May 29, 1931 in Philadelphia PA) is an American electrical engineer known for his work on Information theory

1 Function
2 Decoding
3 Code construction
4 See also
5 References
6 External links

Function

LDPC codes are defined by a sparse parity-check matrix. In Coding theory, a parity-check matrix of a linear block code C is a Generator matrix of the Dual code. This sparse matrix is often randomly generated, subject to the sparsity constraints. In the mathematical subfield of Numerical analysis a sparse matrix is a matrix populated primarily with zeros In the mathematical subfield of Numerical analysis a sparse matrix is a matrix populated primarily with zeros These codes were first designed by Gallager in 1962. Robert G Gallager (born May 29, 1931 in Philadelphia PA) is an American electrical engineer known for his work on Information theory

Below is a graph fragment of an example LDPC code using Forney's factor graph notation. In Mathematics, a factor graph is an XF- Bipartite graph where X=\{X_1X_2\dotsX_n\} is a set of variables and F=\{f_1f_2\dotsf_m\} 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). In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers

If we ignore constraints for lines going out of the picture, then there are 8 possible 6 bit strings which correspond to valid codewords: (i. e. , 000000, 011001, 110010, 111100, 101011, 100101, 001110, 010111). Thus this LDPC code fragment represents a 3-bit message encoded as 6 bits. The purpose of this redundancy is to aid in recovering from channel errors. This is a (6,3) linear code with $n = 6$ and $k = 3$ . In Mathematics and Information theory, a linear code is an important type of Block code used in Error correction and detection schemes

Again, if we ignore lines going out of the picture, then 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. In Coding theory, a parity-check matrix of a linear block code C is a Generator matrix of the Dual code. In Coding theory, a generator matrix is a basis for a Linear code, generating all its possible codewords 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}.$

Decoding

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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties Belief propagation, also known as the sum-product algorithm, is an iterative Algorithm for computing marginals of functions on a Graphical model

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. A binary erasure channel (or BEC is a common Communications channel model used in Coding theory and Information theory. We know that the transmitted message must have satisfied the code constraints which we can represent 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.

Now that we have decoded the 4th bit, we realize that the 1st bit must be a 1 to satisfy the leftmost constraint.

Thus we are able to iteratively decode the message encoded with our LDPC code. For other channel models, the messages passed between the variable nodes and check nodes are real numbers which express probabilities and likelihoods of belief.

We can validate this result 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, we have successfully validated the resulting codeword r. In Communication theory and Coding theory, decoding is the process of translating received messages into Codewords of a given Code.

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^[5]. 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. An Extrinsic information transfer chart, commonly called an EXIT chart, is a technique to aid the construction of good iteratively-decoded Error-correcting codes

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 ^[6]. 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 code is to use Finite geometry. A finite geometry is any geometric system that has only a finite number of points. This method was proposed by Y. Kou et al. in 2001 ^[7]

References

^ David J.C. MacKay (2003) Information theory, inference and learning algorithms, CUP, ISBN 0-521-64298-1, (also available online)
^ Todd K. Moon (2005) Error Correction Coding, Mathematical Methods and Algorithms. Wiley, ISBN 0-471-64800-0 (Includes code)
^ ^a ^b David J.C. MacKay and Radford M. Neal, Near Shannon Limit Performance of Low Density Parity Check Codes, Electronics Letters, July 1996
^ Presentation by Hughes Systems
^ 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
^ 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
^ 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.

External links

The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, discusses LDPC codes in Chapter 47.
Tutorial on LDPC codes and Gallager's original paper (re-typeset)
LDPC codes and performance results
Online density evolution for LDPC codes
Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations:
- Binary LDPC codes in C
- Binary LDPC codes for Python (core algorithm in C)
- LDPC codes over GF(q) in MATLAB
- LDPC encoder and LDPC decoder in MATLAB
- LDPC at Opencores Open source hardware implementation of LDPC encode/decode in Verilog. MATLAB is a numerical computing environment and Programming language. MATLAB is a numerical computing environment and Programming language. In the Semiconductor and electronic design industry Verilog is a Hardware description language (HDL used to model electronic systems.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Function

Decoding

Code construction

See also

People

Theory

Applications

References

External links