Berlekamp–Welch algorithm

The goal of the decoder is to recover the original encoding polynomial ${\displaystyle F(a_i)}$, using the known inputs ${\displaystyle a_1,\cdots ,a_n}$ and received codeword ${\displaystyle b_1,\cdots ,b_n}$ with possible errors. It also computes an error polynomial ${\displaystyle E(a_i)}$ where ${\displaystyle E(a_i)=0}$ corresponding to errors in the received codeword.

The key equations

Defining e = number of errors, the key set of n equations is

${\displaystyle b_{i}E(a_i)=E(a_i)F(a_i)}$

Where E(a_i) = 0 for the e cases when b_i ≠ F(a_i), and E(a_i) ≠ 0 for the n - e non error cases where b_i = F(a_i) . These equations can't be solved directly, but by defining Q() as the product of E() and F():

${\displaystyle Q(a_i)=E(a_i)F(a_i)}$

and adding the constraint that the most significant coefficient of E(a_i) = e_e = 1, the result will lead to a set of equations that can be solved with linear algebra.

${\displaystyle b_{i}E(a_i)=Q(a_i)}$

${\displaystyle b_{i}E(a_i)-Q(a_i)=0}$

${\displaystyle b_i(e_0+e_1{a}_i+e_2{a}_i^2+\cdots +e_e{a}_i^e)-(q_0+q_1{a}_i+q_2{a}_i^2+\cdots +q_q{a}_i^q)=0}$

where q = n - e - 1. Since e_e is constrained to be 1, the equations become:

${\displaystyle b_i(e_0+e_1{a}_i+e_2{a}_i^2+\cdots +e_{e-1}{a}_i^{e-1})-(q_0+q_1{a}_i+q_2{a}_i^2+\cdots +q_q{a}_i^q)=-b_i{a}_i^e}$

resulting in a set of equations which can be solved using linear algebra, with time complexity ${\displaystyle O(n^3)}$.

The algorithm begins assuming the maximum number of errors e = ⌊(n-k)/2⌋. If the equations can not be solved (due to redundancy), e is reduced by 1 and the process repeated, until the equations can be solved or e is reduced to 0, indicating no errors. If Q()/E() has remainder = 0, then F() = Q()/E() and the code word values F(a_i) are calculated for the locations where E(a_i) = 0 to recover the original code word. If the remainder ≠ 0, then an uncorrectable error has been detected.