Redundancy by evaluating a polynomial
Polynomial interpolation reconstructed a shared secret from enough values. The same root bound also builds a code that tolerates missing or corrupted symbols, though error correction and secrecy are different goals.
Definition 9.1.1
(Polynomial evaluation code)
Let be a prime and work in . Choose integers and distinct evaluation points . Encode a coefficient vector by forming and sending
Each coordinate is one field symbol, not necessarily one bit. The code is the set of all such words.
These polynomial evaluation codes are a standard Reed–Solomon construction; the points need not exclude zero. The set is linear because evaluation respects addition and scalar multiplication. A nonzero polynomial of degree below cannot vanish at all distinct points, so evaluation is injective and .
Exact minimum distance
Theorem 9.1.2
(Distance of an evaluation code)
For the construction above the minimum Hamming distance is .
Proof
(Root count for the lower bound, a product of factors for equality)
For two distinct polynomials of degree below , their nonzero difference has at most roots. Their evaluation words therefore agree in at most positions and differ in at least . Equality is attained: choose any evaluation points and let be the product of the corresponding factors , with the empty product if . Its degree is , it vanishes exactly at those chosen positions, and the words for and zero have distance .
Common mistake
(Evaluation points must be distinct)
The root bound counts distinct roots, so a repeated point breaks the distance formula. Over with and points , the polynomial has degree two and word , of weight two rather than .
Missing versus incorrect symbols
Definition 9.1.3
(Erasures and errors)
An erasure is a position whose value is marked as unavailable; an error is an unmarked position containing the wrong value.
The following is a uniqueness guarantee, not an efficient decoding algorithm.
Theorem 9.1.4
(Mixed errors and erasures)
Suppose a transmitted codeword has erased positions and at most erroneous unerased positions. If , it is the unique codeword differing from the received values in at most unerased positions. For this code the condition is .
Proof
(Two candidates would be too close)
If a second codeword also differs from the received values in at most unerased positions, the two codewords differ in at most unerased positions. They can additionally differ in at most erased positions. Their total distance would be at most , contradicting the minimum distance. The transmitted word exists and satisfies the condition by assumption. Since all quantities are integers, is equivalent to .
Proof X-ray
Why an error costs two positions in the bound
The key move is a triangle inequality on the unerased positions only: two candidate codewords may disagree with the same visible received word at different positions, so their mutual distance there can include both sets of errors, up to . At an erased position there is no observed value to compare with, and that position contributes at most one to their mutual distance. The hypothesis is used exactly once, to contradict the minimum distance; existence of a good candidate is not proved but assumed, since the transmitted word is one. Nothing in the argument uses polynomials beyond the value of , so the same count holds for any code of minimum distance .
When , up to erasures leave at least known values, from which interpolation reconstructs . With errors present, the theorem establishes uniqueness under the stated bound but does not tell us how to find the word efficiently. Outside the bound, the proof gives no universal guarantee; an arbitrary decoder may fail or miscorrect.
Worked example 9.1.5
(A length-five code over )
Take , , and evaluation points . For , the values are , , , and , so the word is modulo seven. Here : any two erasures are recoverable, or one unmarked symbol error is uniquely correctable.
Worked example 9.1.6
(Filling two erasures by interpolation)
Suppose the positions at and are erased, leaving the pairs . The values are symmetric about , so try ; then gives . Expanding, , which is . The erased values are and . Three point-value pairs determine a polynomial of degree at most two uniquely, so no other codeword fits.
Worked example 9.1.7
(Locating one error by trial interpolation)
Suppose is received with no erasures and at most one error. Interpolating the values at gives again, and also matches the value at ; it differs from the received word only at , so by the theorem it is the unique answer. An interpolant through a set containing the bad position is rejected. Through the conditions and give , , so , with and . It disagrees with the received word at two positions, too many for one error.
Common mistake
(An error is not as cheap as an erasure)
The rule would wrongly claim that one error and one erasure are always handled when . Take the word and the codeword of . Erase the last position and receive . The visible values differ from the word only at and from the word only at , so both are consistent with one error. The correct requirement is , which fails here since .
Counterexample mode
Beyond the guaranteed radius
Let . Its word is . If is received after transmitting the word, two symbols were corrupted. This received word is distance two from the transmitted word but distance one from the word. A nearest-codeword rule therefore selects the wrong word. Knowing the permitted error bound matters; redundancy alone does not identify every corruption.
A different use of the same interpolation
In threshold secret sharing, random coefficients hide a secret from too few shares. Here the entire coefficient vector is the message, and no random masking has been added. In particular, including as an evaluation point reveals directly. The distance proof provides error resilience, not confidentiality. Practical deployments also need a specified encoding, decoder and integrity model; none is supplied by the distance formula alone.
Exercises
Quick check
(Over , evaluate at and find for .)
Solution · Answer
The word is , and .
Quick check
(In that code, are one error and one erasure covered by the uniqueness guarantee? Are two erasures covered?)
Solution · Answer
One error and one erasure give , so the theorem gives no guarantee. Two erasures give and are covered.
Quick check
(For , , find the minimum distance and the largest number of erasures always recoverable without errors.)
Solution · Answer
and erasures are recoverable, assuming a field with at least six distinct evaluation points.
Quick check
(Why does including as an evaluation point rule out using this unmasked encoding to hide from a holder of that coordinate?)
Solution · Answer
The corresponding symbol is , so it directly reveals that coefficient.
Further reading
MIT OpenCourseWare, Lecture 20: Reed–Solomon Codes discusses polynomial evaluation, minimum distance and decoding.