List decoding

In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.
The unique decoding model in coding theory, which is constrained to output a single valid codeword from the received word could not tolerate a greater fraction of errors. This resulted in a gap between the error-correction performance for stochastic noise models (proposed by Shannon) and the adversarial noise model (considered by Richard Hamming). Since the mid 90s, significant algorithmic progress by the coding theory community has bridged this gap. Much of this progress is based on a relaxed error-correction model called list decoding, wherein the decoder outputs a list of codewords for worst-case pathological error patterns where the actual transmitted codeword is included in the output list. In case of typical error patterns though, the decoder outputs a unique single codeword, given a received word, which is almost always the case (However, this is not known to be true for all codes). The improvement here is significant in that the error-correction performance doubles. This is because now the decoder is not confined by the half-the-minimum distance barrier. This model is very appealing because having a list of codewords is certainly better than just giving up. The notion of list-decoding has many interesting applications in complexity theory.
The way the channel noise is modeled plays a crucial role in that it governs the rate at which reliable communication is possible. There are two main schools of thought in modeling the channel behavior:
The highlight of list-decoding is that even under adversarial noise conditions, it is possible to achieve the information-theoretic optimal trade-off between rate and fraction of errors that can be corrected. Hence, in a sense this is like improving the error-correction performance to that possible in case of a weaker, stochastic noise model.
Mathematical formulation.
Let formula_1 be a formula_2 error-correcting code; in other words, formula_1 is a code of length formula_4, dimension formula_5 and minimum distance formula_6 over an alphabet formula_7 of size formula_8. The list-decoding problem can now be formulated as follows:
Input: Received word formula_9, error bound formula_10
Output: A list of all codewords formula_11 whose hamming distance from formula_12 is at most formula_10.
Motivation for list decoding.
Given a received word formula_14, which is a noisy version of some transmitted codeword formula_15, 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 formula_6 is the minimum Hamming distance of a code formula_1, then there exists two codewords formula_18 and formula_19 that differ in exactly formula_6 positions. Now, in the case where the received word formula_14 is equidistant from the codewords formula_18 and formula_19, unambiguous decoding becomes impossible as the decoder cannot decide which one of formula_18 and formula_19 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 formula_14 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 formula_10 beyond half-the minimum distance, there is only a single codeword formula_15 within Hamming distance formula_10 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.
List-decoding potential.
For a polynomial-time list-decoding algorithm to exist, we need the combinatorial guarantee that any Hamming ball of radius formula_30 around a received word formula_31 (where formula_32 is the fraction of errors in terms of the block length formula_4) has a small number of codewords. This is because the list size itself is clearly a lower bound on the running time of the algorithm. Hence, we require the list size to be a polynomial in the block length formula_4 of the code. A combinatorial consequence of this requirement is that it imposes an upper bound on the rate of a code. List decoding promises to meet this upper bound. It has been shown non-constructively that codes of rate formula_35 exist that can be list decoded up to a fraction of errors approaching formula_36. The quantity formula_36 is referred to in the literature as the list-decoding capacity. This is a substantial gain compared to the unique decoding model as we now have the potential to correct twice as many errors. Naturally, we need to have at least a fraction formula_35 of the transmitted symbols to be correct in order to recover the message. This is an information-theoretic lower bound on the number of correct symbols required to perform decoding and with list decoding, we can potentially achieve this information-theoretic limit. However, to realize this potential, we need explicit codes (codes that can be constructed in polynomial time) and efficient algorithms to perform encoding and decoding.
("p", "L")-list-decodability.
For any error fraction formula_39 and an integer formula_40, a code formula_41 is said to be list decodable up to a fraction formula_32 of errors with list size at most formula_43 or formula_44-list-decodable if for every formula_45, the number of codewords formula_46 within Hamming distance formula_47 from formula_14 is at most formula_49
Combinatorics of list decoding.
The relation between list decodability of a code and other fundamental parameters such as minimum distance and rate have been fairly well studied. It has been shown that every code can be list decoded using small lists beyond half the minimum distance up to a bound called the Johnson radius. This is quite significant because it proves the existence of formula_44-list-decodable codes of good rate with a list-decoding radius much larger than formula_51 In other words, the Johnson bound rules out the possibility of having a large number of codewords in a Hamming ball of radius slightly greater than formula_52 which means that it is possible to correct far more errors with list decoding.
List-decoding capacity.
What this means is that for rates approaching the channel capacity, there exists list decodable codes with polynomial sized lists enabling efficient decoding algorithms whereas for rates exceeding the channel capacity, the list size becomes exponential which rules out the existence of efficient decoding algorithms.
The proof for list-decoding capacity is a significant one in that it exactly matches the capacity of a formula_8-ary symmetric channel formula_66. In fact, the term "list-decoding capacity" should actually be read as the capacity of an adversarial channel under list decoding. Also, the proof for list-decoding capacity is an important result that pin points the optimal trade-off between rate of a code and the fraction of errors that can be corrected under list decoding.
Sketch of proof.
The idea behind the proof is similar to that of Shannon's proof for capacity of the binary symmetric channel formula_67 where a random code is picked and showing that it is formula_44-list-decodable with high probability as long as the rate formula_69 For rates exceeding the above quantity, it can be shown that the list size formula_43 becomes super-polynomially large.
A "bad" event is defined as one in which, given a received word formula_71 and formula_72 messages formula_73 it so happens that formula_74, for every formula_75 where formula_32 is the fraction of errors that we wish to correct and formula_77 is the Hamming ball of radius formula_78 with the received word formula_79 as the center.
Now, the probability that a codeword formula_80 associated with a fixed message formula_81 lies in a Hamming ball formula_82 is given by
where the quantity formula_84 is the volume of a Hamming ball of radius formula_78 with the received word formula_79 as the center. The inequality in the above relation follows from the upper bound on the volume of a Hamming ball. The quantity formula_87 gives a very good estimate on the volume of a Hamming ball of radius formula_32 centered on any word in formula_89 Put another way, the volume of a Hamming ball is translation invariant. To continue with the proof sketch, we conjure the union bound in probability theory which tells us that the probability of a bad event happening for a given formula_90 is upper bounded by the quantity formula_91.
With the above in mind, the probability of "any" bad event happening can be shown to be less than formula_92. To show this, we work our way over all possible received words formula_93 and every possible subset of formula_43 messages in formula_95
Now turning to the proof of part (ii), we need to show that there are super-polynomially many codewords around every formula_96 when the rate exceeds the list-decoding capacity. We need to show that formula_97 is super-polynomially large if the rate formula_58. Fix a codeword formula_99. Now, for every formula_96 picked at random, we have
since Hamming balls are translation invariant. From the definition of the volume of a Hamming ball and the fact that formula_79 is chosen uniformly at random from formula_103 we also have
Let us now define an indicator variable formula_105 such that
Taking the expectation of the volume of a Hamming ball we have
Therefore, by the probabilistic method, we have shown that if the rate exceeds the list-decoding capacity, then the list size becomes super-polynomially large. This completes the proof sketch for the list-decoding capacity.
List-decoding algorithms.
In the period from 1995 to 2007, the coding theory community developed progressively more efficient list-decoding algorithms. Algorithms for Reed–Solomon codes that can decode up to the Johnson radius which is formula_108 exist where formula_109 is the normalised distance or relative distance. However, for Reed-Solomon codes, formula_110 which means a fraction formula_111 of errors can be corrected. Some of the most prominent list-decoding algorithms are the following:
Because of their ubiquity and the nice algebraic properties they possess, list-decoding algorithms for Reed–Solomon codes were a main focus of researchers. The list-decoding problem for Reed–Solomon codes can be formulated as follows:
Input: For an formula_120 Reed-Solomon code, we are given the pair formula_121 for formula_122, where formula_123 is the formula_124th bit of the received word and the formula_125's are distinct points in the finite field formula_126 and an error parameter formula_127.
Output: The goal is to find all the polynomials formula_128 of degree at most formula_129 which is the message length such that formula_130 for at least formula_131 values of formula_132. Here, we would like to have formula_131 as small as possible so that greater number of errors can be tolerated.
With the above formulation, the general structure of list-decoding algorithms for Reed-Solomon codes is as follows:
Step 1: (Interpolation) Find a non-zero bivariate polynomial formula_134 such that formula_135 for formula_122.
Step 2: (Root finding/Factorization) Output all degree formula_129 polynomials formula_138 such that formula_139 is a factor of formula_134 i.e. formula_141. For each of these polynomials, check if formula_142 for at least formula_131 values of formula_144. If so, include such a polynomial formula_138 in the output list.
Given the fact that bivariate polynomials can be factored efficiently, the above algorithm runs in polynomial time.
Applications in complexity theory and cryptography.
Algorithms developed for list decoding of several interesting code families have found interesting applications in computational complexity and the field of cryptography. Following is a sample list of applications outside of coding theory: