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 ).
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).
- = Code word length
- = Number of information points
- = Code rate
Definition of terms
- or source code word (info word)
- redundant part of the channel code word
- Channel codeword
- Reception sequence
- 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 ".
The aim is to find a sequence to be sent that satisfies the equation .
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:
- Be and
- The following should apply:
- This can be transformed:
- This results in
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.
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.
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 .
- Robert G. Gallager: Low-Density Parity-Check Codes . MIT Press Classic Series, Cambridge MA, 1963 ( MIT Press research monographs 21, 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 ).
- Robert G. Gallager: Low-Density Parity-Check Codes . ( Memento of the original from May 23, 2005 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 1.1 MB) in IRE Transactions on Information Theory , pages 21 to 28, 1962
- Robert G. Gallager: Low-Density Parity-Check Codes . - 1963
- Jian Sun: An Introduction to Low Density Parity Check (LDPC) Codes ( Memento from January 13, 2012 in the Internet Archive )
- Alex Balatsoukas-Stimming: The Progressive Edge Growth Algorithm (PDF; 261 kB)
- David MacKay: C - Implementation of the PEG algorithm for LDPC codes
- Design and Implementation of LDPC Codes (PDF; 255 kB)
- Design of LDPC Codes (PDF; 563 kB)
- IEEE: IEEE Standard 802.11n
- IEEE: IEEE Standard 802.16e
- List of standardized LDPC codes with properties and explanations