Introduction

Every digital channel — a satellite link, a CD, a Wi-Fi packet — flips bits at random. The goal of error-correcting codes is to add just enough redundancy so the receiver can reconstruct the original message even after some bits are corrupted.

Shannon's 1948 theorem says there exist codes that communicate reliably at any rate below the channel capacity. But for years, the codes that actually approached that limit required exponential-time decoding — beautiful in theory, useless in practice.

In 1965, G. David Forney found an elegant escape: concatenate two simpler codes. Encode the message with a powerful outer code (say, a Reed-Solomon code); then encode each of its symbols again with a fast inner code. The inner code handles the scattered, bit-level errors cheaply. The outer code then sees a much cleaner channel and mops up the residual burst errors with its own decoder. The two decoders compose, and together they approach capacity with only polynomial decoding complexity — a landmark result in coding theory.

Concatenated codes powered the Voyager probes, made CDs scratch-resistant, and held the field until turbo codes and LDPC appeared in the 1990s.

Try It

The demo below lets you inject channel noise and watch the two-layer pipeline in action. A short message is encoded by an inner repetition code, then the inner codewords are encoded again by an outer repetition code. Random bit-flip errors are added, and the two decoders run in sequence.

<!-- Concatenated-codes demo: inner repetition code + outer repetition code -->
<div class="controls">
  <label for="noise-slider">Channel noise: <span id="noise-val">15</span>%</label>
  <input type="range" id="noise-slider" min="0" max="50" value="15" step="1" aria-label="Channel noise:">
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="pipeline" id="pipeline">
  <div class="stage" id="stage-src">
    <div class="stage-label">Source message</div>
    <div class="bits" id="bits-src"></div>
  </div>
  <div class="arrow">&#x25B6;</div>
  <div class="stage" id="stage-inner-enc">
    <div class="stage-label">After inner encode</div>
    <div class="bits" id="bits-inner-enc"></div>
  </div>
  <div class="arrow">&#x25B6;</div>
  <div class="stage" id="stage-noisy">
    <div class="stage-label">After channel noise</div>
    <div class="bits" id="bits-noisy"></div>
  </div>
  <div class="arrow">&#x25B6;</div>
  <div class="stage" id="stage-inner-dec">
    <div class="stage-label">After inner decode</div>
    <div class="bits" id="bits-inner-dec"></div>
  </div>
  <div class="arrow">&#x25B6;</div>
  <div class="stage" id="stage-outer-dec">
    <div class="stage-label">After outer decode</div>
    <div class="bits" id="bits-outer-dec"></div>
  </div>
</div>
<div class="legend">
  <span class="dot ok"></span> correct
  <span class="dot flip"></span> error
  <span class="dot erase"></span> erasure
  <span class="dot fixed"></span> recovered
</div>
<div class="status-msg" id="status-msg"></div>

/* Layout and bit-state colours */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; font-size: 14px; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 80px; max-width: 160px; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.pipeline { display: flex; align-items: flex-start; flex-wrap: wrap; gap: .3rem; }
.arrow { font-size: 1.2rem; color: #888; align-self: center; padding: 0 .2rem; }
.stage { display: flex; flex-direction: column; align-items: center; gap: .35rem; }
.stage-label { font-size: .78rem; font-weight: 700; text-align: center; color: #555;
               max-width: 72px; line-height: 1.2; }
.bits { display: flex; flex-wrap: wrap; gap: 3px; max-width: 80px; justify-content: center; }
.bit { width: 20px; height: 20px; border-radius: 4px; display: flex; align-items: center;
       justify-content: center; font: 700 11px ui-monospace, monospace; transition: background .25s; }
/* Bit state colour classes */
.bit.ok    { background: #d4edda; color: #155724; border: 1px solid #b1dfbb; }
.bit.flip  { background: #f8d7da; color: #721c24; border: 1px solid #f1aeb5; }
.bit.erase { background: #fff3cd; color: #856404; border: 1px solid #ffd966; }
.bit.fixed { background: #cce5ff; color: #004085; border: 1px solid #99caff; }
.bit.empty { background: #e9ecef; color: #adb5bd; border: 1px solid #dee2e6; }
.legend { display: flex; flex-wrap: wrap; gap: .5rem; margin: .6rem 0; font-size: .78rem; align-items: center; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 3px; margin-right: 2px; }
.dot.ok    { background: #d4edda; border: 1px solid #b1dfbb; }
.dot.flip  { background: #f8d7da; border: 1px solid #f1aeb5; }
.dot.erase { background: #fff3cd; border: 1px solid #ffd966; }
.dot.fixed { background: #cce5ff; border: 1px solid #99caff; }
.status-msg { font-weight: 700; font-size: .95rem; min-height: 1.3em; }
.status-msg.ok  { color: #155724; }
.status-msg.bad { color: #721c24; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Concatenated codes demo — inner x3 repetition + outer x3 repetition
// Coding parameters
// inner repetition factor (each bit -> 3 copies) inner repetition factor (each bit -> 3 copies)
const INNER_REP = 3;
// outer repetition factor (each inner block -> 3 copies) outer repetition factor (each inner block -> 3 copies)
const OUTER_REP = 3;
// source message (4 bits) source message (4 bits)
const SRC = [1, 0, 1, 1];

const slider = document.getElementById('noise-slider');
const noiseVal = document.getElementById('noise-val');
slider.addEventListener('input', () => { noiseVal.textContent = slider.value; });

// render an array of {v, cls} into a container render an array of {v, cls} into a container
function renderBits(id, arr) {
  const el = document.getElementById(id); el.innerHTML = '';
  arr.forEach(({v, cls}) => {
    const d = document.createElement('div');
    d.className = 'bit ' + cls;
    d.textContent = v === null ? '?' : v;
    el.appendChild(d);
  });
}

// inner encoder: repeat each bit INNER_REP times inner encoder: repeat each bit INNER_REP times
function innerEncode(bits) {
  const out = [];
  bits.forEach(b => { for (let i = 0; i < INNER_REP; i++) out.push(b); });
  return out;
}

// inner decoder: majority vote over each group of INNER_REP bits inner decoder: majority vote over each group of INNER_REP bits
// returns {decoded, erasures[]} where erasures flags tied votes returns {decoded, erasures[]} where erasures flags tied votes
function innerDecode(bits) {
  const decoded = []; const erasures = [];
  for (let i = 0; i < bits.length; i += INNER_REP) {
    const group = bits.slice(i, i + INNER_REP);
    const ones = group.filter(x => x === 1).length;
    const zeros = group.filter(x => x === 0).length;
    if (ones > zeros) { decoded.push(1); erasures.push(false); }
    else if (zeros > ones) { decoded.push(0); erasures.push(false); }
    else { decoded.push(null); erasures.push(true); } // tied vote = erasure tied vote = erasure
  }
  return { decoded, erasures };
}

// outer encoder: repeat each inner block OUTER_REP times outer encoder: repeat each inner block OUTER_REP times
function outerEncode(innerBlocks) {
  const out = [];
  innerBlocks.forEach(block => {
    for (let i = 0; i < OUTER_REP; i++) out.push([...block]);
  });
  return out;
}

// outer decoder: majority vote across OUTER_REP copies of each inner block outer decoder: majority vote across OUTER_REP copies of each inner block
// each symbol is a decoded bit (or null for erasure) each "symbol" is a decoded bit (or null for erasure)
function outerDecode(blocks, srcLen) {
  const result = [];
  for (let b = 0; b < srcLen; b++) {
    const votes = [];
    for (let r = 0; r < OUTER_REP; r++) {
      const val = blocks[b * OUTER_REP + r];
      if (val !== null) votes.push(val);
    }
    if (votes.length === 0) { result.push(null); continue; }
    const ones = votes.filter(x => x === 1).length;
    result.push(ones > votes.length / 2 ? 1 : 0);
  }
  return result;
}

// inject bit-flip errors at the given rate (0-1) inject bit-flip errors at the given rate (0–1)
function injectNoise(bits, rate) {
  return bits.map(b => Math.random() < rate ? 1 - b : b);
}

function run() {
  const noiseRate = parseInt(slider.value) / 100;

  // Step 1: source message Step 1: source message
  renderBits('bits-src', SRC.map(v => ({ v, cls: 'ok' })));

  // Step 2: inner encode — repeat each source bit INNER_REP times Step 2: inner encode — repeat each source bit INNER_REP times
  const innerEncoded = innerEncode(SRC);
  // Step 3: outer encode — repeat the entire inner codeword OUTER_REP times Step 3: outer encode — repeat the entire inner codeword OUTER_REP times
  const outerBlocks = outerEncode(
    SRC.map((_, i) => innerEncoded.slice(i * INNER_REP, (i + 1) * INNER_REP))
  );
  const transmitted = outerBlocks.flat();

  // display flattened encoded bits display flattened encoded bits
  renderBits('bits-inner-enc', transmitted.map(v => ({ v, cls: 'ok' })));

  // Step 4: apply noise Step 4: apply noise
  const received = injectNoise(transmitted, noiseRate);
  const noisyDisplay = received.map((v, i) => ({
    v, cls: v !== transmitted[i] ? 'flip' : 'ok'
  }));
  renderBits('bits-noisy', noisyDisplay);

  // Step 5: inner decode each group of INNER_REP bits Step 5: inner decode each group of INNER_REP bits
  const innerDecGroups = [];
  for (let b = 0; b < SRC.length * OUTER_REP; b++) {
    const chunk = received.slice(b * INNER_REP, (b + 1) * INNER_REP);
    innerDecGroups.push(innerDecode(chunk));
  }
  const innerDecSymbols = innerDecGroups.map(g => g.decoded[0]);
  const innerErasures   = innerDecGroups.map(g => g.erasures[0]);

  const innerDecDisplay = innerDecSymbols.map((v, i) => ({
    v: v === null ? '?' : v,
    cls: v === null ? 'erase' : v !== transmitted.flat()[i * INNER_REP] ? 'flip' : 'ok'
  }));
  renderBits('bits-inner-dec', innerDecDisplay);

  // Step 6: outer decode — majority vote across OUTER_REP copies Step 6: outer decode — majority vote across OUTER_REP copies
  const outerDecoded = outerDecode(innerDecSymbols, SRC.length);

  const outerDisplay = outerDecoded.map((v, i) => ({
    v: v === null ? '?' : v,
    cls: v === null ? 'erase' : (v === SRC[i] ? 'fixed' : 'bad')
  }));
  // mark perfect recoveries as fixed (blue), mismatches as flip (red) mark perfect recoveries as "fixed" (blue), mismatches as "flip" (red)
  const outerDisplayFinal = outerDecoded.map((v, i) => ({
    v: v === null ? '?' : v,
    cls: v === null ? 'erase' : (v === SRC[i] ? 'fixed' : 'flip')
  }));
  renderBits('bits-outer-dec', outerDisplayFinal);

  // summary message summary message
  const errors = outerDecoded.filter((v, i) => v !== SRC[i]).length;
  const statusEl = document.getElementById('status-msg');
  if (errors === 0) {
    statusEl.textContent = '✓ Message recovered perfectly by the two-layer decoder.';
    statusEl.className = 'status-msg ok';
  } else {
    statusEl.textContent = fmt('✗ %errors% bit(s) unrecovered — try lowering the noise.', { errors: errors });
    statusEl.className = 'status-msg bad';
  }
}

function reset() {
  ['bits-src','bits-inner-enc','bits-noisy','bits-inner-dec','bits-outer-dec'].forEach(id => {
    const el = document.getElementById(id); el.innerHTML = '';
  });
  document.getElementById('status-msg').textContent = '';
  document.getElementById('status-msg').className = 'status-msg';
  slider.value = 15; noiseVal.textContent = '15';
}

document.getElementById('btn-run').addEventListener('click', run);
document.getElementById('btn-reset').addEventListener('click', reset);
run();
Result
Console

Notice the division of labor: the inner decoder fixes scattered single-bit errors within each inner block. The outer decoder then sees occasional block-erasures (inner failures) and corrects those bursts. Neither layer alone would suffice; together they recover the message from a surprisingly noisy channel.

The Real Complexity

Why is this construction so important? Before Forney, the only known capacity-approaching codes required exponential decoding — 2n2^{n} work for a message of length nn. The concatenated scheme changes that picture completely.

  • Inner code: a block code of length ninn_{\text{in}} over a small alphabet. Its decoder runs in O(nin)O(n_{\text{in}}) or O(nin2)O(n_{\text{in}}^{2}) time. It reduces a noisy channel to a much cleaner one, but it occasionally fails and produces a block erasure.
  • Outer code: a Reed-Solomon or other algebraic code of block length NoutN_{\text{out}}. It sees the erasures left by the inner decoder and corrects them in O(Nout2)O(N_{\text{out}}^{2}) time.
  • Total decoding: O(Nout⋅nin2)O(N_{\text{out}} \cdot n_{\text{in}}^{2}) — polynomial in the total codeword length N=Nout⋅ninN = N_{\text{out}} \cdot n_{\text{in}}.

Forney proved that by choosing the inner and outer codes carefully, the end-to-end block error probability decays exponentially in NN at any rate strictly below capacity — the same guarantee as exponential-time codes, but now achievable with polynomial work.

The key insight is that errors arrive in two scales: scattered (within an inner block, handled cheaply by the inner decoder) and bursty (failed inner blocks, handled by the outer code's burst-correction ability). Each layer is matched to the error structure it sees.

This two-scale philosophy echoes throughout modern coding theory. Turbo codes also use two component codes in parallel, iterating soft messages between them instead of decoding once per layer.

Where It Matters

Forney's construction left fingerprints across almost every major digital medium:

  • Deep-space probes: Voyager 1 and 2 (1977) used a convolutional inner code with a Reed-Solomon outer code. The combination gave NASA reliable telemetry over billions of kilometers.
  • Compact discs: the Cross-Interleaved Reed-Solomon Coding (CIRC) scheme layers two Reed-Solomon codes with an interleaver between them. A scratched CD loses a burst of bytes — the interleaver spreads that burst so the outer RS code can recover it.
  • DVB and early digital TV: the DVB-S and DVB-T standards use a convolutional inner code (Viterbi decoder) plus a Reed-Solomon outer code (204, 188) — exactly Forney's architecture.
  • Theoretical impact: Forney's analysis was the first polynomial-complexity result for capacity-approaching codes, and it seeded decades of follow-up work. The algebraic geometry codes of the 1980s and the list-decoding breakthroughs of Guruswami and Sudan in 1998 both build directly on concatenated-code ideas.

Even after turbo codes and LDPC replaced concatenation in bandwidth-critical applications, concatenated codes remain the standard design for systems that need proven worst-case guarantees — reliability proofs, not just empirical graphs.

Conclusion

Forney's concatenated codes answered a question that had haunted information theory for seventeen years: can we actually reach Shannon's limit without infinite computation? The answer was yes — provided you split the job across two layers.

The inner code fights the cheap, scattered errors. The outer code fights the expensive, bursty ones. Neither needs to be optimal on its own; together they compose into something better than the sum of their parts.

That division-of-labor philosophy shows up again and again in computing: in compression pipelines that chain predictors and entropy coders, in network stacks that layer protocols, in machine-learning architectures that stack representations. The lesson of concatenated codes is not just about error correction — it is about the power of well-chosen composition.

Share this article

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

Comments

Loading comments...

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