List decoding returns all codewords within a specified Hamming distance of a received word, rather than insisting on a single answer. For a block code , a radius- list isThe code is -list-decodable when every received word has at most such codewords. This is a worst-case bound over received words, not an average list size.
For and received , radius one gives the singleton , while radius two gives both codewords. Unique decoding cannot guarantee correction beyond half the minimum distance, but a bounded list can remain informative beyond that radius. An efficient list-decoding algorithm must find the candidates in reasonable time; the combinatorial list bound alone does not supply an algorithm. Extra information or a later check may then choose one candidate.
Articles by others on the same topic
List decoding is a method in coding theory that extends the concept of traditional decoding of error-correcting codes. In classical decoding, the goal is to recover the original message from a received codeword, assuming that the codeword has been corrupted by noise. When using list decoding, however, the decoder generates a list of all messages that are within a certain distance of the received codeword, rather than just trying to find a single most likely message.