Reed-Solomon Codes

Scratch a CD, smudge a QR code, or lose a burst of packets streaming from a probe near Saturn — and the data still arrives perfect. That is not luck. It is Reed-Solomon coding, invented in 1960 by Irving Reed and Gustave Solomon at MIT's Lincoln Laboratory.

The idea is almost magical in its simplicity. Instead of storing your message as raw bytes, you treat the bytes as the coefficients of a polynomial and then write down the value of that polynomial at more points than you strictly need. Those extra points are pure redundancy — and they are exactly what lets you rebuild any symbols that get lost or corrupted.

Two points define a line. Three define a parabola. The deep fact Reed-Solomon exploits is that any k points pin down a unique degree-(k−1) polynomial — so if you publish n points, you can lose up to n−k of them and still recover the original curve, and with it, your message.

Here is a tiny message of 3 numbers. We treat them as a degree-2 polynomial and sample it at 7 points — the 3 originals plus 4 redundant ones. Click any sample to erase it, simulating a scratch or a lost packet.

<p class="hint">{{hint}}</p>
<div class="msg">
  <span class="lbl">{{lbl_message}}</span>
  <input id="m0" type="number" min="0" max="96" value="7">
  <input id="m1" type="number" min="0" max="96" value="11">
  <input id="m2" type="number" min="0" max="96" value="3">
  <button id="encode" type="button">{{btn_encode}}</button>
</div>
<div id="codeword" class="codeword"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="recover" type="button">{{btn_recover}}</button>
  <button id="reset" type="button" class="ghost">{{btn_restore}}</button>
</div>
<div id="result" class="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.msg { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; margin: .4rem 0 .8rem; }
.lbl { font-weight: 600; font-size: .9rem; }
.msg input { width: 56px; padding: .35rem; font: 600 14px ui-monospace, monospace;
             border: 1px solid #cdd9e3; border-radius: 6px; text-align: center; }
.codeword { display: grid; grid-template-columns: repeat(7, 1fr); gap: 6px; margin: .5rem 0; }
.sample { display: flex; flex-direction: column; align-items: center; padding: .4rem 0;
          border-radius: 8px; cursor: pointer; user-select: none; transition: all .12s;
          background: #e8eef3; border: 1px solid #cdd9e3; }
.sample .x { font-size: .7rem; color: #5a7088; }
.sample .y { font: 700 16px ui-monospace, monospace; color: #1d3557; }
.sample.orig { background: #dceede; border-color: #b6d8bc; }
.sample:hover { filter: brightness(.96); }
.sample.erased { background: #f3d6d9; border-color: #e2a9b0; }
.sample.erased .y { color: #c92f3c; text-decoration: line-through; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { margin-top: .6rem; font: 600 15px ui-monospace, monospace; }

// Code not found

Notice the resilience. As long as any 3 of the 7 samples survive, the demo runs Lagrange interpolation through the survivors, recovers the exact polynomial, and reads your message straight back. Erase a fourth point, though, and there is no longer a unique curve — the message is gone. That sharp threshold, k survivors needed out of n sent, is the whole engineering trade-off in one picture.

How well does Reed-Solomon work? The answer is unusually clean: it is provably optimal, and it is solved — Reed and Solomon settled the construction in 1960, and fast decoders followed within a decade.

• Data is a polynomial. A message of k symbols becomes a degree-(k−1) polynomial; the codeword is its value at n distinct points.
• Any k points are enough. By the uniqueness of polynomial interpolation, any k of the n samples reconstruct the polynomial. So the code tolerates up to n−k erasures (known-missing symbols) and up to (n−k)/2 errors (silently wrong symbols).
• It is an MDS code. Reed-Solomon meets the Singleton bound with equality — no code with the same length and redundancy can ever recover from more failures. You cannot do better.
• Everything is efficient. Encoding is polynomial evaluation; erasure decoding is Lagrange interpolation; error decoding uses the Berlekamp-Massey algorithm. All run in low-degree polynomial time over a finite field (so arithmetic never overflows).

The one subtlety is the finite field: real implementations work in arithmetic mod a prime or in GF($2^{8}$), where bytes have exact addition and multiplication. That keeps the "points on a curve" picture mathematically exact while every symbol stays a single byte.

"Survive damage you cannot predict" is one of the most universal demands in engineering, and Reed-Solomon is its quiet workhorse:

• Optical media: CDs, DVDs and Blu-ray discs use Reed-Solomon so a scratch or fingerprint never costs you a note or a frame.
• QR codes: that smudge-tolerant square you scan daily recovers from up to ~30% damage thanks to Reed-Solomon blocks.
• Deep space: Voyager, Mars rovers and other NASA missions wrap telemetry in Reed-Solomon so faint, noisy signals still decode on Earth.
• Storage and cloud: RAID-6 and distributed systems (from data centers to QR-style backups) use Reed-Solomon erasure coding to survive whole disk or node failures with minimal overhead.

Understand Reed-Solomon and you have met erasure coding — the same redundancy-through-redundancy idea that protects everything from a compressed file on disk to a streaming packet crossing the solar system.

Reed-Solomon turns a schoolroom fact — a handful of points determines a curve — into one of the most dependable tools in all of engineering. Sample your message at a few extra points, and you can lose or scramble a chunk of them and still rebuild the original exactly. No code with the same redundancy can do better; the math literally hits the wall of what is possible.

So the next time a scratched disc still plays, a battered QR code still scans, or a whisper from another planet arrives flawless, remember the trick: your data was never just bytes. It was a polynomial, and a polynomial is remarkably hard to lose. For the broader story of squeezing and protecting data, see Squeezing Data.