Reed-Solomon

Reed-Solomon codes are a class of non-binary cyclic error-correcting codes invented by Irving Reed and Gustave Solomon in 1960. Unlike binary codes such as the Hamming code, Reed-Solomon codes operate on symbols drawn from a finite field (typically GF(2⁸)), making them exceptionally effective at correcting burst errors — contiguous sequences of corrupted bits — that are common in storage media and wireless channels.

The key insight of Reed-Solomon codes is to treat the message as a polynomial over a finite field and to encode it by evaluating the polynomial at additional points. The resulting codeword can correct up to t errors and 2t erasures provided the code is constructed with sufficient redundancy. This algebraic structure made Reed-Solomon codes the workhorse of digital communication for decades: they protect data on CDs, DVDs, QR codes, deep-space transmission protocols, and modern solid-state drives.

The connection to error correction as a systems principle is direct. Reed-Solomon codes demonstrate that the optimal strategy for noise resilience depends on the statistical structure of the noise itself. Where errors are random and independent, binary codes suffice; where errors cluster in bursts — as they do in physical reality — algebraic codes over larger alphabets provide superior protection. The choice of code is thus a choice about the nature of the environment, not merely a technical optimization.