Convolutional Codes and Viterbi Decoding

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

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">{{hint}}</p>
<div class="row">
  <label>{{label_input}} <input id="inp" type="text" value="10110" maxlength="12" spellcheck="false"/></label>
</div>
<div class="row">
  <label>{{label_noise}} <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">{{btn_encode}}</button>
  <button id="decode-btn">{{btn_decode}}</button>
  <button id="reset-btn" class="ghost">{{btn_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; }

// Code not found

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.

Decoding a convolutional code by brute force would mean comparing the received sequence to every possible transmitted sequence — $2^{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 $2^{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 $2^{k-1}$ survivors need to be kept at each step.
• Result: the total work is $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.

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.

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.