↑ arvau

Wikipedia / 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:

  • Probabilistic noise model studied by Shannon in which the channel noise is modeled precisely in the sense that the probabilistic behavior of the channel is well known and the probability of occurrence of too many or too few errors is low

  • Worst-case or adversarial noise model considered by Hamming in which the channel acts as an adversary that arbitrarily corrupts the codeword subject to a bound on the total number of errors.

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

. The list-decoding problem can now be formulated as follows:

Input:, error bound

Output: whose hamming distance.

Motivation for list decoding

considered above occur only in the worst-case and if one looks at the way Hamming balls 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

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

Combinatorics of list decoding

In other words, the Johnson bound which means that it is possible to correct far more errors with list decoding.

List-decoding capacity

  1. Theorem (List-Decoding Capacity)..

    1. -list decodable code.

    2. .

    Where

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.

. 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 becomes super-polynomially large.

as the center.

is given by

Put another way, the volume of a Hamming ball is translation invariant. To continue with the proof sketch, we conjure the union bound.

picked at random, we have

we also have

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 decodability of Reed–Solomon error correctionReed–Solomon Codes

In 2023, building upon three seminal works, coding theorists showed that, with high probability, Reed–Solomon codes defined over random evaluation points are list decodable up to the list-decoding capacity over linear size alphabets.

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 of errors can be corrected. Some of the most prominent list-decoding algorithms are the following:

  • errors developed by Madhu Sudan.

  • Guruswami–Sudan '98 errors by Madhu Sudan and his then doctoral student Venkatesan Guruswami.

  • Parvaresh–Vardy '05 – In a breakthrough paper, Farzad Parvaresh and Alexander Vardy as in the case of usual Reed-Solomon codes.

  • Guruswami–Rudra '06 - In yet another breakthrough, Venkatesan Guruswami and Atri Rudra. In other words, this is error-correction with optimal redundancy. This answered a question that had been open for about 50 years. This work has been invited to the Research Highlights section of the Communications of the ACM (which is “devoted to the most important research results published in Computer Science in recent years”) and was mentioned in an article titled “Coding and Computing Join Forces” in the Sep 21, 2007 issue of the Science magazine. The codes that they are given are called folded Reed-Solomon codes which are nothing but plain Reed-Solomon codes but viewed as a code over a larger alphabet by careful bundling of codeword symbols.

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.

Output as small as possible so that a 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.

Step 2 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:

See also

References

Historical:

Review articles: