Low-Density-Parity-Check-Code

Low density parity check codes, referred to as LDPC or Gallager codes are linear block codes for error correction. They were developed in 1962 by Robert Gray Gallager in his doctoral thesis at MIT.

Low- density parity - check codes describe using a matrix many contiguous parity checks. It is the principle of a check matrix is applied during this process: wherein the check matrix ( parity check matrix), and the sequence of received code symbols is. H is sparse (hence the term low-density ).

Notation

  • = Codeword length
  • = Number of information points
  • = Code rate

Definition of Terms

  • Or source code word ( word info )
  • Redundant part of the channel codeword
  • Channel codeword
  • Receive sequence
  • Control matrix

Regular and non-regular codes

An LDPC code whose parity check matrix in each row and each column contains the same number of ones ( row and column weight) is called regularly. The line weight needs this is not the size of the columns correspond to the weight.

An LDPC code that does not satisfy this requirement (that is, a code vary in the column or row weight ) is, however, referred to as "irregular".

Coding

It is necessary to provide a sequence to be transmitted which satisfies the equation.

A possible form of encoding works as follows: The channel code word is composed of the data to be transmitted (which are known) and the redundant part. As above formula must meet, must be calculated according to:

  • Be and
  • It should apply:
  • This may be converted:
  • It follows

In words, must correspond to the inverted square - the first - portion of the check matrix H k with the remainder of the check matrix Hl and the data to be sent are multiplied al.

Decoding

This applies also to solve the problem. For this iterative graph - based algorithms are often chosen. After transmission of the channel codeword over a transmission channel, such as an AWGN channel ( additive white Gaussian noise) is, generally, the word consisting of real values ​​, is received. From this an approximate solution is, as a rule, by means of an iterative process calculated. By equation matrix H N are given equations; each of these equations makes it possible to calculate independent information about the included elements. Now the information is re-used in the other equation calculations. It should be noted that the information that was calculated with an equation that must be removed in the next iteration before re- computation.

Construction of LDPC code

LDPC codes are described through your check matrix H. Thus to develop a LDPC code is called to find a suitable control matrix or construct. The need to create codewords generator matrix G can be derived using the Gauss-Jordan method of H. For the generation of control matrices are, inter alia, the following methods, which are based in part on to symbolize the check matrix as Tanner graph and to work on this with the help of various algorithms:

  • Progressive Edge Growth ( PEG)
  • Design by David JC Radford M. Neal and MayKay
  • Random structure of the check matrix

To keep the number of species in the matrix ones to relatively low, even so-called " Row splitting" can - and "Column splitting" algorithms are used.

Practical use of LDPC codes

LDPC codes can be applied in different fields of technology. Usually they are used threaded. So LDPC codes used for example for error-correcting data transmission of DVB -S2 signals. In addition to the newer wireless standards such as IEEE 802.11n ( " n- WLAN" or " Draft-n WLAN" ) implemented the WLAN -like 802.16e ( Wimax ) LDPC codes. Other standards are GMR -1, IEEE 802.3, IEEE 802.22, CMMB, and WiMedia 1.5.

Institute of Electrical and Electronics Engineers GEO-Mobile Radio Interface David J. C. MacKay
359570
de