Low density parity check code

Low-density parity check codes , also known as LDPC or Gallager codes , are linear block codes for error correction . They were developed in 1962 by Robert Gray Gallager as part of his dissertation at MIT .

With the help of a matrix, low-density parity check codes describe many related parity checks . The principle of a control matrix is used: where the control matrix (parity-check matrix) and the sequence of the received code symbols (represented as a line vector) represents. H is only sparsely populated (hence the name low-density ). ${\ displaystyle H \ cdot b ^ {T} = 0}$ ${\ displaystyle H}$ ${\ displaystyle b}$

Long forgotten, they experienced a renaissance when Rüdiger Urbanke and Thomas J. Richardson showed in 2001 that they could operate near the Shannon border and could be efficiently implemented as an irregular LDPC. The irregular LDPC include the tornado codes for erasure coding ( Michael Luby , Michael Mitzenmacher , Daniel A. Spielman , Amin Shokrollahi 2001).

notation

${\ displaystyle (n, l, R) \; {\ text {LDPC}}}$

${\ displaystyle n}$ = Code word length
${\ displaystyle l}$ = Number of information points
${\ displaystyle R}$ = Code rate

Definition of terms

${\ displaystyle a ^ {*}}$ or source code word (info word) ${\ displaystyle a_ {l}}$
${\ displaystyle a_ {k}}$ redundant part of the channel code word
${\ displaystyle a}$ Channel codeword
${\ displaystyle b}$ Reception sequence
${\ displaystyle H}$ Control matrix

Regular and non-regular codes

An LDPC code whose control matrix contains the same number of ones (row and column weight) in each row and column is called regular. The row weight does not have to correspond to the size of the column weight.

An LDPC code that does not meet this requirement (i.e. a code in which column or row weights vary) is referred to as " irregular ".

Coding

The aim is to find a sequence to be sent that satisfies the equation . ${\ displaystyle a}$ ${\ displaystyle H \ cdot a ^ {T} = 0}$

One possible form of coding works as follows: The channel code word is composed of the data to be sent (which are known) and the redundant part . Since the above formula must be met, the following must be calculated accordingly: ${\ displaystyle a}$ ${\ displaystyle a_ {l}}$ ${\ displaystyle a_ {k}}$ ${\ displaystyle a}$ ${\ displaystyle a_ {k}}$

Be and ${\ displaystyle a = [a_ {k}, a_ {l}]}$ ${\ displaystyle H = [H_ {k}, H_ {l}]}$
The following should apply: ${\ displaystyle [H_ {k}, H_ {l}] * [a_ {k}, a_ {l}] ^ {T} = 0}$
This can be transformed: ${\ displaystyle [H_ {k}] [a_ {k}] = [H_ {l}] [a_ {l}]}$
This results in ${\ displaystyle a_ {k} ^ {T} = H_ {k} ^ {- 1} \ cdot H_ {l} \ cdot a_ {l}}$

Expressed in words, the inverted square - the first - part H _{k of} the control matrix must be multiplied by the remaining remainder H _{l of} the control matrix and the data a _{l to} be sent.

Decoding

It is also important to solve the problem. Iterative graph- based algorithms are often chosen for this. After the transmission of the channel code word over a transmission channel , e.g. B. an AWGN channel (additive white Gaussian noise ), the word , consisting of real values, is usually received. An approximate solution is calculated from these, usually with the help of an iterative procedure. N equations are given by the equation matrix H; each of these equations allows independent information on the elements contained to be calculated. Now this information is reused in the other equation calculations. It should be noted that the information that was calculated using an equation must be removed in the next iteration before the new calculation. ${\ displaystyle H \ cdot b ^ {T} = 0}$ ${\ displaystyle a}$ ${\ displaystyle b_ {M}}$

Construction of LDPC codes

LDPC codes are described by their control matrix H. Developing an LDPC code means finding or constructing a suitable control matrix. The generator matrix G required to create code words can be derived from H with the aid of the Gauss-Jordan method . To generate control matrices are u. a. the following procedures, which are partly based on symbolizing the control matrix as a Tanner graph and processing it with the aid of various algorithms:

Progressive Edge Growth (PEG)
Construction according to David JC MacKay and Radford M. Neal
Random construction of the control matrix

In order to keep the number of ones occurring in the matrix relatively low, so-called “row splitting” and “column splitting” algorithms can also be used.

Practical use of LDPC codes

LDPC codes are used in different areas of technology. As a rule, they are used in a chain . LDPC codes are used, for example, for error-correcting data transmission of digital television signals according to DVB-S2 and for Digital Terrestrial Multimedia Broadcast (DTMB). In addition to newer WLAN standards such as IEEE 802.11n (“n-WLAN” or “n-Draft WLAN”), the WLAN-like standard 802.16e ( Wimax ) also implements LDPC codes. Further standards are GMR-1 , IEEE 802.3an , IEEE 802.22 , CMMB , and WiMedia 1.5 .

literature

Robert G. Gallager: Low-Density Parity-Check Codes . MIT Press Classic Series, Cambridge MA, 1963 ( MIT Press research monographs 21, ZDB -ID 597839-7 ), ( different version ; PDF; 655 kB).
David JC MacKay : Information theory, inference and learning algorithms . Cambridge University Press, Cambridge et al. 2003, ISBN 0-521-64298-1 (also available online ).
Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms . Wiley-Interscience, Hoboken NJ, 2005, ISBN 0-471-64800-0 .
Amin Shokrollahi : LDPC Codes: An Introduction . In: Keqin Feng et al. (Ed.): Coding, cryptography and combinatorics . Birkhäuser, Basel et al. 2004, ISBN 3-7643-2429-5 , pp. 85-112 ( Progress in computer science and applied logic 23), ( PDF ).