- List-decoding
In computer science, particularly in coding theory, list decoding is an alternative to unique decoding of
error correcting codes for large error rates. The notion was proposed by Elias in the 1950's. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.Mathematical formulation
Let mathcal{C} be a n,k,d)_{q} error-correcting code; in other words, mathcal{C} is a code of length n, dimension k and minimum distance d over an alphabet Sigma of size q. The list decoding problem can now be formulated as follows:
Input: Received word x in Sigma^{n}, error bound e
Output: A list of all codewords x_{1},x_{2},ldots,x_{m} in mathcal{C} whose hamming distance from x is at most e.
Applications
Algorithms for list decoding of various codes have played a central role in a variety of results in complexity theory. Some important applications are construction of
Hardcore Predicates fromone-way permutations , amplifying hardness of boolean functions, construction of extractors.External links
* [http://theory.lcs.mit.edu/%7Emadhu/papers/ifip-journ.ps A Survey by Madhu Sudan on list decoding]
* [http://people.csail.mit.edu/madhu/FT01/ Notes from a course taught by Madhu Sudan]
* [http://www.cs.berkeley.edu/~luca/cs294/ Notes from a course taught by Luca Trevisan]
Wikimedia Foundation. 2010.