Berlekamp–Welch algorithm

Short description: Error-correcting 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,\cdots ,m_k$ is used as coefficients of a polynomial $F(a_i)$ or used with Lagrange interpolation to generate the polynomial $F(a_i)$ of degree < k for inputs $a_1,\cdots ,a_k$ and then $F(a_i)$ is applied to $a_{k+1},\cdots ,a_n$ to create an encoded codeword $c_1,\cdots ,c_n$.

The goal of the decoder is to recover the original encoding polynomial $F(a_i)$, using the known inputs $a_1,\cdots ,a_n$ and received codeword $b_1,\cdots ,b_n$ with possible errors. It also computes an error polynomial $E(a_i)$ where $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

$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():

$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.

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

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

$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:

$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 $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 $y=5-x$, and one of the points is incorrect. The points that the algorithm gets as an input are $(1,4),(2,3),(3,4),(4,1)$, where $(3,4)$ is the defective point. The algorithm must solve the following system of equations:

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

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

Letting $E(x)=x+e_0$ and $Q(x)=q_0+q_{1}x+q_2{x}^2$ and bringing $E(x)$ to the left, we can rewrite the system thus:

$\begin{array}{rlrlrlrlrlr}{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{array}$

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

$q_0=-15,q_1=8,q_2=-1,e_0=-3$

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

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

$5-x$ fits three of the four points given, so it is the most likely to be the original polynomial.

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:

$\left[\begin{array}{ccccccc}{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{array}\right]\left[\begin{array}{c}{e}_0\\ e_1\\ q0\\ q1\\ q2\\ q3\\ q4\\ \end{array}\right]=\left[\begin{array}{c}-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{array}\right]$

$\left[\begin{array}{ccccccc}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{array}\right]\left[\begin{array}{c}{e}_0\\ e_1\\ q0\\ q1\\ q2\\ q3\\ q4\\ \end{array}\right]=\left[\begin{array}{c}0\\ 2\\ 2\\ 2\\ 1\\ 6\\ 5\\ \end{array}\right]$

$\left[\begin{array}{ccccccc}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{array}\right]\left[\begin{array}{c}{e}_0\\ e_1\\ q0\\ q1\\ q2\\ q3\\ q4\\ \end{array}\right]=\left[\begin{array}{c}4\\ 2\\ 4\\ 3\\ 3\\ 1\\ 3\\ \end{array}\right]$

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

$Q(a_i)=3x^4+1x^3+3x^2+3x+4$

$E(a_i)=1x^2+2x+4$

$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
• Welch, Lloyd R. & Elwyn R. Berlekamp, "Error Correction for Algebraic Block Codes", US patent 4,633,470, published September 27, 1983, issued December 30, 1986 – The patent by Lloyd R. Welch and Elewyn R. Berlekamp