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 1: rate 1/2 code, binary symmetric channel

We demonstrate a rate 1/2 code which encodes K=10000 bits into N=20000 bits.

The source vector is the top 100x100 bits. [Copyright(c)1997 United Feature Syndicate, Inc., used with permission.] The transmitted vector consists of these 10000 bits and an equal number of parity bits, show as the bottom half of the image.

In this demonstration you see a received vector corrupted by transmission over a binary symmetric channel with noise density 7.5%; then at one second intervals the best guess produced by an iterative probabilistic decoder after each of 13 iterations. At the 13th iteration, the guess violates no parity checks, and the decoder halts. The decoding is error-free.

For comparison, the Shannon limit for a code of rate 1/2 is a noise level of about 11%.


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

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.


(c) David J.C. MacKay | Lecture course | Book | Other demonstrations |

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


An mpeg alternative to this animated gif demo can be found here: | 20000,10000 | 13298,3298 |
http://www.inference.phy.cam.ac.uk/mackay/ | mirror: http://www.cs.toronto.edu/~mackay/
Last modified: Wed Mar 10 10:29:57 2004