Overview

In 1962, R. G. Gallager ^[162] introduced a class of error correcting codes called Low-Density Parity-Check (LDPC) codes. These codes have parity check matrices that are sparse, i.e., contain mostly O's and have only a few l's. Although the sparseness of the parity check matrix results in low decoding complexity, still the decoding complexity was high enough to make the implementation of the LDPC codes infeasible until recently. It is interesting to note that the iterative decoding procedure proposed by Gallager ^[162] is practically the same as the message passing schemes used for decoding of the turbo and turbo-like codes today. In spite of all this, apart from a few references ^{[164] [165] [163]} to Gallager's work, overall the subject remained unknown to the information theory community. It was only after the discovery of turbo codes in 1993 ^[6] that interest in Low-Density Parity-Check codes was rekindled and LDPC codes were re-discovered independently by MacKay and Neal ^[167] and Wiberg ^[166]. In the past few years, there has been a considerable amount of research work on LDPC codes ^[168], ^[171], ^[14], ^[176], ^[174], ^[179], ^[178] and ^[180].