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
is used as coefficients of a polynomial
or used with Lagrange interpolation to generate the polynomial
of degree < k for inputs
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
corresponding to errors in the received codeword.
Defining e = number of errors, the key set of n equations is Where E(ai) = 0 for the e cases when bi ≠ F(ai), and E(ai) ≠ 0 for the n - e non error cases where bi = F(ai) .
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(ai) = ee = 1, the result will lead to a set of equations that can be solved with linear algebra.
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
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(ai) are calculated for the locations where E(ai) = 0 to recover the original code word.
If the remainder ≠ 0, then an uncorrectable error has been detected.
Consider RS(7,3) (n = 7, k = 3) defined in GF(7) with α = 3 and input values: ai = i-1 : {0,1,2,3,4,5,6}.
The message to be systematically encoded is {1,6,3}.
Using Lagrange interpolation, F(ai) = 3 x2 + 2 x + 1, and applying F(ai) for a4 = 3 to a7 = 6, results in the code word {1,6,3,6,1,2,2}.
Assume errors occur at c2 and c5 resulting in the received code word {1,5,3,6,3,2,2}.
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(ai) = 0 at a2 = 1 and a5 = 4 Calculate F(a2 = 1) = 6 and F(a5 = 4) = 1 to produce corrected code word {1,6,3,6,1,2,2}.