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 ${\displaystyle m_{1},\cdots ,m_{k}}$ is used as coefficients of a polynomial ${\displaystyle F(a_{i})}$ or used with Lagrange interpolation to generate the polynomial ${\displaystyle F(a_{i})}$ of degree < k for inputs ${\displaystyle a_{1},\cdots ,a_{k}}$ and then ${\displaystyle F(a_{i})}$ is applied to ${\displaystyle a_{k+1},\cdots ,a_{n}}$ to create an encoded codeword ${\displaystyle c_{1},\cdots ,c_{n}}$.

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.

Simple Example

The error locator polynomial serves to "neutralize" errors in P by making Q zero at those points, so that the system of linear equations is not affected by the inaccuracy in the input.

Consider a simple example where a redundant set of points are used to represent the line ${\displaystyle y=5-x}$, and one of the points is incorrect. The points that the algorithm gets as an input are ${\displaystyle (1,4),(2,3),(3,4),(4,1)}$, where ${\displaystyle (3,4)}$ is the defective point. The algorithm must solve the following system of equations:

${\displaystyle {\begin{alignedat}{1}Q(1)&=4*E(1)\\Q(2)&=3*E(2)\\Q(3)&=4*E(3)\\Q(4)&=1*E(4)\\\end{alignedat}}}$

Given a solution ${\displaystyle Q}$ and ${\displaystyle E}$ to this system of equations, it is evident that at any of the points ${\displaystyle x=1,2,3,4}$ one of the following must be true: either ${\displaystyle Q(x_{i})=E(x_{i})=0}$, or ${\displaystyle P(x_{i})={Q(x_{i}) \over E(x_{i})}=y_{i}}$. Since ${\displaystyle E}$ is defined as only having a degree of one, the former can only be true in one point. Therefore, ${\displaystyle P(x_{i})}$ must equal ${\displaystyle y_{i}}$ at the three other points.

Letting ${\displaystyle E(x)=x+e_{0}}$ and ${\displaystyle Q(x)=q_{0}+q_{1}x+q_{2}x^{2}}$ and bringing ${\displaystyle E(x)}$ to the left, we can rewrite the system thus:

${\displaystyle {\begin{alignedat}{10}q_{0}&+&q_{1}&+&q_{2}&-&4e_{0}&-&4&=&0\\q_{0}&+&2q_{1}&+&4q_{2}&-&3e_{0}&-&6&=&0\\q_{0}&+&3q_{1}&+&9q_{2}&-&4e_{0}&-&12&=&0\\q_{0}&+&4q_{1}&+&16q_{2}&-&e_{0}&-&4&=&0\end{alignedat}}}$

This system can be solved through Gaussian elimination, and gives the values:

${\displaystyle q_{0}=-15,q_{1}=8,q_{2}=-1,e_{0}=-3}$

Thus, ${\displaystyle Q(x)=-x^{2}+8x-15,E(x)=x-3}$. Dividing the two gives:

${\displaystyle {Q(x) \over E(x)}=P(x)=5-x}$

${\displaystyle 5-x}$ fits three of the four points given, so it is the most likely to be the original poly

Example

Consider RS(7,3) (n = 7, k = 3) defined in GF(7) with α = 3 and input values: a_i = i-1 : {0,1,2,3,4,5,6}. The message to be systematically encoded is {1,6,3}. Using Lagrange interpolation, F(a_i) = 3 x² + 2 x + 1, and applying F(a_i) for a₄ = 3 to a₇ = 6, results in the code word {1,6,3,6,1,2,2}. Assume errors occur at c₂ and c₅ resulting in the received code word {1,5,3,6,3,2,2}. Start off with e = 2 and solve the linear equations:

${\displaystyle {\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}}$

Starting from the bottom of the right matrix, and the constraint e₂ = 1:

${\displaystyle Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4}$

${\displaystyle E(a_{i})=1x^{2}+2x+4}$

${\displaystyle F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1}$ with remainder = 0.

E(a_i) = 0 at a₂ = 1 and a₅ = 4 Calculate F(a₂ = 1) = 6 and F(a₅ = 4) = 1 to produce corrected code word {1,6,3,6,1,2,2}.

See also

• Reed–Solomon error correction

External links

• MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan
• University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra
• Algebraic Codes on Lines, Planes and Curves, An Engineering Approach – Richard E. Blahut
• Welch Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch
• US 4,633,470, Welch, Lloyd R. & Berlekamp, Elwyn R., "Error Correction for Algebraic Block Codes", published September 27, 1983, issued December 30, 1986 – The patent by Lloyd R. Welch and Elewyn R. Berlekamp