Reed-Solomon

How Reed-Solomon Works

Reed-Solomon is an error-correcting code. With 2t parity symbols, it can detect and correct up to t unknown errors — it figures out where the corruption is and what the correct value should be. This is different from erasure coding, which recovers missing data when you already know which chunks are gone.

The algorithm works in four stages:

1. Syndromes — evaluate the received polynomial at 2t known points. If all zero, no errors. Otherwise the syndrome values encode information about where and what the errors are.
2. Berlekamp-Massey — finds the error locator polynomial Λ(x) from the syndromes. The degree of Λ tells you how many errors occurred.
3. Chien search — brute-force evaluate Λ(α⁻ⁱ) at every position to find which positions have errors (roots of Λ).
4. Forney algorithm — compute the error magnitudes using the error evaluator polynomial Ω(x) = S(x)·Λ(x) mod x²ᵗ and the formal derivative Λ'(x).

All the math happens over GF(256) — the same Galois field used in the erasure coding lab. Every byte value (0–255) is an element of the field, and operations like multiply, divide, and inverse are defined so that there's no rounding or overflow.

Reed-Solomon is everywhere: QR codes, CDs and DVDs, deep-space communication (Voyager, Mars rovers), RAID 6 storage, and digital television. Anywhere data might get corrupted in transit or storage, RS codes are likely involved.