Introduction

Every time you make a call, stream a video, or send a message over a cellular network, your device wraps the raw bits in a protective shell before transmitting them. That shell is often a convolutional code — an error-correction scheme first described by Peter Elias in 1955 that dominated digital communications for half a century.

The idea is beautifully simple: instead of sending each input bit as-is, pass it through a small shift register that mixes it with the recent past. Every input bit produces two or more output bits, all of which encode not just the current bit but a memory of the last several bits. That redundancy lets the receiver reconstruct the original message even when the channel flips some bits.

Decoding seems hard at first glance — there are exponentially many possible transmitted sequences. But Andrew Viterbi discovered in 1967 that the trellis structure of the code reduces the search to a clean polynomial-time algorithm. The Viterbi algorithm is now one of the most-used algorithms in the history of digital communications, and it solves the decoding problem optimally in O(n⋅2k)O(n \cdot 2^{k}) time, where n is the message length and k is the constraint length of the code.

This is a case where a problem that looks exponential turns out to have an efficient exact solution — not because it's easy, but because its structure is perfectly suited to dynamic programming.

Try It: Encode, Corrupt, Recover

Type a short binary message (or use the example), then click Encode to run it through the rate-1/2 convolutional encoder. The slider controls how many bits the channel randomly flips. Press Decode (Viterbi) to recover the original — the algorithm traces the most-likely path through the trellis.

<p class="hint">Type a binary message (e.g. <code>10110</code>), then <b>Encode</b> it with a rate-1/2 convolutional code. Use the slider to add noise, then <b>Decode (Viterbi)</b> to recover the original.</p>
<div class="row">
  <label>Input bits: <input id="inp" type="text" value="10110" maxlength="12" spellcheck="false"/></label>
</div>
<div class="row">
  <label>Noise (bits to flip): <input id="noise" type="range" min="0" max="6" value="1"/> <span id="noise-val">1</span></label>
</div>
<div class="btns">
  <button id="encode-btn">Encode</button>
  <button id="decode-btn">Decode (Viterbi)</button>
  <button id="reset-btn" class="ghost">Reset</button>
</div>
<div id="panel"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .93rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
code { background: #eef1f4; padding: 0 3px; border-radius: 3px; font-size: .85rem; }
.row { display: flex; align-items: center; gap: .5rem; margin: .35rem 0; flex-wrap: wrap; }
label { display: flex; align-items: center; gap: .4rem; font-size: .88rem; }
input[type=text] { font: 600 15px ui-monospace, monospace; width: 130px; padding: .3rem .5rem;
  border: 1px solid #cdd9e3; border-radius: 6px; }
input[type=range] { width: 120px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#panel { margin-top: .6rem; }
.section-label { font-size: .78rem; font-weight: 700; color: #6b7280; text-transform: uppercase;
                 letter-spacing: .05em; margin: .7rem 0 .2rem; }
.bits { display: flex; flex-wrap: wrap; gap: 3px; margin: .2rem 0 .5rem; }
.bit { display: inline-flex; align-items: center; justify-content: center;
       width: 28px; height: 28px; border-radius: 5px; font: 700 13px ui-monospace, monospace;
       border: 1px solid #cdd9e3; }
.bit-in  { background: #dbeafe; border-color: #93c5fd; color: #1e40af; }
.bit-enc { background: #dcfce7; border-color: #86efac; color: #166534; }
.bit-rx  { background: #fef3c7; border-color: #fcd34d; color: #92400e; }
.bit-rx.flipped { background: #fee2e2; border-color: #fca5a5; color: #991b1b; }
.bit-dec { background: #ede9fe; border-color: #c4b5fd; color: #5b21b6; }
.result-ok  { color: #166534; font-weight: 700; margin: .3rem 0; }
.result-err { color: #991b1b; font-weight: 700; margin: .3rem 0; }
.note { font-size: .82rem; color: #4b5563; margin: .4rem 0 0; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Rate-1/2 convolutional code, constraint length k=3.
// Generators: g1=110 (0x6), g2=111 (0x7) — standard NASA/GSM polynomials.
// State = last 2 input bits (2 bits, 4 states).
// Each input bit produces 2 output bits; encoded length = 2 * (n + k - 1).
// We tail-bite by appending k-1=2 zero bits to flush the encoder.

const G1 = [1,1,0]; // taps for output 1
const G2 = [1,1,1]; // taps for output 2
const K  = 3;       // constraint length
const STATES = 1 << (K - 1); // 4 states

function dot(reg, taps) {
  return reg.reduce((s, b, i) => s ^ (b & taps[i]), 0);
}

// Encode: input is array of bits; appends (K-1) zeros to flush.
function encode(bits) {
  const msg = [...bits, ...new Array(K - 1).fill(0)];
  const reg = new Array(K).fill(0);
  const out = [];
  for (const b of msg) {
    reg.unshift(b); reg.pop();
    out.push(dot(reg, G1), dot(reg, G2));
  }
  return out;
}

// Viterbi decoder: received is array of bits (possibly noisy).
// Returns decoded bits (original length, without the flush zeros).
function viterbi(received, origLen) {
  const totalSteps = origLen + K - 1;
  // paths[state] = { cost, bits[] }
  let paths = Array.from({length: STATES}, (_, s) => ({
    cost: s === 0 ? 0 : Infinity, bits: []
  }));
  const rx = received;

  for (let t = 0; t < totalSteps; t++) {
    const r0 = rx[2 * t], r1 = rx[2 * t + 1];
    const next = Array.from({length: STATES}, () => ({ cost: Infinity, bits: null }));

    for (let s = 0; s < STATES; s++) {
      if (paths[s].cost === Infinity) continue;
      for (const b of [0, 1]) {
        const reg = [(b << (K-1)) | s >> 0]; // reconstruct shift register
        // reg[0]=current input bit, reg[1..K-1]=previous state bits
        const fullReg = [b, ...toBits(s, K-1)];
        const c0 = dot(fullReg, G1);
        const c1 = dot(fullReg, G2);
        const hammingDist = (c0 ^ r0) + (c1 ^ r1);
        const newCost = paths[s].cost + hammingDist;
        const nstate = ((s >> 1) | (b << (K-2))); // next state
        if (newCost < next[nstate].cost) {
          next[nstate] = { cost: newCost, bits: [...paths[s].bits, b] };
        }
      }
    }
    paths = next;
  }
  // Find state with lowest cost (should be 0 if flush zeros worked)
  let best = paths[0];
  for (const p of paths) if (p.cost < best.cost) best = p;
  return best.bits.slice(0, origLen);
}

function toBits(n, len) {
  const b = [];
  for (let i = len - 1; i >= 0; i--) b.push((n >> i) & 1);
  return b;
}

function addNoise(encoded, nFlips) {
  const rx = [...encoded];
  // randomly pick nFlips distinct positions
  const idx = [];
  while (idx.length < Math.min(nFlips, rx.length)) {
    const p = Math.floor(Math.random() * rx.length);
    if (!idx.includes(p)) idx.push(p);
  }
  const flipped = new Set(idx);
  for (const i of idx) rx[i] ^= 1;
  return { rx, flipped };
}

function parseBits(s) {
  return [...s.trim()].filter(c => c==='0'||c==='1').map(Number);
}

function renderBits(bits, cls, flippedSet) {
  return bits.map((b, i) => {
    const f = flippedSet && flippedSet.has(i) ? ' flipped' : '';
    return `<span class="bit ${cls}${f}">${b}</span>`;
  }).join('');
}

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

let lastInput = null, lastEncoded = null, lastRx = null, lastFlipped = null;

document.getElementById('encode-btn').addEventListener('click', () => {
  const bits = parseBits(document.getElementById('inp').value);
  if (bits.length === 0) { document.getElementById('panel').innerHTML = '<p class="result-err">Enter at least one bit (0 or 1).</p>'; return; }
  lastInput   = bits;
  lastEncoded = encode(bits);
  const nFlips = parseInt(noiseSlider.value);
  const { rx, flipped } = addNoise(lastEncoded, nFlips);
  lastRx = rx; lastFlipped = flipped;
  document.getElementById('panel').innerHTML = "\n    " + fmt(`<div class="section-label">Input (%length% bits)</div>
    <div class="bits">%renderBits%</div>
    <div class="section-label">Encoded (%length2% bits) — rate 1/2, generators 110 &amp; 111</div>
    <div class="bits">%renderBits2%</div>
    <div class="section-label">Received after channel (%nFlips% bit%v% flipped, shown in red)</div>
    <div class="bits">%renderBits3%</div>
    <p class="note">Press <b>Decode (Viterbi)</b> to recover the original.</p>`, { length: bits.length, renderBits: renderBits(bits, 'bit-in', null), length2: lastEncoded.length, renderBits2: renderBits(lastEncoded, 'bit-enc', null), nFlips: nFlips, v: nFlips!==1?`s`:'', renderBits3: renderBits(rx, 'bit-rx', flipped) });
});

document.getElementById('decode-btn').addEventListener('click', () => {
  if (!lastInput || !lastRx) { document.getElementById('panel').innerHTML = '<p class="result-err">Click Encode first.</p>'; return; }
  const decoded = viterbi(lastRx, lastInput.length);
  const ok = decoded.every((b, i) => b === lastInput[i]);
  document.getElementById('panel').innerHTML += "\n    " + fmt(`<div class="section-label">Decoded (Viterbi)</div>
    <div class="bits">%renderBits%</div>
    <p class="%v%">%v2%</p>
    <p class="note">The Viterbi algorithm traces the most-likely path through %STATES% states × %v3% steps = %v4% trellis nodes.</p>`, { renderBits: renderBits(decoded, 'bit-dec', null), v: ok ? 'result-ok' : 'result-err', v2: ok ? `✓ Perfect recovery — Viterbi found the original.` : `✗ Decoding error — too many flipped bits for this code.`, STATES: STATES, v3: lastInput.length + K - 1, v4: STATES * (lastInput.length + K - 1) });
  console.log(`Input:`, lastInput.join(''), '| Encoded:', lastEncoded.join(''), '| Flipped positions:', [...lastFlipped].sort((a,b)=>a-b).join(','), '| Decoded:', decoded.join(''), '| Match:', ok);
});

document.getElementById('reset-btn').addEventListener('click', () => {
  document.getElementById('inp').value = '10110';
  noiseSlider.value = 1; noiseVal.textContent = '1';
  lastInput = lastEncoded = lastRx = lastFlipped = null;
  document.getElementById('panel').innerHTML = '';
});
Result
Console

Notice two things. First, the encoded sequence is exactly twice as long as the input — each input bit becomes two output bits. Second, even with several bit-flips the Viterbi decoder recovers the original perfectly, because the redundancy gives it enough information to correct errors. Only when the noise exceeds the code's error-correcting capacity does it start to fail.

The Real Complexity

Decoding a convolutional code by brute force would mean comparing the received sequence to every possible transmitted sequence — 2n2^{n} options for an n-bit message, which is hopelessly slow.

The Viterbi algorithm escapes that trap by exploiting the trellis structure of the code:

  • States: the encoder has 2k−12^{k-1} states (determined by the last k−1 input bits). For a constraint length of k=3, that is just 4 states.
  • Transitions: at each step, every state connects to exactly 2 successor states (one for input bit 0, one for input bit 1), and each transition emits a known pair of bits.
  • Dynamic programming: the algorithm keeps, for each state, the most-likely path from the beginning up to the current step. When two paths arrive at the same state, it discards the worse one — this is the survivor path trick. Only the 2k−12^{k-1} survivors need to be kept at each step.
  • Result: the total work is O(n⋅2k−1)O(n \cdot 2^{k-1}) — linear in message length, exponential only in the (fixed, small) constraint length.

Jim Omura proved in 1969 that the Viterbi algorithm is optimal: no other algorithm can decode a convolutional code with fewer error-correcting operations. This makes it a rare case in the study of algorithms — a proven optimal solution that is also practical for real hardware.

Compare this with P vs NP: most hard-to-decode codes (like general linear codes with maximum-likelihood decoding) are NP-hard. Convolutional codes escape that fate because their structure is regular enough to support exact dynamic programming. The trellis is the key: it turns an exponential problem into a linear scan.

Where It Matters

Convolutional codes and the Viterbi algorithm powered some of the most demanding communication systems ever built:

  • Deep-space probes: NASA's Voyager 1 and 2 (1977) used rate-1/2 convolutional codes to send images across billions of kilometers. The Pioneer and Galileo missions followed. Every pixel of those iconic Saturn and Jupiter photos was decoded with Viterbi.
  • Mobile networks: GSM (2G), CDMA, W-CDMA (3G), and early LTE (4G) all used convolutional codes as their primary channel coding scheme. When you made a call in 2005, the Viterbi algorithm was running billions of times per second on your handset's baseband chip.
  • Satellite TV: direct-broadcast satellite standards (DVB-S, DirecTV) relied on convolutional codes for decades to deliver crisp video over noisy downlinks.
  • Disk drives: variants of Viterbi decoding (PRML — partial response maximum likelihood) have been the standard for hard-disk read channels since the 1990s.

Modern systems have largely moved to turbo codes (1993, Berrou et al.) and LDPC codes (re-discovered by Gallager 1962, now in 5G and Wi-Fi 6), which approach the theoretical Shannon limit more closely. But the Viterbi algorithm — and the insight that trellis structure makes optimal decoding tractable — remains central to all of them.

Understanding convolutional codes also illuminates sequence alignment in bioinformatics: the Needleman–Wunsch and Smith–Waterman algorithms are essentially Viterbi decoding applied to DNA, and the Hidden Markov Model framework that underlies speech recognition is the same trellis idea in yet another domain.

Conclusion

Convolutional codes are a masterclass in using structure to defeat apparent intractability. By feeding bits through a small memory and spreading them across multiple outputs, the encoder creates redundancy that survives noise. By exploiting the trellis that the encoder's state machine naturally draws, the Viterbi algorithm turns what looks like an exponential search into a linear-time scan — and does so optimally.

The lesson echoes across computer science: many problems that appear exponential have hidden structure that makes them tractable. Finding that structure — and proving you've found it — is one of the deepest activities in the field, and it sits right at the heart of P vs NP.

The next time your phone call stays crisp through a tunnel, or a spacecraft image arrives clean from across the solar system, a trellis is being walked somewhere in silicon — and 1967's insight is doing the work.

Share this article

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

Comments

Loading comments...

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