List-decoding Algorithms
In the recent past, there has been a slew of efficient algorithms developed by the coding theory community towards the goal of achieving list-decoding capacity. List-decoding algorithms for Reed–Solomon codes that can decode up to the Johnson radius which is have been developed where is the normalised distance or relative distance. However, for Reed-Solomon codes, which means a fraction of errors can be corrected. Some of the most prominent list-decoding algorithms are the following:
- Sudan '95 – The first known non-trivial list-decoding algorithm for Reed–Solomon codes that achieved efficient list decoding up to errors developed by Madhu Sudan.
- Guruswami–Sudan '98 – An improvement on the above algorithm for list decoding Reed–Solomon codes up to errors by Madhu Sudan and his then doctoral student Venkatesan Guruswami.
- Parvaresh–Vardy '05 – In a breakthrough paper, Farzad Parvaresh and Alexander Vardy presented codes that can be list decoded beyond the radius for low rates . Their codes are variants of Reed-Solomon codes which are obtained by evaluating correlated polynomials instead of just as in the case of usual Reed-Solomon codes.
- Guruswami–Rudra '06 - In yet another breakthrough, Venkatesan Guruswami and Atri Rudra give explicit codes that achieve list-decoding capacity, that is, they can be list decoded up to the radius for any . 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 give 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 have been the main focus of researchers. The list-decoding problem for Reed–Solomon codes can be formulated as follows:
Input: For an Reed-Solomon code, we are given the pair for, where is the th bit of the received word and the 's are distinct points in the finite field and an error parameter .
Output: The goal is to find all the polynomials of degree at most which is the message length such that for at least values of . Here, we would like to have 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 such that for .
Step 2: (Root finding/Factorization) Output all degree polynomials such that is a factor of i.e. . For each of these polynomials, check if for at least values of . If so, include such a polynomial in the output list.
Given the fact that bivariate polynomials can be factored efficiently, the above algorithm runs in polynomial time.
Read more about this topic: List Decoding