Reed-Solomon Correctable Errors

Irving Reed and Gustave Solomon published this in the Journal of the Society for Industrial and Applied Mathematics in 1960, on five pages. The construction treats $k$ data symbols as the coefficients of a polynomial and transmits its value at $n$ distinct points; any $k$ of those $n$ values determine the polynomial uniquely, so the code tolerates the loss of $n - k$ of them. That property makes it a maximum distance separable code — it meets the Singleton bound exactly, so no code of the same length and dimension can do better. Very few code families manage that.

The correction capability follows from the minimum distance $d = n - k + 1$. Two codewords differ in at least $d$ positions, so a received word within $\lfloor (d-1)/2 \rfloor$ positions of a codeword is unambiguously closer to it than to any other — hence $t = \lfloor (n-k)/2 \rfloor$. An error at an unknown position costs two parity symbols: one to find it and one to fix it. An erasure, where the position is already known to be bad, costs only one, so the same code corrects $2t$ erasures, or any mix satisfying $2(\text{errors}) + (\text{erasures}) \le n - k$. That two-for-one is why real systems work so hard to pass position information down to the decoder, and it is exactly what the CD's CIRC scheme does between its two Reed-Solomon layers.

The count is in symbols, not bits, and this is the property that makes the code famous. RS(255,223) works over $GF(256)$, where each symbol is a byte, so those 16 correctable errors may be 16 wholly mangled bytes — 128 bits, if they all went bad — anywhere in the codeword. A burst of noise that destroys eight consecutive bits damages at most two symbols. That is why Reed-Solomon codes ended up in every medium where damage arrives in clumps: scratches on a CD, dust on a QR code, fading on a satellite link, a bad block on a disk. Bit-oriented codes like Hamming handle scattered single-bit errors and fall apart on bursts; Reed-Solomon is the other way round, which is why the two are often stacked.

The symbol size caps the codeword. A code over $GF(2^m)$ can have at most $n = 2^m - 1$ symbols, so byte symbols stop at 255 — which is where the ubiquitous RS(255,k) family comes from. Longer messages are split across codewords and interleaved, so that a burst which would overwhelm one codeword is spread thinly across several. Interleaving is not part of this arithmetic and it is most of what makes a real system work.

The code rate $R = k/n$ is the price. RS(255,223), the CCSDS deep-space standard that brought the Voyager images home, spends 12.5% of the channel to correct 16 symbol errors per block. A QR code offers four rates from about 93% down to 70%, buying roughly 7% to 30% damage tolerance — which is why a QR code still scans with a logo pasted over the middle of it. Choosing the rate is a straight trade between throughput and how bad you expect the channel to get, and the usual mistake is optimism.

One caution about the failure mode. Past $t$ errors a decoder usually detects that something is wrong and declares failure, which is the behaviour you want. But not always: with enough errors the received word can land closer to a different valid codeword, and the decoder will then hand back wrong data with complete confidence. The probability is small and it is not zero, which is why a checksum outside the error-correcting code is worth keeping. Correction and detection are different jobs, and a code that is doing all it can at correction has spent its margin for detection.