Foundations and Trends® in Theoretical Computer Science > Vol 2 > Issue 2

Algorithmic Results in List Decoding

Venkatesan Guruswami, Department of Computer Science & Engineering, University of Washington, USA, venkat@cs.washington.edu
 
Suggested Citation
Venkatesan Guruswami (2007), "Algorithmic Results in List Decoding", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 2, pp 107-195. http://dx.doi.org/10.1561/0400000007

Published: 29 Jan 2007
© 2006 V. Guruswami
 
Subjects
Cryptography and information security
 

Free Preview:

Article Help

Share

Download article
In this article:
Part I General Literature
1 Introduction
2 Definitions and Terminology
3 Combinatorics of List Decoding
4 Decoding Reed–Solomon Codes
5 Graph-Based List-Decodable Codes
Part II Achieving List Decoding Capacity
6 Folded Reed–Solomon Codes
7 Achieving Capacity over Bounded Alphabets
8 Concluding Thoughts
Acknowledgments
References

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."

DOI:10.1561/0400000007
ISBN: 978-1-60198-004-5
112 pp. $75.00
Buy book
 
ISBN: 978-1-60198-005-2
112 pp. $100.00
Buy E-book
Table of contents:
Abstract
1. Introduction
2. Definitions and Terminology
3. Combinatorics of List Decoding
4. Decoding Reed-Solomon Codes
5. Graph-based List-Decodable Codes
6. Folded Reed-Solomon Codes
7. Achieving Capacity over Bounded Alphabets
8. Concluding Thoughts
References

Algorithmic Results in List Decoding

Algorithmic Results in List Decoding 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." The main technical focus is on giving a complete presentation of the recent algebraic results achieving list decoding capacity, while pointers or brief descriptions are provided for other works on list decoding. Algorithmic Results in List Decoding is intended for scholars and graduate students in the fields of theoretical computer science and information theory. The author concludes by posing some interesting open questions and suggests directions for future work.

 
TCS-007