Engineering / Mathematics — Polynomial Algorithms
Error-Correcting Codes and Algebraic Decoding
Reed-Solomon codes, their distance property, and decoding by rational function reconstruction.
Executive summary
Reed-Solomon codes encode a message as the evaluations of a polynomial. Two distinct low-degree polynomials agree in few places, which gives the code its error-correcting distance.
Decoding reduces to rational function reconstruction, so the extended Euclidean algorithm is the decoder.
Learning objectives
- Define Reed-Solomon codes and derive the minimum distance.
- State the error correction capability.
- Describe decoding as reconstruction.
01The code
Reed-Solomon code
Fix distinct evaluation points x₁, ..., x_n in F_q. A message (m₀, ..., m_{k−1}) is encoded as the evaluations (f(x₁), ..., f(x_n)) of f(X) = Σ mᵢX^i.
Minimum distance
Two distinct polynomials of degree below k agree in at most k − 1 points, so distinct codewords differ in at least n − k + 1 positions.
This meets the Singleton bound with equality, making Reed-Solomon codes maximum distance separable — no code with the same parameters can do better. The proof is simply that a non-zero polynomial of degree below k has fewer than k roots.
Corrects up to t = ⌊(n − k)/2⌋ errors02Why the distance gives correction
If fewer than half the distance many errors occur, the received word is closer to the transmitted codeword than to any other, so nearest-codeword decoding recovers it uniquely.
- Detection only
up to n − k errorsEnough to know something is wrong - Unique correction
up to (n − k)/2 errorsThe classical decoding radius - List decoding
beyond that radiusReturns a short list containing the true codeword
03Decoding by reconstruction
Compute syndromes
From the received word, forming a polynomial capturing the error information.
Set up the key equation
The error locator and evaluator polynomials satisfy a congruence modulo a known polynomial.
Solve by reconstruction
Run extended Euclid, halting when the remainder degree falls below the bound. This is rational function reconstruction.
Find error positions
The roots of the error locator polynomial identify which positions are corrupt.
Compute error values
Evaluate the error evaluator at those positions and correct.
The decoder is therefore extended Euclid with a degree-based stopping rule, plus a root-finding step. Recognising the key equation as a reconstruction problem is what makes the algorithm short and its correctness clear.
| Decoder | Method | Note |
|---|---|---|
| Berlekamp-Massey | Minimal linear recurrence | Equivalent to the Euclidean approach |
| Euclidean | Rational function reconstruction | Conceptually cleaner; same cost |
| Sugiyama | Euclidean variant | The standard practical formulation |
Berlekamp–Massey and the Euclidean decoder solve the same problem and are essentially the same algorithm in different presentations, which is why the linearly generated sequence machinery appears in both coding theory and sparse linear algebra.
04Frequently asked questions
Where are Reed-Solomon codes used?
Widely — optical media, QR codes, deep space communication, RAID storage and distributed storage systems. Their burst-error tolerance suits applications where errors cluster rather than scatter.
Why does the code need a finite field?
Because symbols must be field elements for the polynomial evaluation and interpolation to work. The field size bounds the code length, since evaluation points must be distinct.
How does this relate to secret sharing?
They are the same construction viewed differently. Shamir's shares are evaluations of a polynomial, exactly as codeword symbols are, and the threshold property is the interpolation property that gives the code its distance.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 413-415.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.