= List decoding
{title2=$L(y,t)$}
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> $C\subseteq\Sigma^n$, a radius-$t$ list is
$$
L(y,t)=\{c\in C:d_H(c,y)\leq t\}.
$$
The code is $(t,L)$-list-decodable when every received word has at most $L$ such <codewords>. This is a worst-case bound over received words, not an average list size.
For $C=\{000,111\}$ and received $y=001$, radius one gives the singleton $\{000\}$, 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.
Back to article page
