Berlekamp–Welch algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

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{alignat}{1} Q(1) & = 4*E(1) \\ Q(2) & = 3*E(2) \\ Q(3) & = 4*E(3) \\ Q(4) & = 1*E(4) \\ \end{alignat} 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) = {Q(x_i) \over 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_1x + q_2x^2 and bringing E(x) to the left, we can rewrite the system thus: \begin{alignat}{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{alignat} 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: {Q(x) \over 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 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 + 2 x + 1, and applying F(a i ) for a 4 = 3 to a 7 = 6, results in the code word {1,6,3,6,1,2,2}. Assume errors occur at c 2 and c 5 resulting in the received code word {1,5,3,6,3,2,2}. Start off with e = 2 and solve the linear equations: \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} \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} \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} Q(a_i) = 3 x^4 + 1 x^3 + 3 x^2 + 3x + 4 E(a_i) = 1 x^2 + 2 x + 4 F(a_i) = Q(a_i) / E(a_i) = 3 x^2 + 2 x + 1 with remainder = 0. E(a i ) = 0 at a 2 = 1 and a 5 = 4 Calculate F(a 2 = 1) = 6 and F(a 5 = 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 – The patent by Lloyd R. Welch and Elewyn R. Berlekamp

Text derived from https://en.wikipedia.org/w/index.php?oldid=1328903250 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.