Iterative Probabilistic Decoding of a Low Density Parity Check Code

We have rediscovered Gallager's (1962) low density parity check codes and iterative decoding algorithm. We find these codes to perform substantially better than standard textbook codes.

(MacKay and Neal, 1995/6/7)


Demonstration number 2: rate 1/4 code, Gaussian channel

We demonstrate a rate ~1/4 code which encodes K=3296 bits into N=13298 bits.

The source vector is the top 103x32=3296 bits. The transmitted vector consists of these bits and about three times as many parity bits, shown in the lower part of the image.

In this demonstration you see at the far left a received vector corrupted by transmission over a Gaussian channel with s.n.r. (signal amplitude to noise amplitude) equal to 0.84; the dynamic display shows at one second intervals the best guess produced by an iterative probabilistic decoder after each of 16 iterations. At the 16th iteration, the guess violates no parity checks, and the decoder halts. The decoding is free of errors.

For comparison, the Shannon limit for a code of this rate is a s.n.r. of 0.64.

For the Gaussian channel this graph shows the performance of rate-1/4 codes developed by Davey and MacKay that are superior to all known rate-1/4 codes.


Demonstration number 1: rate 1/2 code, binary symmetric channel


Papers and software available on-line | Mirror in North America

1997 course on Information theory, pattern recognition and neural networks


http://www.inference.org.uk/mackay/ | mirror: http://www.cs.toronto.edu/~mackay/
Last modified: Mon Dec 3 09:17:43 2001