Reed-Solomon codes

The formula

The parameters, for an RS(n, k) code over the field GF(2^m):

n ≤ 2^m − 1        d = n − k + 1        t = ⌊(n − k)/2⌋

Reading: block length n symbols (each symbol is m bits), k of them data, and the code corrects any t symbol errors anywhere in the block. The workhorse RS(255, 223) over GF(256) carries 223 data bytes, 32 parity bytes, and fixes 16 corrupted bytes per block.

The error–erasure tradeoff:

2E + S ≤ n − k

Reading: an error at an unknown location costs two parity symbols; an erasure — a symbol you already know is bad — costs one. Tell the decoder where the damage is and its capacity doubles, up to n − k = 32 erasures on RS(255, 223).

The original 1960 definition — a codeword is a polynomial, sampled:

c = ( p(α⁰), p(α¹), ..., p(α^(n−1)) )       p(x) = m₀ + m₁·x + ... + m_(k−1)·x^(k−1)

Reading: pack the k data symbols into a polynomial of degree less than k, then evaluate it at n distinct field points. Any k clean samples pin down the polynomial; the other n − k samples are pure redundancy.

The generator-polynomial (BCH) view every hardware encoder actually uses:

g(x) = (x − α)(x − α²)···(x − α^(n−k))
c(x) = m(x)·x^(n−k) + [ m(x)·x^(n−k) mod g(x) ]

Reading: shift the message left by n − k symbols, divide by g(x), and append the remainder — long division in GF(2^m), where addition is XOR. Data rides through untouched (systematic), parity trails behind.

The burst-sizing rule of thumb:

a burst of b bits spans at most ⌈(b + m − 1)/m⌉ consecutive m-bit symbols

Reading: with 8-bit symbols, a 121-bit burst touches at most 16 bytes however it straddles the boundaries — so one RS(255, 223) block swallows it whole. At 122 bits the worst-case alignment needs a 17th symbol and you're out of parity.

Where you meet it

The telemetry ground station. CCSDS deep-space and satellite downlinks frame their data in RS(255, 223) blocks, usually interleaved four or five deep, wrapped around a rate-1/2 convolutional inner code ^[1]^[7]. The frame processor's status page shows corrected-symbol counts per block; watching that number climb from 2 toward 16 during a low-elevation pass is your earliest warning the link margin is going, well before frames actually drop.
The asset tag on the fixture. QR codes carry Reed-Solomon parity at four selectable levels — L, M, Q, H — restoring roughly 7%, 15%, 25%, or 30% of the codewords ^[6]. A cal sticker printed at level H keeps scanning after a year of solvent wipes and forklift scuffs. If your labels die young, the fix is one dropdown in the label software, not a better printer.
The test-data archive. RAID-6 survives two simultaneous drive failures because its second parity stripe is Reed-Solomon-style arithmetic over GF(256) ^[11]. When the array rebuilds overnight after a controller hiccup and nobody loses the vibration data, that's an erasure decode — the array knows exactly which drives died, so each failure costs one parity unit, not two.
The RF bench. DVB-T broadcast television and plenty of legacy satellite modems run RS(204, 188) — the 255-byte code shortened, 8 correctable bytes per packet ^[10]. When a BER tester shows a raw channel at 10⁻⁴ and the transport stream comes out clean, the RS decoder is quietly earning its gate count.

How it works

The whole trick is that Reed-Solomon corrects symbols, not bits. An 8-bit symbol with one flipped bit and a symbol with all eight flipped are the same single error to the decoder — verified directly: XOR 0xFF into one byte of an RS(255, 223) codeword and it decodes clean, same as a one-bit flip. That's what makes RS the burst-error workhorse: a contiguous 121-bit burst lands in at most 16 consecutive bytes no matter how it straddles the boundaries, so one code block absorbs it entirely. Scatter those same 121 flipped bits randomly across the block instead, and each lone bit burns a whole symbol's worth of correction — the code drowns. RS is superb against clustered damage and mediocre against salt-and-pepper noise. That asymmetry drives two standard moves:

Concatenate. Deep-space links put a convolutional code inside and RS outside. A Viterbi decoder fails in short bursts — exactly the error pattern RS eats for free ^[3]^[7]. Modern ground-up designs (DVB-S2, 5G) went to LDPC instead, which handles random errors near the Shannon limit; RS survives where burst structure, block framing, or silicon heritage favors it.
Interleave. Spread each codeword's symbols across time or across the disc and a physical burst turns into a few symbols per codeword. The CD's CIRC runs two shortened RS codes over GF(256) — a (32, 28) and a (28, 24), each correcting 2 symbols — cross-interleaved so the first decoder fixes small hits and flags what it can't as erasures for the second ^[1]^[3]^[5]. Result: full correction of 4,000-bit bursts, about 2.5 mm of track, and interpolated concealment out to roughly 12,000 bits ^[1]^[5].

The code is maximum distance separable: d = n − k + 1 meets the Singleton bound with equality, so no code of the same length and size has more distance ^[1]^[3]. Every parity symbol you pay for buys exactly one symbol of distance. That's also why erasure performance is so good — any k intact symbols of the n reconstruct the data, period, which is the property RAID and modern cloud erasure coding are built on.

The gotcha worth knowing cold: beyond t errors, the decoder does not degrade gracefully. Sometimes it declares failure — but sometimes the corrupted word lands within distance t of a different valid codeword and the decoder confidently returns wrong data. How often depends on the code, hard. At t + 1 errors, a bounded-distance decoder on a full-length code miscorrects with probability approaching 1/t! — measured on full-length RS(255, 251), t = 2, with 3 injected errors: 986 of 2000 trials decoded silently to garbage. A coin flip, right at the predicted 1/2! = 0.5. Two things buy that risk down. More parity: for the t = 16 workhorse, 1/t! is on the order of 10⁻¹³ — negligible. And shortening: rerun the same experiment on a shortened RS(20, 16) over GF(256), still t = 2, and only 2 of 2000 trials miscorrected, with 1998 flagged as failures — the Chien search must land every error root inside the short valid position range, and almost all wrong-codeword candidates point outside it. Either way the miscorrection rate grows as parity shrinks, and no decoder status flag is a guarantee — which is why real systems keep a CRC inside the RS payload as a final check rather than trusting "decode succeeded."

The mistake people make in reviews: reading "corrects 16 errors" as 16 bit errors. It's 16 symbols — up to 128 bit errors if they cluster perfectly, as few as 16 if they don't. Quote RS capability in symbols or not at all. Second trap: n ≤ 255 for 8-bit symbols is a hard ceiling from the field size; longer blocks mean bigger symbols or (usually) shortening a 255-code down, the way (204, 188) and every QR block do — shortening costs nothing in distance.

Decoding runs a fixed pipeline you'll see named in every FPGA IP core datasheet: compute syndromes, run Berlekamp-Massey (or the Euclidean method) to find the error-locator polynomial, Chien search for the error positions, Forney's formula for the error values ^[1]^[3]. Encoding is a shift register with a handful of GF multipliers; the asymmetry — trivial encoder, serious decoder — is why the spacecraft carries the cheap half and the ground station carries the racks.

History

Irving Reed and Gustave Solomon were staff members at MIT Lincoln Laboratory when their five-page paper, "Polynomial Codes over Certain Finite Fields," ran in the Journal of the Society for Industrial and Applied Mathematics in June 1960 ^[1]^[2]^[3]^[4]. The construction was the evaluation map above — take a polynomial through your data, sample it oversampled — and it was, provably, as good as a block code can be. What it lacked was any practical way to decode: their own proposal solved simultaneous equations by brute force, workable only for toy codes ^[3]. For most of a decade the codes sat as elegant theory while decoding advanced in steps — Peterson's direct-solution algorithm for binary BCH codes in 1960, extended to nonbinary codes by Gorenstein and Zierler in 1961 ^[1]^[3]. The breakthrough came when Elwood Berlekamp demonstrated an efficient algorithm in 1967, and James Massey showed in 1969 that the problem was equivalent to synthesizing the shortest linear feedback shift register generating a given sequence — hardware engineers know how to build shift registers ^[1]^[3]. Sugiyama and colleagues added the Euclidean-algorithm route in 1975 ^[1]^[3].

Then the hardware caught up with the math. Voyager carried a concatenated RS(255, 223)-plus-convolutional system held in reserve as too risky for the primary Jupiter–Saturn mission; it was switched on for the extended mission, and the first Reed-Solomon-encoded image from deep space was a photograph of Uranus ^[3]^[7]. That pairing became the CCSDS standard for deep-space telemetry ^[7]. The same decade put RS in every living room: the compact disc's cross-interleaved pair shipped by the hundreds of millions, making Reed-Solomon, by common claim, the most-deployed error-correcting code on Earth ^[3]^[4]. Reed and Solomon shared the IEEE Masaru Ibuka Consumer Electronics Award in 1995 for it ^[8]^[9]. Not bad for five pages.

Related tools

/tools/link-budget — coding gain from RS is a line item in the budget; it's the dB you get back for the bandwidth the parity costs
/tools/free-space-path-loss — the loss that decides whether the corrected-symbol counter reads 2 or 15
/tools/thermal-noise-floor — sets the raw channel error rate the decoder has to live with
/tools/snr-enob — the analog-side error budget upstream of every digital check

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →