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

Algorithmic Results in List Decoding

  • Venkatesan Guruswami 1

[1]Venkatesan Guruswami, Department of Computer Science & Engineering, University of Washington, USA, venkat@cs.washington.edu

Short description

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

Keywords

Subscribers Download

(non-subscribers see Book Details tab if available)

Table of contents

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

Foundations and Trends® in Theoretical Computer Science

(Vol 2, Issue 2, 2006, pp 107-195)

DOI: 10.1561/0400000007

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

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
Cover image for Algorithmic Results in List Decoding

Algorithmic Results in List Decoding

112 pages

DOI: 10.1561/9781601980052

E-ISBN: 978-1-60198-005-2

ISBN: 978-1-60198-004-5

Description

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.