Reed-Solomon Code

A Reed-Solomon code is a non-binary cyclic error-correcting code invented by Irving Reed and Gustave Solomon at MIT Lincoln Laboratory in 1960. Unlike binary codes that operate on individual bits, Reed-Solomon codes work on blocks of symbols drawn from a finite field, treating the message as coefficients of a polynomial. The encoded message is a set of evaluations of this polynomial at distinct points. Because a degree-k polynomial is uniquely determined by k+1 points, the receiver can reconstruct the original polynomial even if some evaluations are corrupted — provided the number of errors does not exceed half the number of redundant symbols.

This algebraic structure makes Reed-Solomon codes exceptionally good at correcting burst errors: contiguous sequences of corrupted bits that overwhelm codes designed for random independent errors. The Voyager spacecraft used Reed-Solomon codes to transmit images from the outer planets. The codes are also embedded in everyday technology: CDs, DVDs, Blu-ray discs, QR codes, and RAID-6 storage systems all rely on Reed-Solomon error correction to recover data from scratches, dust, and drive failures.

The connection between Reed-Solomon decoding and the Fast Fourier Transform is deep: decoding can be performed using FFT-like algorithms over finite fields, making efficient implementation possible. The codes are also the foundation of Reed-Solomon erasure codes, which are used in distributed storage systems to ensure that data can be reconstructed from any sufficiently large subset of fragments.