Berlekamp–Welch algorithm

The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for <a href="/facts/Elwyn_R._Berlekamp/zUTTIlF6">Elwyn R. Berlekamp</a> and <a href="/facts/Lloyd_R._Welch/IdP5tqxo">Lloyd R. Welch</a>. This is a decoder algorithm that efficiently corrects errors in <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed–Solomon codes</a> for an RS(n, k), code based on the Reed Solomon original view where a message 
 
 
 
 
 m
 
 1
 
 
 ,
 ⋯
 ,
 
 m
 
 k
 
 
 
 
 {\displaystyle m_{1},\cdots ,m_{k}}
 
 is used as coefficients of a polynomial 
 
 
 
 F
 (
 
 a
 
 i
 
 
 )
 
 
 {\displaystyle F(a_{i})}
 
 or used with <a href="/facts/Lagrange_polynomial/MnpMmhtC">Lagrange interpolation</a> to generate the polynomial 
 
 
 
 F
 (
 
 a
 
 i
 
 
 )
 
 
 {\displaystyle F(a_{i})}
 
 of degree < k for inputs 
 
 
 
 
 a
 
 1
 
 
 ,
 ⋯
 ,
 
 a
 
 k
 
 
 
 
 {\displaystyle a_{1},\cdots ,a_{k}}
 
 and then 
 
 
 
 F
 (
 
 a
 
 i
 
 
 )
 
 
 {\displaystyle F(a_{i})}
 
 is applied to 
 
 
 
 
 a
 
 k
 +
 1
 
 
 ,
 ⋯
 ,
 
 a
 
 n
 
 
 
 
 {\displaystyle a_{k+1},\cdots ,a_{n}}
 
 to create an encoded codeword 
 
 
 
 
 c
 
 1
 
 
 ,
 ⋯
 ,
 
 c
 
 n
 
 
 
 
 {\displaystyle c_{1},\cdots ,c_{n}}
 
.
The goal of the decoder is to recover the original encoding polynomial 
 
 
 
 F
 (
 
 a
 
 i
 
 
 )
 
 
 {\displaystyle F(a_{i})}
 
, using the known inputs 
 
 
 
 
 a
 
 1
 
 
 ,
 ⋯
 ,
 
 a
 
 n
 
 
 
 
 {\displaystyle a_{1},\cdots ,a_{n}}
 
 and received codeword 
 
 
 
 
 b
 
 1
 
 
 ,
 ⋯
 ,
 
 b
 
 n
 
 
 
 
 {\displaystyle b_{1},\cdots ,b_{n}}
 
 with possible errors. It also computes an error polynomial 
 
 
 
 E
 (
 
 a
 
 i
 
 
 )
 
 
 {\displaystyle E(a_{i})}
 
 where 
 
 
 
 E
 (
 
 a
 
 i
 
 
 )
 =
 0
 
 
 {\displaystyle E(a_{i})=0}
 
 corresponding to errors in the received codeword.

Berlekamp–Welch algorithm open-in-new

Berlekamp–Welch algorithm