The formula
A rate k/n convolutional encoder takes k input bits per step and puts out n coded bits. The n outputs are each a modulo-2 sum (XOR) of the current input and some of the previous inputs held in a shift register. For the common rate-1/2 case, using the K=7 generators defined below:
y1[i] = x[i] ⊕ x[i-1] ⊕ x[i-2] ⊕ x[i-3] ⊕ x[i-6] tap pattern g1
y2[i] = x[i] ⊕ x[i-2] ⊕ x[i-3] ⊕ x[i-5] ⊕ x[i-6] tap pattern g2
Reads as: every output bit is a fixed XOR of the current data bit and a handful of recent ones. Which recent ones is set by the generator polynomials.
Two numbers define a code:
K = constraint length = register span = number of input bits that touch each output
r = k / n = code rate (fraction of the stream that is your data)
Reads as: K is how far back the memory reaches; r is how much overhead you paid. A rate-1/2 code doubles your bit stream.
The generators are written in octal. The industry-standard deep-space code is K=7, rate 1/2:
g1 = 171 (octal) = 1111001 (binary)
g2 = 133 (octal) = 1011011 (binary)
Reads as: two seven-bit tap masks. The encoder XORs together the register bits marked 1 in each mask — exactly the delays written out in the y1 and y2 lines above.
The trellis has 2^(K-1) states. For K=7 that is 2^6 = 64 states. The decoder's job is to pick the state sequence closest to what was received.
dfree = minimum Hamming distance between any two distinct coded sequences
t = floor( (dfree - 1) / 2 ) guaranteed bit-error correction within one decoding window
For the K=7 (171,133) code, dfree = 10, so t = floor(9/2) = 4. Both numbers verified by trellis search, not quoted. Mind the fine print: unlike a block code's t, this guarantee only applies to errors falling within one decoding span — a sliding window a few constraint lengths wide, roughly the traceback depth. Errors spread farther apart than that are handled independently, so over a long stream the code corrects far more than t errors total; but a dense clump of more than t errors inside one window defeats it (see the burst-error discussion below).
Where you meet it
- A legacy satellite downlink on the bench. Anything talking to the CCSDS deep-space standard — Voyager-heritage telemetry, older weather birds, a lot of cubesat beacons — runs a K=7 rate-1/2 inner code, often concatenated with an outer Reed-Solomon block. Your SDR receiver has a Viterbi block in the chain whether you configured it or not.
- A radio-link margin review. When the link-budget spreadsheet shows required Eb/N0 dropping by several dB "because of coding," that number is the convolutional coding gain. It is real signal margin you can spend on a smaller dish, lower power, or more range.
- A GPS or old modem teardown. GPS L2C and L5 CNAV navigation data, IS-95 CDMA, 802.11a/g, and dial-up V.32 modems all carry convolutional codes — the legacy L1 C/A LNAV message, by contrast, has no forward error correction at all, only a parity check per 30-bit word, which is exactly why the modernized civil signals added the K=7 code. If you are reverse-engineering a bit stream and it will not sync to any block code, suspect a trellis.
- A radiation-hardened FPGA design. The Viterbi decoder is a classic fixed-function block in space-grade parts. Traceback depth, soft-decision bit width, and puncturing pattern are the parameters you set, and they trade latency and logic against error performance.
How it works
The encoder is dead simple: a shift register and a few XOR gates, clocked at the data rate. All the intelligence lives in the decoder.
The Viterbi algorithm is maximum-likelihood decoding done cheaply. Picture the trellis: 64 states across the top, time running left to right, two possible branches leaving each state (input 0 or 1). Every received symbol, the decoder computes a branch metric — how far the received bits are from what each branch would have transmitted. It then keeps, for each of the 64 states, only the single surviving path with the best accumulated metric. That "keep the best path into each state" step is the whole trick. Instead of comparing all 2^L possible messages, you do a fixed 64-state update per symbol, forever. Cost grows with 2^(K-1), not with message length.
The single biggest lever is soft versus hard decision. Hard-decision hands the decoder a clean 0 or 1 per received bit. Soft-decision hands it a confidence value — typically a 3-bit number saying "probably 1, but weak." Letting the decoder see the analog confidence buys roughly 2 dB of coding gain over hard-decision, for free in the demodulator. Engineers who wire up a Viterbi decoder in hard-decision mode and then wonder where their margin went have made the classic mistake. If your ADC and demod can hand over soft bits, use them.
Puncturing is how you get higher rates without a new decoder. Start with the rate-1/2 code, then periodically delete some output bits per a fixed pattern to reach rate 2/3, 3/4, or 7/8. The decoder inserts erasures where bits were punctured and runs the same trellis. You trade coding gain for throughput and keep one hardware core. This is why one Viterbi block can serve several link modes.
Watch the limits. Convolutional codes with Viterbi decoding shine against random, memoryless bit errors — thermal noise on an AWGN channel. They do poorly against bursts, because a burst corrupts a run of contiguous trellis branches and the survivor paths all take the same hit. Two standard fixes, and they sit in different places. Against channel bursts, a channel interleaver goes after the convolutional encoder, with the matching deinterleaver ahead of the Viterbi decoder, so the burst gets scattered into isolated errors the trellis can absorb — that is the IS-95 and DVB arrangement. In the CCSDS deep-space stack the interleaving is Reed-Solomon symbol interleaving between the outer Reed-Solomon code and the inner convolutional encoder, and its job is the reverse direction: it protects the RS decoder from the bursty clumps of errors a Viterbi decoder emits when it does fail. That layered defense — Reed-Solomon outer, interleave, convolutional inner — exists because no single code covers both noise types.
Two more practical gotchas. Traceback depth must be long enough — a common rule is about five times K — or you truncate good paths and lose performance; too long wastes latency and memory. And the decoder introduces a fixed decode delay equal to that traceback length, so decoded bit 1 comes out aligned to received bit tblen+1, not bit 1. If your framing looks shifted, that offset is usually why.
History
Peter Elias, on the MIT electrical engineering faculty, introduced convolutional codes in a 1955 paper, "Coding for Noisy Channels," presented in the IRE Convention Record [1][2]. He was working in the shadow of Claude Shannon's 1948 result, which had promised that reliable communication near channel capacity was possible but did not say how to build it. Elias's convolutional construction was one of the first practical attempts — codes with memory, generated by sliding a small register across the data. Elias was born in 1923 and spent nearly his whole career at MIT [2].
For a decade the codes existed but lacked a good decoder. Sequential decoding methods were tried but had ugly, data-dependent running times. The breakthrough came in 1967, when Andrew Viterbi published "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm" in the IEEE Transactions on Information Theory [3][4]. Viterbi's original goal was theoretical — bounding the error probability — but the algorithm he built to prove the bound turned out to be maximum-likelihood, and its cost was fixed per symbol rather than exploding with message length.
The tool that made it click for engineers was the trellis. In 1973, G. David Forney Jr. published "The Viterbi Algorithm" in the Proceedings of the IEEE and framed the whole thing as a shortest-path search through a time-unrolled state diagram [3][5]. Drawn as a trellis, the algorithm's maximum-likelihood nature is obvious at a glance, and hardware designers could read the state count and branch structure straight off the picture.
The proof of the pudding was deep space. NASA and JPL adopted the K=7, rate-1/2 code — generators 171 and 133 octal — for the Voyager missions, later concatenating it with a Reed-Solomon outer code, and that combination became the CCSDS standard used across ESA, NASA, and JPL deep-space links [3][6]. A code Elias sketched to chase Shannon's bound is why a spacecraft billions of miles out can still be heard.
Related tools
- /tools/link-budget
- /tools/thermal-noise-floor
- /tools/snr-enob
- /tools/db-converter
- /tools/free-space-path-loss
- /tools/noise-figure-temperature