Must the decoder know where the errors occurred?

No. The error-locator construction is designed to recover without that information.

Can it work with ordinary floating-point noisy measurements?

The Reed - Solomon setting uses exact finite-field symbols. Statistical noise fitting is a different problem.

The intended relation is Q = P E, so exact division removes the error-locator factor and recovers P.

AI Glossary / Mathematics and optimization / Advanced

Berlekamp - Welch algorithm

Definition

The Berlekamp - Welch algorithm recovers a low-degree polynomial from evaluations that include a limited number of incorrect values. It is used to decode Reed - Solomon codes by solving linear equations for an error-locator polynomial and a related product polynomial. The decoder does not need to know the error locations beforehand, but recovery depends on having enough redundancy and staying within the supported error bound.

What it means

A message can be represented by polynomial coefficients over a finite field. The sender evaluates that polynomial at several distinct points and transmits the resulting values. Extra evaluations provide redundancy beyond what is needed for ordinary interpolation.

If some transmitted values are changed, interpolating through every received point can produce the wrong polynomial. Berlekamp - Welch instead introduces an auxiliary polynomial that vanishes at erroneous positions. This converts an apparently combinatorial search over error locations into an algebraic problem.

How it works

Suppose the message polynomial P has degree less than k, there are n distinct evaluation points, and at most t received values are wrong. The usual unique-decoding condition is n ≥ k + 2t.

Seek a nonzero error-locator E of degree at most t and a polynomial Q of degree less than k + t such that Q(x_i) = y_i E(x_i) for every received pair. Treat the coefficients of Q and E as unknowns and solve the resulting linear system, using a suitable normalization to avoid the all-zero solution.

Divide Q by E to obtain a candidate P. Check exact divisibility, the degree bound, and agreement with enough received symbols. Arithmetic must use the code's field. A failed check must not be disguised as successful correction.

Three practical examples

1. A coding-theory demonstration reconstructs a short message after one transmitted symbol is altered, without revealing the altered position to the decoder.

2. A storage research prototype studies algebraic decoding of redundant polynomial evaluations and compares implementation costs with other Reed - Solomon decoding approaches.

3. A distributed-computation experiment models returned values as polynomial evaluations, then investigates how many incorrect results can be corrected under its encoding assumptions.

Think of it this way

Think of recovering a simple curve from plotted points when a few labels are wrong. Instead of guessing which labels to erase, the algorithm builds a mathematical mask that becomes zero at the bad locations. The analogy is limited: finite-field geometry does not behave like an ordinary real-valued graph, and the decoder corrects symbol errors rather than small measurement noise.

Worked example

Work in the field of integers modulo 7. The original polynomial is P(x) = 2x + 1, with degree less than k = 2. At points x = 0,1,2,3,4, its values are 1,3,5,0,2. Suppose the third value is corrupted from 5 to 6, so the receiver sees 1,3,6,0,2.

There are n = 5 evaluations and t = 1 error, satisfying 5 ≥ 2 + 2. Set E(x) = x + e and Q(x) = ax squared + bx + c. Each received pair gives a linear equation in a,b,c,e. For example, the x = 0 equation is c = e, and the x = 1 equation is a + b + c = 3(1 + e), all modulo 7.

A solution is E(x) = x + 5 and Q(x) = 2x squared + 4x + 5. E vanishes at x = 2 because 2 + 5 equals zero modulo 7. At that point, both sides of Q(2) = 6E(2) are zero, so the incorrect received value is neutralized.

At the other four points, Q evaluates to 5,4,0,4 respectively, matching the products of received values and E. Polynomial division gives Q/E = 2x + 1 exactly. Evaluating this recovered polynomial identifies the sole disagreement at x = 2 and restores its value to 5.

The arithmetic is exact modular arithmetic. Replacing it with ordinary decimal division would solve a different problem. This is a hand-checked reconstruction, not a benchmark of a decoder implementation.

Illustrative case study

Fictional case: Birch Archive demonstrates a redundant storage format using a small finite-field code. Its test tool initially reports “repaired” whenever the linear solver returns coefficients.

Reviewers add checks that the quotient is a polynomial of the permitted degree and that the reconstructed word differs from the received word in no more than the supported number of positions. They include tests beyond the correction radius and keep a separate integrity mechanism for confirming intended content. The case illustrates validation requirements; it does not claim that every corruption outside the bound is detectable or recoverable.

Common misconceptions and mistakes

Do not confuse an error with an erasure. An erasure's location is known, while an erroneous symbol may appear ordinary. Unknown locations require additional redundancy for guaranteed unique correction.

Do not assume the algorithm corrects arbitrarily many errors because it uses a linear solver. Beyond the correction radius, ambiguity or failure can occur, and a different nearby codeword may be misleading.

Berlekamp - Welch is also distinct from Berlekamp - Massey and polynomial factorization algorithms sharing the Berlekamp name. Finally, error correction does not authenticate who produced a message or establish that its original contents were truthful.

Business use

The relevant business benefit is dependable reconstruction within an explicitly designed encoding model. Before choosing a decoder, establish symbol size, code parameters, expected error and erasure patterns, and the required throughput.

Compare mature implementations and account for field operations, validation, and failure handling. A teaching example over seven elements is useful for understanding the mechanism but says little about storage-system performance. Keep correction status separate from application-level acceptance, especially when a reconstructed record will trigger further automated processing.

Check your understanding

Why does the corrupted value 6 cause no contradiction at x = 2 in the worked equations?

Answer: E(2) is zero modulo 7, so multiplying the received value by E(2) gives zero. Q(2) is also zero, preserving the equation.

Related terms

Hamming distance
Reed–Solomon code
finite field
polynomial interpolation
error-locator polynomial
error correction
erasure
linear system

Learn next

Study finite-field arithmetic next. Verify all five equations in the example and the polynomial product E × P. Then compare the redundancy required when the single damaged position is known in advance.

Sources

Primary reference opened: Madhu Sudan's MIT Essential Coding Theory, Lecture 6, https://ocw.mit.edu/courses/6-895-essential-coding-theory-fall-2004/139d3fc06ab21f3201e4f43500163427_lect06.pdf. Its error-locator and linear-system construction were read. The modulo-7 example and fictional case are original hand-checked illustrations.

Previous: Berk-Jones test Next: Berlin procedure