Reections on \Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes"
Venkatesan Guruswami, Madhu Sudan · 2002
A t-error-correcting code over a q-ary alphabet Fq is a set C ⊆ Fq such that for any received vector r ∈ Fq there is at most one vector c ∈ C that lies within a Hamming distance of t from r. The minimum distance of the code C is the minimum Hamming distance between any pair of distinct vectors c1, c2 ∈ C. In his seminal work introducing these concepts, Hamming pointed out that a code of minimum distance 2t+ 1 is a t-error-correcting code. It also pointed out the obvious fact that such a code is not a t′-error-correcting code for any t′ > t. We conclude that a code can correct half as many errors as its distance and no more. The mathematical correctness of the above statements are indisputable, yet the interpretation is quite debatable. If a message encoded with a t-error-correcting code ends up getting corrupted in t′ > t places, the decoder may simply throw it hands up in the air and cite the above paragraph. Or, in an alternate notion of decoding, called list decoding, proposed in the late 1950s by Elias [10] and Wozencraft [43], the decoder could try to output a list of codewords within distance t′ of the received vector. If t′ is not much larger than t and the errors are caused by a probabilistic (non-malicious) channel, then most likely this list would have only one element — the transmitted codeword. Even if the errors are caused by a malicious jammer, the list cannot contain too many codewords provided t′ is not too much larger than t. Thus, in either case, the receiver is in a better position to recover the transmitted codeword under the model of list decoding. List decoding was initiated mainly as a mathematical tool that allowed for a better understanding of some of the classical parameters of interest in information and coding theory. Elias [10] used this notion to get a better handle on the error-exponent in the strong forms of Shannon’s coding theorem. The notion also plays a dominant role in the Elias-Bassalygo [34, 4] upper bound on the rate of a code as a function of its relative distance. Through the decades the notion has continued to be investigated in a combinatorial context; and more recently has seen a spurt of algorithmic results. The paper being reflected on [23] was motivated by a gap between the combinatorial understanding of Reed-Solomon codes, and the known algorithmic performance. Below we summarize the combinatorial state of knowledge, and describe the main result of [23], and also use the opportunity to survey some of the rich body of algorithmic results on list decoding that have emerged in the recent past. We also muse upon some useful asymptotic perspectives that eased the way for some of this progress, and reflect on some possibilities for future work.