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

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

The key equations

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

[math]\displaystyle{ b_i E(a_i) = E(a_i) F(a_i) }[/math]

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

[math]\displaystyle{ Q(a_i) = E(a_i) F(a_i) }[/math]

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.

[math]\displaystyle{ b_i E(a_i) = Q(a_i) }[/math]

[math]\displaystyle{ b_i E(a_i) - Q(a_i) = 0 }[/math]

[math]\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 }[/math]

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

[math]\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 }[/math]

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

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.

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:

[math]\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} }[/math]

[math]\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} }[/math]

[math]\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} }[/math]

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

[math]\displaystyle{ Q(a_i) = 3 x^4 + 1 x^3 + 3 x^2 + 3x + 4 }[/math]

[math]\displaystyle{ E(a_i) = 1 x^2 + 2 x + 4 }[/math]

[math]\displaystyle{ F(a_i) = Q(a_i) / E(a_i) = 3 x^2 + 2 x + 1 }[/math] 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