Motivation
Repeating a symbol protects it by using many copies of the same information. Polynomial evaluation distributes information differently: several message symbols become coefficients, and the transmitted symbols are values at distinct points. Any sufficiently large surviving set of values determines the entire polynomial. This makes the construction especially transparent for erasures, where the receiver knows which positions are missing.
The key fact is that two low-degree polynomials cannot agree at too many distinct points unless they are equal. It gives a distance proof, an interpolation decoder for erasures and an exact account of the redundancy. We also derive a parity-check matrix, connecting this evaluation viewpoint with the earlier linear-code chapters. Unknown errors require another argument; the next decoding unit will supply it.
We assume finite-field arithmetic, polynomial division and the definitions of a linear code and its distance.
Definitions
Let be a finite field, and choose integers and distinct points . For a polynomial of degree less than , form its evaluation word
The set of these words is the Reed–Solomon evaluation code . A coefficient message represents . All operations take place in the field. When is a nonprime prime power, field arithmetic is not integer arithmetic modulo .
An erasure is an explicitly missing coordinate. An error is a received field element that differs from the transmitted one, without its position necessarily being known. We count erased positions and errors among the remaining positions; these are disjoint sets of coordinates. Minimum distance provides uniqueness under a bound on these counts, while an algorithm must separately find the transmitted word.
For a linear code, the Singleton bound proved below states . A code attaining this bound is called maximum distance separable, or MDS. This is a statement about distance at fixed length and dimension. It is different from perfection, which asks whether disjoint decoding balls fill the whole ambient space.
Theorem/proposition
Theorem 16.1.1
(Singleton bound)
Every linear code satisfies .
The evaluation construction attains this bound, and interpolation supplies both its erasure decoder and its parity checks.
Theorem 16.1.2
(Evaluation parameters and erasure recovery)
The code is linear with parameters . Any of its coordinates determine the entire codeword. In particular, up to erasures can be recovered uniquely. More generally a received word with unknown errors and erasures has at most one compatible codeword within that error bound whenever .
Theorem 16.1.3
(Interpolation weights give parity checks)
Assume , and put
The matrix with entries , for , has rank and satisfies . Here words are treated as columns in the equation . An equivalent row-word convention uses a transpose.
Proof sketch or proof idea
Root counts determine the code parameters
Proof
(Root bound, injectivity and a word of minimum weight)
Evaluation is linear because evaluating a sum or scalar multiple commutes with those operations. A nonzero polynomial of degree at most has at most distinct roots in a field. To recall the proof, a root gives a factor by division; every different root is a root of the remaining factor, since a field has no zero divisors. Induction on degree proves the bound.
If all evaluations of a degree-less-than- polynomial vanish, the root bound and force the polynomial to be zero. Thus evaluation is injective, giving dimension . For any nonzero codeword, at most coordinates are zero, so its weight is at least . This lower bound is attained: the polynomial vanishes at those points and nowhere else in the chosen set. For use the empty product one. Hence the minimum distance is exactly .
Proof
(Deleting coordinates)
Here is a direct proof of the Singleton bound that does not assume the evaluation construction. Delete any coordinates from every word of a code of minimum distance . Two different codewords cannot become equal: otherwise they originally differed in at most those positions. The deletion map is therefore injective. For a linear dimension- code this gives , hence the bound. Evaluation codes attain it by the root-count calculation.
Recover a polynomial from values
Proof
(Lagrange interpolation, and a distance count)
Choose any distinct surviving points with values . Define the Lagrange polynomials
Every denominator is nonzero by distinctness. Each has degree at most and equals one at and zero at the other selected points. Thus has the prescribed values. If another polynomial of degree less than did too, their difference would have roots and must be zero. Evaluating the reconstructed at the missing coordinates recovers all erasures.
For mixed errors and erasures, suppose two candidate codewords each disagree with the unerased received positions at at most places. They differ from each other at at most unerased positions and at most erased positions. Their distance would be at most , a contradiction. This proves uniqueness. It does not tell us which unerased positions are incorrect, so ordinary interpolation on an arbitrary received positions is not yet an error-correction algorithm.
Choose what the message symbols mean
The coefficient encoder is convenient for proving linearity, but the message does not need to be a coefficient list. Choose any designated coordinate positions as information positions. Interpret the message as the desired values at those positions, interpolate the unique degree-less-than- polynomial taking those values, and output its values at every point. The message then appears unchanged at the designated coordinates: this is a systematic encoder. Injectivity of interpolation shows that every old codeword still occurs, so the code and its distance have not changed. Only the correspondence between messages and codewords has changed.
For erasure recovery, the information positions need not be among the survivors. Any distinct surviving points suffice. This flexibility is the operational meaning of the MDS property in the erasure model: no particular subset of positions is privileged. If more than symbols survive, one may reconstruct from any and compare the result with the remaining observations. Under the stated erasure-only promise they agree. Without that promise, disagreement reveals that the erasure-only model is wrong, but does not itself identify all incorrect symbols.
The erasure limit is sharp. Take a nonzero minimum-weight codeword, whose support has positions, and erase exactly that support. Every surviving coordinate is zero, just as for the zero codeword. The receiver cannot distinguish those two transmitted words from the surviving data. Thus no decoder for this code can recover every pattern of erasures. The earlier recovery theorem and this ambiguity example give matching positive and negative statements, rather than only a sufficient condition.
Increasing raises the symbol rate but reduces both the guaranteed erasure tolerance and minimum distance. This tradeoff is exact for the fixed evaluation construction. It does not compare every possible code over every alphabet, and the requirement of enough distinct field points remains part of the construction.
Interpolation also explains the check matrix
Proof
(A missing top coefficient, and a root count for the rows)
Apply Lagrange interpolation at all points to the polynomial , where . Its coefficient of is zero. The coefficient of in the th Lagrange basis polynomial is , so comparison gives
For a message monomial with and a row index , one has . The identity therefore shows . By linearity every codeword is in .
The rows are independent. If a row combination vanishes, a polynomial of degree at most satisfies at all points. Each is nonzero, so has roots and must be zero. Thus the rank is and the kernel has dimension , equal to . When , the code is the whole space and the empty check matrix can be handled separately; no nonzero parity equations are needed.
Proof X-ray
Where the hypotheses enter the parity-check proof
The proof has two halves that use different facts. Containment is pure degree bookkeeping: a message monomial of degree times a row monomial of degree has degree at most , so the vanishing of the top Lagrange coefficient applies. This is the only place where the row range stops at ; one more row would reach degree and the identity would fail. Independence of the rows uses the root bound again, together with , which holds because the points are distinct. The two halves meet in a dimension count: has dimension , so containment becomes equality without any direct description of the kernel. The hypothesis only ensures that has at least one row.
Worked examples
Worked example 16.1.4
(Encode five symbols from three coefficients)
Work over , with points and . The coefficient message represents . Its evaluations are
since the unreduced values are . The code is : it uniquely corrects one unknown error or recovers two erasures. A message consisting of the first three evaluations would instead be . Coefficient encoding and systematic-value encoding are different message conventions for the same code.
Worked example 16.1.5
(Recover two missing evaluations)
Suppose the values at survive as . Write . The first gives . The other two give and modulo seven. Subtracting twice the first equation from the second yields ; hence . The reconstructed polynomial is , and the erased values at are . Distinctness of these three points and the degree bound prove uniqueness beyond this one successful calculation.
Worked example 16.1.6
(Check the same word with two parity equations)
For the five points above, the weights are . For example, at point zero the denominator is in the field, whose inverse is five. The matrix is
On the word the two integer dot products are and , both zero modulo seven. If the fourth coordinate increases by one, the syndrome increases by the fourth column . This checks membership and isolates the syndrome effect of that specified error; identifying an unknown error still requires a decoding rule.
Concept lensStructural
The dual code is again an evaluation code
The rows of span , because has rank and . A row combination with coefficient polynomial , of degree less than , is the word . So evaluates polynomials of degree less than and then rescales coordinate by . The root bound gives every nonzero dual word weight at least : the dual is MDS too. In the worked example the two rows have weights five and four.
Common mistakes
Common mistake
(MDS does not mean perfect)
In the example a radius-one ball has words. The code has words, so its disjoint radius-one balls contain words, fewer than the ambient . It meets the Singleton bound while leaving many received words outside those balls. Different optimality statements compare different resources.
Counterexample mode
A residue ring is not a substitute for the field
Over , the nonzero degree-one polynomial vanishes at both zero and two. Evaluating at gives , of weight two, whereas the field formula for length four and dimension parameter two would predict distance three. The failed step is the root bound: two is a zero divisor and cancellation is unavailable. A field of order four exists, but it is a different algebraic object from this residue ring.
Common mistake
(Repeating an evaluation point)
Distinct evaluation points are essential. Repeating the same point adds another copy of the same equation, not an independent interpolation condition. Over with the points and , the polynomial evaluates to , a nonzero codeword of weight , below the value that the root count would give. For length greater than , one needs a different or extended construction; this chapter's definition cannot supply that many distinct field elements.
Summary
The field root bound gives exact distance and injective encoding. Lagrange interpolation recovers erasures, the Singleton argument explains the attained distance bound, and a top-coefficient comparison produces explicit parity checks. These results separate recoverable missing positions from unknown errors and set up a polynomial-time error decoder in the companion unit.
Exercises
Quick check
(Over , evaluate at and state the code parameters for .)
Reduce each value modulo , then use .
Solution · Answer
The word is , and the code is . The integer value at is , which is zero in the field.
Quick check
(In that code only the values and survive. Recover .)
Write and subtract the two equations.
Solution · Answer
Write . Subtracting gives modulo five, so and . Two distinct points determine a degree-less-than-two polynomial uniquely.
Quick check
(For an evaluation code, explain why , is covered by the uniqueness theorem when , but , is not.)
Compare with .
Solution
The first pair gives , so two competing codewords would violate distance. The second gives and lies outside the proved guarantee. Failure of the guarantee is not a claim that every such pattern is ambiguous; it means this theorem cannot certify uniqueness uniformly.
Quick check
(Prove directly that the dimension-one evaluation code has distance . Why is the claim still valid if one selected evaluation point is zero?)
Polynomials of degree less than one are constants.
Solution
Degree less than one means a constant polynomial. Every nonzero constant gives a word with all entries nonzero, so its weight and the minimum distance are . Evaluating a nonzero constant at zero does not change it; zero is a valid evaluation point and should not be confused with a zero code symbol.
For a broader view of algebraic code families, see Guruswami's coding-theory notes on Reed–Solomon and related codes.