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, code based on the Reed Solomon original view where a message is used as coefficients of a polynomial or used with Lagrange interpolation to generate the polynomial of degree < k for inputs and then is applied to to create an encoded codeword. The goal of the decoder is to recover the original encoding polynomial, using the known inputs and received codeword with possible errors. It also computes an error polynomial where corresponding to errors in the received codeword.
The key equations
Defining e = number of errors, the key set of n equations is Where E = 0 for the e cases when bi ≠ F, and E ≠ 0 for the n - e non error cases where bi = F. These equations can't be solved directly, but by defining Q as the product of E and F: and adding the constraint that the most significant coefficient of E = ee = 1, the result will lead to a set of equations that can be solved with linear algebra. where q = n - e - 1. Since ee is constrained to be 1, the equations become: resulting in a set of equations which can be solved using linear algebra, with time complexity O. The algorithm begins assuming the maximum number of errors e = ⌊ /2 ⌋. If the equations can not be solved, 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 are calculated for the locations where E = 0 to recover the original code word. If the remainder ≠ 0, then an uncorrectable error has been detected.
Example
Consider RS defined in with α = 3 and input values: ai = i-1 :. The message to be systematically encoded is. Using Lagrange interpolation, F = 3 x2 + 2 x + 1, and applying F for a4 = 3 to a7 = 6, results in the code word. Assume errors occur at c2 and c5 resulting in the received code word. Start off with e = 2 and solve the linear equations: Starting from the bottom of the right matrix, and the constraint e2 = 1: with remainder = 0. E = 0 at a2 = 1 and a5 = 4 Calculate F = 6 and F = 1 to produce corrected code word.
