Berlekamp–Welch algorithm

The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon codes 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 Lagrange interpolation 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 Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon codes 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 Lagrange interpolation 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. Defining e = number of errors, the key set of n equations is Where E(ai) = 0 for the e cases when bi ≠ F(ai), and E(ai) ≠ 0 for the n - e non error cases where bi = F(ai) . These equations can't be solved directly, but by defining Q() as the product of E() and F(): and adding the constraint that the most significant coefficient of E(ai) = ee = 1, the result will lead to a set of equations that can be solved with linear algebra. where q = n - e - 1. Since ee is constrained to be 1, the equations become: