Information Theory and Coding Theory

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

V. B. Balakirskii


Abstract: 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.

UDC: 621.391.15

Received: 16.05.1989

 English version: Problems of Information Transmission, 1991, 27:1, 40–48

Bibliographic databases:

•