List Decoding - Motivation For List Decoding

Motivation For List Decoding

Given a received word, which is a noisy version of some transmitted codeword, the decoder tries to output the transmitted codeword by placing its bet on a codeword that is “nearest” to the received word. The Hamming distance between two codewords is used as a metric in finding the nearest codeword, given the received word by the decoder. If is the minimum Hamming distance of a code, then there exists two codewords and that differ in exactly positions. Now, in the case where the received word is equidistant from the codewords and, unambiguous decoding becomes impossible as the decoder cannot decide which one of and to output as the original transmitted codeword. As a result, the half-the minimum distance acts as a combinatorial barrier beyond which unambiguous error-correction is impossible, if we only insist on unique decoding. However, received words such as considered above occur only in the worst-case and if one looks at the way Hamming balls are packed in high-dimensional space, even for error patterns beyond half-the minimum distance, there is only a single codeword within Hamming distance from the received word. This claim has been shown to hold with high probability for a random code picked from a natural ensemble and more so for the case of Reed–Solomon codes which is well studied and quite ubiquitous in the real world applications. In fact, Shannon’s proof of the capacity theorem for q-ary symmetric channels can be viewed in light of the above claim for random codes.

Under the mandate of list-decoding, for worst-case errors, the decoder is allowed to output a small list of codewords. With some context specific or side information, it may be possible to prune the list and recover the original transmitted codeword. Hence, in general, this seems to be a stronger error-recovery model than unique decoding.