Sequential Decoding Algorithm Producing the Maximum-Likelihood Estimate for Low-Density Gallager Codes

A sequential decoding algorithm is proposed for low-density block codes introduced by Gallager [Low-Density Parity-Check Codes, MIT Press, Cambridge (1963)]. If the low-density code is used for transmission of information in a binary symmetric channel, the proposed algorithm produces a maximum-likelihood estimate of the transmitted codewords. The characteristics of the algorithm are reported for a block code of length 20 and minimum distance 6. An asymptotic upper bound is obtained on the average number of decoder computations over the code ensemble.