Brief guide to low density parity check codes

In some sense one might say that this section is about the ``codes of the future''. Low density parity check (LDPC) codes were introduced by R. Gallagher in his 1960 MIT PhD thesis [Ga]. At the time, little attention was paid to them due to their impracticality with the current technolgy. However, Gallagher showed that a large proportion of them have ``good parameters'', i.e., parameters approaching the Shannon limit [MN], [Mac]. Recently, their practicality has improved dramatically and in some cases linear time encoding and decoding algorithms have been established for them [Sp]. There are two ways to define LDPC codes, one using matrices and another using graphs. We shall discuss both.