Guruswami–Sudan list decoding algorithm

In <a href="/facts/Coding_theory/SBqStoGL">coding theory</a>, <a href="/facts/List_decoding/WI1Mf26J">list decoding</a> is an alternative to unique decoding of error-correcting codes in the presence of many errors. If a code has relative distance 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
, then it is possible in principle to recover an encoded message when up to 
 
 
 
 δ
 
 /
 
 2
 
 
 {\displaystyle \delta /2}
 
 fraction of the codeword symbols are corrupted. But when error rate is greater than 
 
 
 
 δ
 
 /
 
 2
 
 
 {\displaystyle \delta /2}
 
, this will not in general be possible. List decoding overcomes that issue by allowing the decoder to output a short list of messages that might have been encoded. List decoding can correct more than 
 
 
 
 δ
 
 /
 
 2
 
 
 {\displaystyle \delta /2}
 
 fraction of errors.
There are many polynomial-time algorithms for list decoding. In this article, we first present an algorithm for <a href="/facts/RS_code/HPc3Qj6N">Reed–Solomon (RS) codes</a> which corrects up to 
 
 
 
 1
 −
 
 
 2
 R
 
 
 
 
 {\displaystyle 1-{\sqrt {2R}}}
 
 errors and is due to <a href="/facts/Madhu_Sudan/6XbwMvWN">Madhu Sudan</a>. Subsequently, we describe the improved <a href="/facts/Venkatesan_Guruswami/FLUy7glV">Guruswami</a>–<a href="/facts/Madhu_Sudan/6XbwMvWN">Sudan</a> list decoding algorithm, which can correct up to 
 
 
 
 1
 −
 
 
 R
 
 
 
 
 {\displaystyle 1-{\sqrt {R}}}
 
 errors.
Here is a plot of the rate R and distance 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 for different algorithms.
<a href="https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg">https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg</a>

Guruswami–Sudan list decoding algorithm open-in-new

Guruswami–Sudan list decoding algorithm