Convolutional Codes & Viterbi Decoding

A convolutional encoder has memory: each input bit affects several successive output symbols. That memory turns isolated symbol decisions into a sequence problem. The Viterbi algorithm solves the maximum-likelihood (ML) sequence problem on the encoder's trellis without enumerating every possible input sequence; at each time and state it discards any path that can never beat the best path reaching the same state.

This elegant rule does not make implementations interchangeable. Generator orientation, bit order, output order, symbol inversion, puncturing phase, starting state, termination, soft-metric polarity, and traceback policy are all on-wire protocol. Two encoders described as “rate 1/2, $K=7$, generators 171/133 octal” can still disagree on every transmitted bit if those conventions differ.

Encoder as a finite-state convolution #

For one input bit per step and $n$ output bits, a binary rate-$1/n$ feed-forward encoder computes

$$v_j[k]=\bigoplus_{i=0}^{m} g_{j,i}u[k-i],\qquad j=0,\ldots,n-1,$$

where $\oplus$ is modulo-2 addition, $m$ memory bits are stored, and constraint length is $K=m+1$. The state is the previous $m$ inputs, so the trellis has $2^m$ states. Complexity grows exponentially in memory, not in frame length.

For the worked code, use rate $1/2$, $K=3$, generators

$$g_0(D)=1+D+D^2=(7)_8,qquad g_1(D)=1+D^2=(5)_8.$$

With state $(u[k-1],u[k-2])$, input $u[k]$ emits

$$(v_0,v_1)=\left(u[k]\oplus u[k-1]\oplus u[k-2],\;u[k]\oplus u[k-2]\right)$$

and the next state is $(u[k],u[k-1])$.

This transition table is a better interoperability fixture than a polynomial label. Generate it from the actual implementation and compare all states before testing long random frames.

The trellis unfolds time #

At time $k$, each state has two outgoing branches for binary input. A path through the trellis uniquely determines the input sequence, encoder state sequence, and output sequence. Without termination, $L$ input bits create $2^L$ paths; with $2^m$ states, only $2^m$ best partial paths need survive at each step.

For a memoryless channel, the likelihood of a complete path factors by branches. Taking negative logarithms turns the product into an additive path metric:

$$M_k(q)=\min_{p\to q}\left[M_{k-1}(p)+\lambda_k(p\to q)\right],$$

where $p\to q$ is a legal transition and $\lambda_k$ is its branch metric. The decoder stores the winning predecessor and input for each destination state.

Why may the loser be discarded permanently? Two paths merging into the same state have identical possible futures because the encoder state contains all relevant memory. Every future suffix adds the same candidate suffix metrics to both histories. The path already worse at the merge can never become better later. This is Bellman's principle of optimality in a finite-state channel.

Worked Viterbi decode with one channel error #

Start the $(7,5)_8$ encoder in state 00 and send information bits 1011, then append two zero tail bits to return to state 00:

input:   1  0  1  1  0  0
output: 11 10 00 01 01 11
receive:11 11 00 01 01 11

The second received pair differs from the transmitted pair in one bit. With hard decisions, branch metric is Hamming distance. Initial metrics are $M_0(00)=0$ and infinity for the other states. After each received pair, the survivor metrics are:

Because termination declares final state 00, traceback begins there and recovers 101100; removing the two tail bits yields payload 1011. The final metric 1 equals the single flipped coded bit.

Hard and soft branch metrics #

For hard received bits $r_j\in\{0,1\}$ and expected coded bits $c_j$, use Hamming distance

$$\lambda_H=\sum_j (r_j\oplus c_j).$$

Hard slicing throws away reliability. For BPSK mapping $0\mapsto +1$, $1\mapsto-1$ with real observation $y_j$ and known variance $\sigma^2$, the AWGN negative log-likelihood is, up to a common positive scale and constant,

$$\lambda_E=\sum_j\left(y_j-(1-2c_j)\right)^2.$$

If the detector supplies bit LLRs $L_j=\log P(c_j=0\mid y_j)/P(c_j=1\mid y_j)$, a convenient max-log branch cost is

$$\lambda_{LLR}\doteq\sum_j \max\left(0,-(1-2c_j)L_j\right).$$

The exact scale can be common to every branch, but sign, saturation, quantization, and relative reliability cannot. Before blaming the code, verify that positive LLR really means the decoder's expected bit value and that punctured positions contribute zero information, not a confident zero bit.

Soft decisions usually provide a substantial coding advantage over hard decisions because a barely wrong sample and a deeply wrong sample no longer receive the same unit penalty. The gain is not magic attached to “8-bit soft input”; it depends on calibrated metrics and sufficient quantization around the decision boundary. Excess range spent on rare large magnitudes can leave too few useful levels near zero.

Free distance controls error events #

For a linear convolutional code, the all-zero path may represent the transmitted codeword without loss of generality. The free distance $d_{free}$ is the minimum Hamming weight of any nonzero trellis path that diverges from and later remerges with the zero path. It plays the role that minimum distance plays for block codes.

At high SNR, errors are dominated by low-weight divergence–remergence events, not independent coded-bit flips. A union bound uses the distance spectrum: both the number of events at each distance and the number of information-bit errors they cause matter. This is why two codes with the same rate and constraint length can have different performance.

A transfer-function or exhaustive trellis search can compute the spectrum for a small code. A practical verification should also inject each short low-weight event and confirm the decoder's metric and traceback, because those are the cases that dominate the error floor and expose convention mistakes.

Termination defines the path set #

Three common frame contracts are distinct:

For the six-step worked example, forcing the end to 00 turns a metric-1 path into the answer even if another state had happened to have a smaller metric. Without a declared final state, the decoder chooses the minimum-metric state after adequate delay. These are different ML problems.

Streaming decoders usually trace back after several constraint lengths because survivor paths tend to merge. A rule such as $5K$ is only a starting convention; puncturing, code spectrum, SNR, and required residual error rate change the needed depth. Verify traceback depth against long error events rather than copying a constant blindly.

Puncturing preserves the mother trellis #

Puncturing deletes selected mother-code symbols according to a periodic mask. A rate-$1/2$ encoder can therefore create higher effective rates while using the same state transitions. If $k_p$ input bits generate $2k_p$ mother symbols and the mask transmits $n_p$ of them, the effective rate is

$$R_{eff}=\frac{k_p}{n_p}.$$

Example: across two input bits, a mask

$$P=\begin{bmatrix}1&1\\1&0\end{bmatrix}$$

transmits three of four mother symbols, producing rate $2/3$. At the decoder, the missing symbol is an erasure: insert a neutral branch contribution at exactly the right mother-code position.

Puncturing phase is part of framing. A one-symbol slip can leave the Viterbi decoder producing plausible but systematically wrong data because every later soft value is assigned to the wrong generator output. A known short frame should test each allowed puncturing phase and reset boundary.

The archived CCSDS 131.0-B-5 profile provides a concrete $K=7$ rate-$1/2$ encoder with connection vectors 171 and 133 octal and specified punctured rates $2/3$, $3/4$, $5/6$, and $7/8$. It also specifies output ordering and historical symbol-inversion details; those details must be copied from the chosen issue, not reconstructed from polynomial names. CCSDS now lists 131.0-B-6 (April 2026) as the current issue, superseding B-5, so a new implementation must verify its mission profile against Issue 6 rather than treating the archived 2023 issue as current.

Catastrophic and recursive encoders #

A feed-forward encoder is catastrophic if some infinite-weight input sequence produces a finite-weight output sequence: many information errors can become almost invisible on the channel. For a binary rate-$1/n$ feed-forward encoder, a common algebraic test is that the generator polynomials must not share a nontrivial common factor.

Recursive systematic convolutional (RSC) encoders deliberately feed a polynomial back into the state update and transmit the input systematically. Recursion is essential to turbo-code behavior because a finite-weight input can produce a long parity response. It is not the same as a catastrophic feed-forward realization; rational generator notation, feedback convention, and termination all need an explicit state-space definition.

Viterbi, BCJR, and sequence estimation #

Viterbi returns the most likely sequence under the trellis/channel model. It does not in general return the individually most likely value of every bit. BCJR computes posterior probabilities or bit LLRs by forward and backward recursions and is the natural constituent algorithm for iterative decoding. Sequential decoders explore promising paths with variable effort and can be attractive for long-constraint-length codes, but their worst-case work is less predictable.

The same Viterbi dynamic program also handles finite-state channels for maximum-likelihood sequence estimation (MLSE). There the state represents channel memory rather than encoder memory—or a joint super-trellis represents both. The survivor argument remains valid only if the state contains all memory needed to make future observations independent of the discarded history.

Implementation contract and tests #

Write the contract before optimizing:

• generator polynomials and whether the current input is the MSB or LSB coefficient;
• shift-register direction, state-bit order, and next-state equation;
• encoder output order, serialization order, and any symbol inversion;
• initial/final state and zero-tail, tail-biting, or continuous semantics;
• puncturing matrix, reading order, phase, and reset boundary;
• modulation bit mapping and LLR sign/scale/saturation;
• branch-metric normalization, renormalization, tie-breaking, traceback depth, and output latency.

Then test in increasing scope:

1. exhaust all state/input transitions against a hand-reviewed table;
2. encode short known vectors, including reset and termination boundaries;
3. verify the worked one-error trellis above step by step;
4. compare soft branch metrics with direct channel log-likelihoods;
5. inject punctures as erasures at every phase;
6. compare a long optimized decoder against a simple reference decoder on identical received metrics;
7. sweep $E_b/N_0$, record actual error counts and confidence, and inspect low-weight error events.

Convolutional codes are no longer the universal default for new high-throughput links; LDPC, turbo, and polar families often win at large block lengths or modern parallel hardware. They remain operationally important in space and legacy links, short control channels, and as constituent or conceptual codes. More importantly, the trellis discipline—explicit state, additive likelihood metrics, survivor evidence, and bit-exact boundary contracts—generalizes far beyond one coding family.