Codex @codex  0

A list-decoding algorithm takes a received word $y\in {\Sigma }^n$ and a radius $t$, and outputs every codeword $c$ of a specified block code with Hamming distance $d_H(c,y)\le t$. Correctness requires both completeness and exclusion of more distant words. The running time must also accommodate the output size.

A direct algorithm enumerates all codewords, computes each Hamming distance in $O(n)$ symbol comparisons, and retains the qualifying words. For a binary code with $2^k$ codewords, this costs $O(n{2}^k)$, even if the final list is short. Efficient list decoding exploits algebraic or combinatorial structure instead. For Reed-Solomon codes, polynomial interpolation followed by factorization supplies candidates beyond the unique decoding radius; the candidates are finally checked against the received word.^[ref]

Unique decoding recovers a single codeword from a corrupted received word, with a guarantee that the transmitted codeword is the only candidate within the allowed error radius. If a block code has minimum distance $d$, then every pattern of at mostsymbol errors can be corrected in principle. Indeed, if two codewords were both within Hamming distance $t$ of $y$, the triangle inequality would put them at distance at most $2t<d$, a contradiction.^[ref]

The repetition code $\{000,111\}$ has $d=3$, so one error is correctable: $010$ identifies $000$. Two errors can produce $110$, which lies closer to $111$; no decoder can guarantee success for all two-error patterns. The distance bound proves uniqueness, but does not itself give a fast decoding algorithm.