LDPC Codes

Overview of LDPC Codes:

LDPC codes or Low-Density Parity-Check Codes are a class of codes where each code is specified by a parity-check matrix with the following properties:
·    Each column contains a small fixed number j>= 3 of 1’s and
·    Each row contains a small fixed number k>j of 1’s.
·    A majority of the entries in the matrix are 0’s

An (n,j,k) low-density code is a code of block length n with a matrix as shown below:

 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

In the above code N=20, j=3, k=4. (Matrix from  “Low-Density Parity-Check Codes”, by R.G. Gallagher.

The encoding procedure is similar to that of any linear code, where the message bits are multiplied by a generator matrix to produce a code word. Each parity check matrix has a generator matrix associated with it and if one is given, the other can be easily determined.

Decoding:
There are two basic decoding schemes for the LDPC codes.
In the first scheme, the decoder computes all parity checks and then changes any digit that is contained in more than some   fixed number of unsatisfied parity- check equations. Using these new values, the parity checks are recomputed, and the process is repeated until the parity checks are all satisfied.
In the second scheme an algorithm known as the “sum-product” algorithm is used which is similar to the “belief-propagation algorithm” used in networks.
Information about each bit of the codeword derived from the received data is expressed as a probability ratio, the probability of the bit being 1 divided by the probability of the bit being 0. The probability ratios will be adjusted to take account of information obtained from other bits along with the requirement that the parity checks be satisfied.
The algorithm alternates between recalculating the probability ratios for each check.