|
|
|
|
Algorithmic Results in List Decoding
Foundations and Trends® in
Theoretical Computer Science
Volume 2 Issue 2
DOI: 10.1561/0400000007
Algorithmic Results in List Decoding
Venkatesan Guruswami
Department of Computer Science & Engineering,
University of Washington, Seattle WA 98195, USA, venkat@cs.washington.edu
Abstract
Error-correcting codes are used to cope with the corruption of data by noise during communication or storage. A code uses
an encoding procedure that judiciously introduces redundancy into the data to produce an associated codeword. The redundancy
built into the codewords enables one to decode the original data even from a somewhat distorted version of the codeword. The
central trade-off in coding theory is the one between the data rate (amount of non-redundant information per bit of codeword)
and the error rate (the fraction of symbols that could be corrupted while still enabling data recovery). The traditional decoding
algorithms did as badly at correcting any error pattern as they would do for the worst possible error pattern. This severely
limited the maximum fraction of errors those algorithms could tolerate. In turn, this was the source of a big hiatus between
the error-correction performance known for probabilistic noise models (pioneered by Shannon) and what was thought to be the
limit for the more powerful, worst-case noise models (suggested by Hamming).
In the last decade or so, there has been much algorithmic progress in coding theory that has bridged this gap (and in fact
nearly eliminated it for codes over large alphabets). These developments rely on an error-recovery model called “list decoding,”
wherein for the pathological error patterns, the decoder is permitted to output a small list of candidates that will include
the original message. This book introduces and motivates the problem of list decoding, and discusses the central algorithmic
results of the subject, culminating with the recent results on achieving “list decoding capacity.”
|
|
|
|
|
|
|
|
|