Gallager Codes --- Recent Results
David J C MacKay
In 1948, Claude Shannon posed and solved one of the
fundamental problems of information theory. The question was
whether it is possible to communicate reliably over noisy channels,
and, if so, at what rate.
He defined a theoretical limit, now known as the Shannon limit,
up to which communication is possible, and beyond which communication
is not possible.
Since 1948, coding theorists have attempted to design
error-correcting codes capable of getting close to the Shannon limit.
In the last decade remarkable progress has been made
using codes that are defined in terms
of sparse random graphs, and which are decoded by a simple
probability-based message-passing algorithm.
This paper reviews \ldpc\ codes (Gallager codes),
repeat-accumulate codes, and turbo codes, emphasising
recent
advances.
Some previously unpublished results are then presented,
describing (a) experiments on Gallager codes
with small blocklengths; (b) a stopping rule for
decoding of repeat-accumulate codes, which saves
computer time and allows
block decoding errors to be detected and flagged; and (c)
the empirical power-laws obeyed
by decoding times of sparse graph codes.
postscript (Cambridge UK).
postscript (Canada mirror).
David MacKay's:
home page,
publications.
bibtex file.
Canadian mirrors:
home page,
publications.
bibtex file.