Reed–Solomon Evaluation Code

Recover a polynomial message from finite-field evaluations corrupted at one position.

Reed–Solomon Evaluation Code

Reed–Solomon codes protect digital data from errors by evaluating polynomials over a finite field. A short message forms the coefficients of a polynomial, which is then evaluated at multiple points. Because low-degree polynomials cannot intersect too many times without being identical, we can uniquely identify the original polynomial even if some evaluation points are corrupted.

Worked Example: Encoding and Error Correction

Let the finite field be GF(7), and consider the message [1, 2, 3]. This defines the polynomial:
M(x) = 1 + 2x + 3x² (mod 7)

We evaluate M(x) at five points x = 0, 1, 2, 3, 4 to form the codeword:

M(0) = 1 + 0 + 0 = 1
M(1) = 1 + 2(1) + 3(1) = 6
M(2) = 1 + 2(2) + 3(4) = 1 + 4 + 12 = 17 ≡ 3 (mod 7)
M(3) = 1 + 2(3) + 3(9) = 1 + 6 + 27 = 34 ≡ 6 (mod 7)
M(4) = 1 + 2(4) + 3(16) = 1 + 8 + 48 = 57 ≡ 1 (mod 7)

The encoded word is [1, 6, 3, 6, 1]. Suppose an error of +1 occurs at position x = 2, so the received word is [1, 6, 4, 6, 1]. We check all possible 343 polynomials and find that M(x) = 1 + 2x + 3x² is the only polynomial that matches 4 out of 5 points. Therefore, the decoded coefficients are [1, 2, 3] and the Hamming distance is 1.

Experiment

Use the interactive module to explore how error correction handles different levels of corruption.

Select the Message "General". Observe that the encoded word is [1, 6, 3, 6, 1].
Set the Error position to "2" and Error amount to "1". The received word changes to [1, 6, 4, 6, 1].
Observe the Decoded coefficients remain [1, 2, 3], matching our worked example. The nearest Hamming distance is 1.
Try selecting Error position "None" to see a clean transmission.

Limitations and Assumptions

The interactive visualization is restricted to GF(7) and messages of exactly length 3. Real Reed-Solomon implementations often use GF(256) or GF(65536) to process bytes, rather than a small prime field. Additionally, this module uses a brute-force oracle that evaluates all 343 possible messages to find the closest codeword. Practical systems use algebraic decoding algorithms like Berlekamp-Welch or Berlekamp-Massey, which scale efficiently to much larger block lengths and higher degrees.

References

For a comprehensive introduction to error-correcting codes and polynomial interpolation over finite fields, see:

CMU Lectures on Error Correcting Codes (Part 2) by Guy Blelloch (Fall 2008). This resource details Reed-Solomon encoding and algebraic decoding procedures.

Reed–Solomon Evaluation Code