Introduction

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.

Erase and Rebuild

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">Your message is <b>3 numbers</b>. We treat them as a degree-2
polynomial and sample it at <b>7 points</b> (3 originals + 4 redundant). Click any
sample to <b>erase</b> it — like a scratch or a lost packet. As long as any 3
survive, interpolation rebuilds the message exactly.</p>
<div class="msg">
  <span class="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">Encode</button>
</div>
<div id="codeword" class="codeword"></div>
<div class="status" id="status">Encode a message, then erase samples.</div>
<div class="btns">
  <button id="recover" type="button">Recover message</button>
  <button id="reset" type="button" class="ghost">Restore all</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Reed-Solomon erasure coding (Reed & Solomon, 1960), shown over a prime field.
// A message of k=3 symbols defines a degree-2 polynomial p(x)=m0+m1*x+m2*x^2.
// We evaluate it at n=7 distinct x's. Any k=3 surviving samples uniquely
// determine p (Lagrange interpolation), so up to n-k=4 erasures are recoverable.
const P = 97;              // prime field GF(97): all arithmetic is mod 97
const K = 3, N = 7;
const XS = [1, 2, 3, 4, 5, 6, 7];   // n distinct evaluation points
let msg = [7, 11, 3];
let erased = new Set();    // indices (0..6) of erased samples
let codeword = [];

const mod = (a) => ((a % P) + P) % P;
function inv(a){ // modular inverse via Fermat (P prime): a^(P-2) mod P
  let r = 1, b = mod(a), e = P - 2;
  while (e > 0){ if (e & 1) r = mod(r * b); b = mod(b * b); e >>= 1; } return r;
}
function evalPoly(coef, x){ // Horner over the field
  let acc = 0; for (let i = coef.length - 1; i >= 0; i--) acc = mod(acc * x + coef[i]); return acc;
}
// Lagrange interpolation: recover p(0..k-1) coefficients value at the message
// points. We just need the message back, i.e. p evaluated to its coefficients;
// simplest is to interpolate the value of p at the k "message x's" — but here the
// message IS the coefficients, so we reconstruct coefficients by solving via the
// value of p at x=XS of the originals. Instead, recover by interpolating p and
// reading coefficients: interpolate p(t) at K known (x,y), then evaluate to get
// the original coefficients by matching the encoding x's of the first K samples.
function recoverMessage(samples){ // samples: array of {x,y}, length >= K
  const pts = samples.slice(0, K);
  // Reconstruct the original coefficients by interpolating the polynomial value
  // at the ORIGINAL message-encoding points XS[0..K-1], then those values are the
  // codeword's first K symbols; but the message equals the coefficients, so we
  // instead solve the Vandermonde system implicitly through Lagrange evaluation
  // at the K encoding nodes and then invert. To keep it simple and exact, we
  // interpolate p at the K message x-positions and run forward/back transforms:
  // p(x) = sum_j y_j * prod_{m!=j} (x - x_m)/(x_j - x_m)
  // Expand to coefficients in [c0,c1,c2].
  let coef = [0, 0, 0];
  for (let j = 0; j < pts.length; j++){
    // basis poly L_j(x) = prod_{m!=j} (x - x_m)/(x_j - x_m), as coefficient array
    let basis = [1]; let denom = 1;
    for (let m = 0; m < pts.length; m++){
      if (m === j) continue;
      // multiply basis by (x - x_m): shift + subtract
      const nb = new Array(basis.length + 1).fill(0);
      for (let t = 0; t < basis.length; t++){
        nb[t + 1] = mod(nb[t + 1] + basis[t]);
        nb[t] = mod(nb[t] - basis[t] * pts[m].x);
      }
      basis = nb;
      denom = mod(denom * (pts[j].x - pts[m].x));
    }
    const scale = mod(pts[j].y * inv(denom));
    for (let t = 0; t < basis.length; t++) coef[t] = mod(coef[t] + basis[t] * scale);
  }
  return coef; // [m0, m1, m2]
}

function encode(){
  msg = [0,1,2].map(i => mod(Number(document.getElementById('m'+i).value) || 0));
  [0,1,2].forEach(i => document.getElementById('m'+i).value = msg[i]);
  codeword = XS.map(x => ({ x, y: evalPoly(msg, x) }));
  erased.clear();
  render();
  setStatus('Encoded. Click samples to erase up to 4 of them.', '');
  document.getElementById('result').textContent = '';
}
function render(){
  const c = document.getElementById('codeword'); c.innerHTML = '';
  codeword.forEach((s, i) => {
    const d = document.createElement('div');
    const isOrig = i < K;
    d.className = 'sample' + (isOrig ? ' orig' : '') + (erased.has(i) ? ' erased' : '');
    d.innerHTML = '<span class="x">x=' + s.x + '</span><span class="y">' +
                  (erased.has(i) ? '✗' : s.y) + '</span>';
    d.addEventListener('click', () => {
      erased.has(i) ? erased.delete(i) : erased.add(i);
      render(); setStatus(fmt('%survivors% of 7 samples survive.', { survivors: survivors() }), survivors() >= K ? 'ok' : 'bad');
      document.getElementById('result').textContent = '';
    });
    c.appendChild(d);
  });
}
const survivors = () => N - erased.size;
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function recover(){
  if (survivors() < K){
    setStatus(fmt('Only %survivors% samples left — need at least %K%. Message lost.', { survivors: survivors(), K: K }), 'bad');
    document.getElementById('result').textContent = '';
    return;
  }
  const alive = codeword.filter((_, i) => !erased.has(i));
  const rec = recoverMessage(alive);
  const ok = rec.every((v, i) => v === msg[i]);
  setStatus(ok ? fmt('✓ Recovered from %survivors% survivors!', { survivors: survivors() }) : '✗ Mismatch.', ok ? 'ok' : 'bad');
  document.getElementById('result').textContent = fmt('Recovered message: [ %rec% ]', { rec: rec.join(', ') });
  console.log('survivors', survivors(), 'recovered', rec, 'original', msg);
}

document.getElementById('encode').addEventListener('click', encode);
document.getElementById('recover').addEventListener('click', recover);
document.getElementById('reset').addEventListener('click', () => {
  erased.clear(); render(); setStatus('All samples restored.', ''); document.getElementById('result').textContent = '';
});
encode();
Result
Console

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.

The Real Math

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(282^{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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reed-solomon/Content licensed under CC BY-NC 4.0.