List-decoding algorithm
ID: list-decoding-algorithm
A list-decoding algorithm takes a received word and a radius , and outputs every codeword of a specified block code with Hamming distance . 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 symbol comparisons, and retains the qualifying words. For a binary code with codewords, this costs , 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]
New to topics? Read the docs here!