Introduction

Every time data travels — through a satellite link, a scratched CD, a cellular tower — some bits arrive wrong. Error-correcting codes are the invisible shield that repairs the damage: they add carefully chosen redundancy so a decoder can recover the original message even when the channel flips some symbols.

The classical recipe, called unique decoding, works beautifully as long as the number of corrupted symbols stays below half the minimum distance dd of the code. Cross that threshold and two codewords become equally plausible; the decoder is stuck.

In 1997, Madhu Sudan broke that wall. He showed that, instead of demanding a unique answer, you can ask for a short list of all codewords within a larger radius. Venkatesan Guruswami and Sudan refined the idea in 1998 into the celebrated Guruswami-Sudan algorithm, which efficiently list-decodes Reed-Solomon codes up to the Johnson bound — far beyond d/2d/2. The result earned Guruswami the 2002 Packard Fellowship and reshaped coding theory permanently.

Try It: Recover Candidates

The demo below works with a tiny Reed-Solomon-like code over the alphabet {0,1,…,6}\{0,1,\dots,6\}. Each codeword is a degree-1 polynomial f(x)=ax+bf(x) = ax + b evaluated at positions 0,1,2,3,4,5,60,1,2,3,4,5,6 — so each codeword has length 7 and minimum distance 6.

Use the sliders to inject errors into a received word, then click Unique decode or List decode to see which candidates survive.

<!-- List-decoding interactive demo. -->
<p class="hint">Choose a codeword (slope <b>a</b> and intercept <b>b</b>) and inject up to 5 errors. Then try <b>unique decoding</b> (fails past the half-distance) or <b>list decoding</b> (returns all nearby candidates). The highlighted candidate is the original codeword.</p>
<div class="panel">
  <div class="row">
    <span class="label">Slope a</span>
    <input type="range" id="sliderA" min="0" max="6" value="2" class="slider">
    <span id="valA" class="val">2</span>
  </div>
  <div class="row">
    <span class="label">Intercept b</span>
    <input type="range" id="sliderB" min="0" max="6" value="1" class="slider">
    <span id="valB" class="val">1</span>
  </div>
</div>
<div class="panel">
  <div class="row">
    <span class="label">Errors injected</span>
    <input type="range" id="sliderE" min="0" max="5" value="2" class="slider">
    <span id="valE" class="val">2</span>
  </div>
</div>
<div id="codeword-row" class="coderow"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnUnique" type="button">Unique decode</button>
  <button id="btnList" type="button">List decode</button>
  <button id="btnReset" type="button" class="ghost">New errors</button>
</div>
<div id="result" class="result"></div>

/* Styles for the list-decoding demo. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panel { background: #f4f7fa; border: 1px solid #dde3ea; border-radius: 8px; padding: .6rem .8rem; margin-bottom: .5rem; }
.row { display: flex; align-items: center; gap: .6rem; margin: .2rem 0; }
.label { font-size: .83rem; color: #555; min-width: 80px; }
.slider { flex: 1; accent-color: #1d3557; }
.val { font: 700 .9rem ui-monospace, monospace; color: #1d3557; min-width: 18px; }
.coderow { display: flex; gap: 4px; margin: .5rem 0; flex-wrap: wrap; }
.sym { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
       font: 700 15px ui-monospace, monospace; border-radius: 6px; }
.sym.clean { background: #d4edda; color: #155724; border: 1px solid #b1dfbb; }
.sym.corrupt { background: #f8d7da; color: #721c24; border: 1px solid #f5c6cb; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: .85rem; line-height: 1.6; }
.result b { color: #1d3557; }
.candidate { background: #eef2f7; border-radius: 6px; padding: .2rem .5rem; display: inline-block; margin: .15rem .1rem;
             font: 600 .82rem ui-monospace, monospace; }
.candidate.match { background: #d4edda; color: #155724; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// List-decoding demo: degree-1 polynomials over GF(7).
// Work in GF(7): arithmetic mod 7.
const Q = 7;
const mod7 = x => ((x % Q) + Q) % Q;

// Evaluate polynomial f(x) = a*x + b at positions 0..6 in GF(7).
function evalPoly(a, b) {
  const cw = [];
  for (let x = 0; x < Q; x++) cw.push(mod7(a * x + b));
  return cw;
}

// Build all 49 codewords (a in 0..6, b in 0..6).
function buildCodebook() {
  const book = [];
  for (let a = 0; a < Q; a++)
    for (let b = 0; b < Q; b++)
      book.push({ a, b, cw: evalPoly(a, b) });
  return book;
}
const CODEBOOK = buildCodebook();

// Hamming distance between two equal-length arrays.
function hamming(u, v) {
  let d = 0;
  for (let i = 0; i < u.length; i++) if (u[i] !== v[i]) d++;
  return d;
}

function getParams() {
  return {
    a: parseInt(document.getElementById('sliderA').value),
    b: parseInt(document.getElementById('sliderB').value),
    e: parseInt(document.getElementById('sliderE').value)
  };
}

// Inject numErrors symbol errors at random distinct positions.
function corrupt(cw, numErrors) {
  const r = [...cw];
  const pos = [];
  while (pos.length < numErrors) {
    const p = Math.floor(Math.random() * Q);
    if (!pos.includes(p)) pos.push(p);
  }
  pos.forEach(p => { r[p] = mod7(r[p] + 1 + Math.floor(Math.random() * (Q - 1))); });
  return { received: r, errPos: pos };
}

let lastReceived = null;
let lastA = null, lastB = null;

function renderCodeword(cw, received, errPos) {
  const row = document.getElementById('codeword-row');
  row.innerHTML = '';
  for (let i = 0; i < Q; i++) {
    const d = document.createElement('div');
    d.className = 'sym ' + (received && received[i] !== cw[i] ? 'corrupt' : 'clean');
    d.textContent = received ? received[i] : cw[i];
    d.title = 'x=' + i;
    row.appendChild(d);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function prepare() {
  const { a, b, e } = getParams();
  const cw = evalPoly(a, b);
  const { received, errPos } = corrupt(cw, e);
  lastReceived = received; lastA = a; lastB = b;
  renderCodeword(cw, received, errPos);
  document.getElementById('result').innerHTML = '';
  // Show initial ready status.
  setStatus('Ready — click Unique decode or List decode.', '');
}

// Unique decoding: accept only if exactly 1 codeword within threshold.
function uniqueDecode() {
  if (!lastReceived) { prepare(); return; }
  const { e } = getParams();
  const threshold = Math.floor((Q - 1) / 2); // floor((n-k)/2) = floor(6/2) = 3 for this code, but we use floor((Q-1)/2)=3
  const res = document.getElementById('result');
  if (e > threshold) {
    setStatus('Unique decoding failed: too many errors.', 'bad');
    res.innerHTML = fmt('<b>Unique-decoding radius:</b> %threshold% &lt; errors injected: %e%.', { threshold: threshold, e: e });
    return;
  }
  // Count codewords within the unique-decoding radius.
  const cands = CODEBOOK.filter(({ cw }) => hamming(cw, lastReceived) <= threshold);
  if (cands.length === 1) {
    const { a, b } = cands[0];
    setStatus('Unique decoding succeeded — one codeword found.', 'ok');
    res.innerHTML = fmt('<b>Decoded codeword:</b> f(x) = %a%x + %b% &nbsp;(a=%a%, b=%b%)', { a: a, b: b });
  } else {
    setStatus('Ambiguous — multiple codewords at this radius.', 'bad');
    res.innerHTML = fmt('<b>Candidates found:</b> %length%', { length: cands.length });
  }
}

// List decoding: collect ALL codewords within listRadius.
function listDecode() {
  if (!lastReceived) { prepare(); return; }
  const { e } = getParams();
  const listRadius = e + 1; // Use e+1 as list radius to show behavior just past unique-decoding threshold.
  const cands = CODEBOOK.filter(({ cw }) => hamming(cw, lastReceived) <= listRadius);
  const res = document.getElementById('result');
  if (cands.length === 0) {
    setStatus('No candidates found at this radius.', 'bad');
    res.innerHTML = 'Try a larger error count to see the list grow.';
    return;
  }
  setStatus(fmt('List decoding found %length% candidate(s).', { length: cands.length }), 'ok');
  let html = '<b>Candidates:</b> ';
  cands.forEach(({ a, b, cw }) => {
    const isOrig = (a === lastA && b === lastB);
    const cls = isOrig ? 'candidate match' : 'candidate';
    html += '<span class="' + cls + '">f(x)=' + a + 'x+' + b + '</span> ';
  });
  res.innerHTML = html;
}

// Bind slider and button events.
document.getElementById('sliderA').addEventListener('input', function () {
  document.getElementById('valA').textContent = this.value; prepare();
});
document.getElementById('sliderB').addEventListener('input', function () {
  document.getElementById('valB').textContent = this.value; prepare();
});
document.getElementById('sliderE').addEventListener('input', function () {
  document.getElementById('valE').textContent = this.value; prepare();
});
document.getElementById('btnUnique').addEventListener('click', uniqueDecode);
document.getElementById('btnList').addEventListener('click', listDecode);
document.getElementById('btnReset').addEventListener('click', prepare);
prepare();
Result
Console

Notice the transition: unique decoding succeeds only when errors ≤2\leq 2 (half of d=6d=6 rounds down to 2). List decoding keeps finding candidates even with 3 or 4 errors, returning a small list instead of giving up. Checking every candidate is fast; the power of list decoding is that the list stays polynomial in size even past the unique-decoding radius.

The Real Complexity

How hard is list decoding? Surprisingly tractable — and here is why.

The half-distance wall. A code with minimum distance dd can uniquely correct up to ⌊(d−1)/2⌋\lfloor (d-1)/2 \rfloor errors. Beyond that, a received word may be equidistant from two codewords, and any decoder must guess.

The list-decoding insight. Instead of requiring a unique answer, return every codeword within Hamming distance ρ\rho of the received word. As long as ρ\rho stays below the Johnson bound n−n(n−d)n - \sqrt{n(n-d)}, the list size is guaranteed polynomial — there can be at most O(n2)O(n^2) codewords that close together.

Guruswami-Sudan (1998). The algorithm for Reed-Solomon codes works in two algebraic steps:

  1. Interpolation: find a bivariate polynomial Q(x,y)Q(x, y) of low degree that passes through all (xi,yi)(x_i, y_i) pairs, where yiy_i is the received symbol at position xix_i.
  2. Factorization: extract every linear factor y−f(x)y - f(x) of QQ; each factor corresponds to one candidate codeword.

Both steps run in polynomial time O(n3)O(n^3), and the list has size O(n)O(n). This is a sharp contrast with brute-force search over qnq^n codewords.

Open questions. Achieving the Singleton bound (decoding up to n−kn - k errors, the information-theoretic limit) in polynomial time is still open for large alphabets. For binary codes, the situation is even harder: list decoding up to the Zyablov bound efficiently is an active frontier, and whether one can reach capacity with linear-time algorithms touches the deep theory of expander codes and pseudorandomness.

Where It Matters

List decoding is not just theory — it shapes systems you rely on every day:

  • Storage and optical media. Reed-Solomon codes protect hard drives, DVDs and QR codes. Burst errors from a scratch can exceed the unique-decoding radius; list decoding recovers the data by returning candidates and disambiguating with a tiny checksum.
  • Deep-space communication. NASA's Voyager and Cassini missions used concatenated codes where list decoding of the outer Reed-Solomon layer handles the large error bursts that unique decoding cannot.
  • Pseudorandomness and complexity theory. List-decodable codes are the key ingredient in hardness amplification: if a Boolean function is hard on average, you can use a list-decodable code to turn it into one that is worst-case hard — the foundation of derandomization and of connections between learning with errors and cryptography.
  • Streaming and network codes. In network coding over lossy links, list decoding tolerates packet erasures that push past the unique-decoding threshold.

The thread tying them together: whenever errors are so heavy that a unique answer is untenable, a short list of candidates is worth more than silence.

Conclusion

Unique decoding draws a sharp line at half the minimum distance and refuses to cross it. List decoding erases that line — not by working harder, but by reframing the question. Ask for all plausible answers instead of the answer, and suddenly polynomial-time algorithms reach correction radii that were thought impossible.

The Guruswami-Sudan algorithm turns that insight into algebra: interpolate a bivariate polynomial, factor it, collect the candidates. It runs fast, the list stays small, and it has reshaped not just coding theory but the foundations of pseudorandomness and complexity — a reminder that sometimes the right move is to widen the question rather than sharpen the answer. For a deeper look at the limits of computation that list decoding touches, see P vs NP.

Share this article

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

Comments

Loading comments...

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