List-decoding

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 from one-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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • List of Americans in the Venona papers — Originally declassified by Senator Daniel Patrick Moynihan, Chairman of the bipartisan Commission on Government Secrecy, the Venona project and its associated documentation, contains codenames of several hundred individuals mentioned in decrypted …   Wikipedia

  • List of films about Muhammad — A series of articles on Prophet of Islam Muhammad Life In Mecca · Hijra · …   Wikipedia

  • List of NOVA episodes — Nova is an American science documentary television series produced by WGBH Boston for PBS. Many of the programs in this list were not originally produced for PBS, but were acquired from other sources such as the BBC.[1] All acquired programs are… …   Wikipedia

  • List of Code Lyoko episodes — This is a list of episodes for the French animated television series, Code Lyoko. The first season has no set viewing order save for the last two episodes, so it is listed by the order in which it aired. The following seasons have their episodes… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of Sega arcade system boards — The following is a list of arcade system boards released by Sega. Contents 1 Sega G80 1.1 G80 Specifications 2 Sega System 1 2.1 System 1 Specifications …   Wikipedia

  • List of electronics topics — Alphabetization has been neglected in some parts of this article (the b section in particular). You can help by editing it. This is a list of communications, computers, electronic circuits, fiberoptics, microelectronics, medical electronics,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”