46.09.01 · information-theory / convolutional-classical

Convolutional Codes: Trellis Structure, the Viterbi Algorithm, and Free Distance

shipped3 tiersLean: none

Anchor (Master): MacWilliams & Sloane 1977 The Theory of Error-Correcting Codes (North-Holland) Chapter 11-12; Viterbi 1967 Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm; Forney 1973 The Viterbi Algorithm

Intuition Beginner

Imagine a conveyor belt carrying bits one at a time. As each bit enters, it slides into a row of storage cells called a shift register. Each cell holds one bit. When a new bit arrives, every existing bit shifts one position to the right, and the oldest bit falls off the end. The register always holds the most recent few bits.

Now attach some XOR gates to this register. Each gate reads a fixed subset of the register cells and outputs their parity (sum mod 2). If the register has two cells and you attach two XOR gates, each gate reads a different combination of cells. Every time a new input bit arrives, each gate produces one output bit. With one input and two outputs, you get a rate-1/2 encoder: it turns one bit into two ^{[source pending]}.

The specific wiring of each XOR gate is determined by its generator polynomial. For a constraint-length-3 encoder (two register cells), the generators $(7, 5)_{8}$ mean: the first gate reads all three tap positions (binary $111$ ), and the second gate reads positions 1 and 3 (binary $101$ ). These octal numbers are a compact way to specify the XOR wiring.

The contents of the shift register at any moment define the encoder's state. With two register cells, there are $2^{2} = 4$ possible states: $00$ , $01$ , $10$ , $11$ . As each input bit arrives, the state changes. The old state and the input bit together determine the new state and the two output bits. This finite-state machine has a natural graphical representation called a trellis.

A trellis diagram arranges the 4 states as dots in a vertical column at each time step, then draws arrows between columns showing which transitions are possible. An input of 0 produces one set of arrows (solid lines, say) and an input of 1 produces another (dashed lines). Each arrow carries a label: the two output bits produced by that transition. Any codeword corresponds to a path through the trellis from left to right ^{[source pending]}.

The decoding problem is this: given a noisy received sequence, find the path through the trellis whose output labels are closest to what was received. This is the Viterbi algorithm, and it works by a principle Andrew Viterbi described in 1967 ^{[source pending]}. At each time step, for each state, keep only the single best path that ends at that state. Discard all worse paths. Then extend the survivors one step forward and repeat.

Think of the trellis as a maze. You are racing through it, and at each intersection (state) you keep only the fastest route that reaches that intersection. By the time you reach the end, the single surviving route is the most likely codeword. This pruning is what makes Viterbi decoding feasible: the number of paths you track never exceeds the number of states, no matter how long the input sequence is.

For our 4-state example, the Viterbi algorithm tracks at most 4 candidate paths at any time. Each path has a cumulative distance score (how many bits differ from the received sequence). At each step, each state receives two incoming candidates (one from an input-0 transition, one from an input-1 transition). The algorithm picks the one with the lower score and discards the other. This is the Add-Compare-Select operation, and it runs in constant time per state per time step ^{[source pending]}.

After processing the entire received sequence, the decoder traces back through the surviving path's history to recover the most likely input sequence. The total work scales as $O (n \cdot 2^{ν})$ where $n$ is the sequence length and $ν$ is the number of register cells. For $ν = 2$ (our example), decoding 1000 input bits requires about 4000 compare-select operations. The algorithm is optimal: it finds the maximum-likelihood codeword, the one most likely to have been transmitted given the channel noise model ^{[source pending]}.

Visual Beginner

Convolutional Encoder (rate 1/2, generators (7,5)_8, constraint length K=3)

Input ---> [+]<----+----+----> Output c^(1)  (generator 111)
            |       |    |
            v       v    v
          [s1] --> [s2]
            |       |    |
            +-------+----+----> Output c^(2)  (generator 101)

XOR taps:
  c^(1) = input XOR s1 XOR s2     (generator 1+D+D^2 = 111_2 = 7_8)
  c^(2) = input XOR s2             (generator 1+D^2   = 101_2 = 5_8)

State = (s1, s2) contents of the shift register.

Trellis for (7,5)_8 encoder, 4 states, first 3 time steps:

  t=0        t=1        t=2        t=3

  S=00 ----00/00--- 00 ----00/00--- 00 ----00/00--- 00
      \              / \              / \              /
       \--1/11-- 10    \--1/11-- 10    \--1/11-- 10
       /              \ /              \ /              \
      / --0/00-- 01    / --0/00-- 01    / --0/00-- 01
  S=01                |                |
      \--1/10-- 11    \--1/10-- 11    \--1/10-- 11

  (etc. --- each state has exactly 2 incoming and 2 outgoing branches.
   Labels: input/output, e.g. "1/11" means input bit 1, output bits 11.)

  Convention: solid line = input 0, dashed = input 1.
  Each path left-to-right through the trellis is one codeword.

Component	Role
Shift register	Stores the most recent $ν$ input bits (encoder memory)
Generator polynomials	Specify which register taps feed each XOR gate
State	Contents of the shift register ( $2^{ν}$ possible values)
Trellis	Graph of states over time; branches labelled with input/output
Viterbi algorithm	Shortest-path search on the trellis (ML decoding)

Figure: Top: the rate-1/2 convolutional encoder with generators $(7, 5)_{8}$ . The input bit feeds into a 2-cell shift register. Two XOR gates produce output bits according to the generator tap patterns. Bottom: the corresponding 4-state trellis over three time steps. Each node is a state (register contents). Each branch is a transition, labelled with the input bit and the resulting output pair. The Viterbi decoder finds the lowest-weight path through this trellis matching the received sequence.

Worked example Beginner

Consider the $(7, 5)_{8}$ rate-1/2 convolutional code. The encoder has constraint length $K = 3$ (memory $ν = 2$ ) and 4 states. We encode the input sequence $1, 0, 1, 1, 0$ starting from state $00$ .

Time 1: Input $1$ . Register contents: $(1, 0)$ . Output $c^{(1)} = 1 \oplus 0 \oplus 0 = 1$ . Output $c^{(2)} = 1 \oplus 0 = 1$ . Transmitted pair: $11$ . New state: $10$ .

Time 2: Input $0$ . Register contents: $(0, 1)$ . Output $c^{(1)} = 0 \oplus 1 \oplus 0 = 1$ . Output $c^{(2)} = 0 \oplus 0 = 0$ . Transmitted pair: $10$ . New state: $01$ .

Time 3: Input $1$ . Register contents: $(1, 0)$ . Output $c^{(1)} = 1 \oplus 0 \oplus 1 = 0$ . Output $c^{(2)} = 1 \oplus 1 = 0$ . Transmitted pair: $00$ . New state: $10$ .

Time 4: Input $1$ . Register contents: $(1, 1)$ . Output $c^{(1)} = 1 \oplus 1 \oplus 0 = 0$ . Output $c^{(2)} = 1 \oplus 0 = 1$ . Transmitted pair: $01$ . New state: $11$ .

Time 5: Input $0$ . Register contents: $(0, 1)$ . Output $c^{(1)} = 0 \oplus 1 \oplus 1 = 0$ . Output $c^{(2)} = 0 \oplus 1 = 1$ . Transmitted pair: $01$ . New state: $01$ .

The transmitted codeword is $11, 10, 00, 01, 01$ .

Now suppose the channel introduces one error and the received sequence is $11, 10, 10, 01, 01$ (the third pair is corrupted from $00$ to $10$ ). The Viterbi decoder computes, for each branch in the trellis, the Hamming distance between the branch label and the received pair. It then finds the path through the trellis with the smallest total distance. The correct path (corresponding to input $1, 0, 1, 1, 0$ ) has total distance 1 (one branch mismatches by one bit). All other paths have distance at least 3. The decoder correctly recovers the input.

Check your understanding Beginner

Formal definition Intermediate+

Let $F_{2} = {0, 1}$ denote the binary field and $F_{2} [D]$ the ring of polynomials in the indeterminate $D$ with coefficients in $F_{2}$ .

Definition (Convolutional encoder). A rate- $k / n$ convolutional encoder is a linear map from $F_{2} [D]^{k}$ to $F_{2} [D]^{n}$ specified by a $k \times n$ polynomial generator matrix $G (D)$ . For the common case $k = 1$ , the encoder is fully specified by $n$ generator polynomials $g^{(1)} (D), g^{(2)} (D), \dots, g^{(n)} (D)$ , and encoding is:

c^{(j)} (D) = u (D) \cdot g^{(j)} (D), j = 1, \dots, n,

where $u (D) = u_{0} + u_{1} D + u_{2} D^{2} + \dots$ is the input polynomial and $c^{(j)} (D)$ is the $j$ -th output polynomial ^{[source pending]}.

The constraint length $K$ of the encoder is one plus the maximum degree among the generator polynomials: $K = 1 + max_{j} de g g^{(j)}$ . The encoder memory is $ν = K - 1$ . The physical interpretation is that each output at time $t$ depends on the current input bit and the $ν$ most recent input bits stored in a shift register.

Example. For the $(7, 5)_{8}$ code, the generators are $g^{(1)} (D) = 1 + D + D^{2}$ and $g^{(2)} (D) = 1 + D^{2}$ . The constraint length is $K = 3$ (memory $ν = 2$ ), and the rate is $1/2$ . The generator matrix is the $1 \times 2$ polynomial matrix $G (D) = [1 + D + D^{2}, 1 + D^{2}]$ .

Definition (Trellis section). The trellis at time $t$ is a directed graph whose vertices are the $2^{ν}$ states $s \in {0, 1}^{ν}$ . For each state $s$ and each input symbol $u \in F_{2}$ , there is a directed edge from state $s$ at time $t$ to state $s^{'}$ at time $t + 1$ , where $s^{'}$ is determined by shifting the register contents and inserting $u$ . The edge is labelled with the input/output pair $(u, c)$ where $c \in F_{2}^{n}$ is the output produced by input $u$ when the register holds state $s$ ^{[source pending]}.

The full trellis for a sequence of $L$ input symbols consists of $L + 1$ columns of $2^{ν}$ state nodes (assuming the encoder starts and ends in state $0$ ), connected by $2 \cdot 2^{ν}$ branches per section. Each path through the trellis from the initial state to the terminal state corresponds to one codeword.

Counterexamples to common slips

Convolutional codes are not block codes. A block code of length $n$ processes $n$ symbols as a unit. A convolutional code processes a potentially infinite stream of input symbols, and each output symbol depends on a sliding window of inputs. The "block length" of a convolutional code is not a fixed parameter; it is the length of the input sequence being encoded.
The Viterbi algorithm does not produce soft outputs. Viterbi finds the most likely codeword (hard decisions). The BCJR algorithm ^{[source pending]} produces a-posteriori probabilities for each bit (soft decisions). Turbo decoding requires BCJR, not Viterbi, as the component decoder.
Constraint length is not the same as memory. Constraint length $K = ν + 1$ where $ν$ is the memory (number of register cells). The number of states is $2^{ν}$ , not $2^{K}$ . A "constraint length 7" code has $ν = 6$ and $2^{6} = 64$ states.

Key theorem with proof Intermediate+

Theorem (Viterbi optimality). Consider a rate- $1/ n$ convolutional code with memory $ν$ and trellis states ${0, 1, \dots, 2^{ν} - 1}$ . Let $r = (r_{1}, r_{2}, \dots, r_{L})$ be the received sequence, where each $r_{t}$ is an $n$ -tuple. Define the branch metric $d (r_{t}, c (s, u))$ as the Hamming distance between $r_{t}$ and the output $c (s, u)$ associated with input $u$ from state $s$ . The Viterbi algorithm, which at each time $t$ and state $s$ selects the survivor path with minimum cumulative metric:

δ_{t} (s) = s^{'}, u min [δ_{t - 1} (s^{'}) + d (r_{t}, c (s^{'}, u))],

where the minimum is over all predecessor states $s^{'}$ and inputs $u$ such that the transition $(s^{'}, u) \to s$ exists, produces the maximum-likelihood codeword.

Proof. The proof proceeds by induction on the trellis depth. Let $δ_{t} (s)$ denote the minimum cumulative distance among all paths from the initial state at time 0 to state $s$ at time $t$ .

Base case. At $t = 0$ , the encoder is in state $0$ with cumulative metric $δ_{0} (0) = 0$ . All other states have $δ_{0} (s) = \infty$ (unreachable). This correctly records that only the zero state is a valid starting point.

Inductive step. Assume $δ_{t - 1} (s^{'})$ equals the minimum cumulative distance to state $s^{'}$ at time $t - 1$ for all $s^{'}$ . Any path to state $s$ at time $t$ must pass through some predecessor state $s^{'}$ at time $t - 1$ and traverse exactly one branch from $s^{'}$ to $s$ . The cost of such a path is $δ_{t - 1} (s^{'}) + d (r_{t}, c (s^{'}, u))$ . By the induction hypothesis, $δ_{t - 1} (s^{'})$ is the optimal cost to reach $s^{'}$ . The Add-Compare-Select operation computes:

δ_{t} (s) = s^{'}, u : (s^{'}, u) \to s min [δ_{t - 1} (s^{'}) + d (r_{t}, c (s^{'}, u))],

which is the minimum cost of any path from the initial state to $s$ at time $t$ . This follows from the Markov property of the encoder: the future output depends only on the current state, so the optimal path to any future point decomposes into the optimal path to the current state plus the optimal branch ^{[source pending]}.

At the terminal time $L$ , the minimum-metric state gives the ML codeword, and traceback recovers the associated input sequence. $□$

Bridge. The Viterbi algorithm's optimality builds toward iterative turbo decoding in 46.08.02 by establishing the trellis as the natural computational structure for convolutional codes. The same trellis appears in turbo decoding, but with BCJR replacing Viterbi to produce soft outputs. The foundational reason Viterbi works is that the encoder's finite-state Markov structure provides the optimal-substructure property required for dynamic programming, and this is exactly the property that makes the trellis a computational engine for both hard-decision and soft-decision decoding.

Trellis construction for the $(7, 5)_{8}$ code

We now construct the complete trellis for the $(7, 5)_{8}$ code. The four states are labelled by the register contents $s = (s_{1}, s_{2})$ :

State transition table for (7,5)_8 encoder:

Current    Input   Next     Output
State s    u       state    c^(1) c^(2)
--------   ----    ------   -------------
  00         0      00       0  0
  00         1      10       1  1
  01         0      00       1  1
  01         1      10       0  0
  10         0      01       1  0
  10         1      11       0  1
  11         0      01       0  1
  11         1      11       1  0

Verification for state $10$ , input $0$ : the register holds $(s_{1}, s_{2}) = (1, 0)$ . The new input $u = 0$ shifts the register to $(0, 1)$ , so the next state is $01$ . Output $c^{(1)} = u \oplus s_{1} \oplus s_{2} = 0 \oplus 1 \oplus 0 = 1$ . Output $c^{(2)} = u \oplus s_{2} = 0 \oplus 0 = 0$ . The output pair is $10$ , matching the table.

Viterbi algorithm: worked numerical example

We decode the received sequence $r = (11, 10, 10, 01, 01)$ on the $(7, 5)_{8}$ trellis. The encoder starts in state $00$ . We compute the survivor path metrics step by step.

Time 1, received $r_{1} = 11$ . From state $00$ :

Input 0 goes to state $00$ , output $00$ . Distance: $d (11, 00) = 2$ . Metric $δ_{1} (00) = 2$ .
Input 1 goes to state $10$ , output $11$ . Distance: $d (11, 11) = 0$ . Metric $δ_{1} (10) = 0$ .

States $01$ and $11$ are unreachable: $δ_{1} (01) = δ_{1} (11) = \infty$ .

Time 2, received $r_{2} = 10$ . From each reachable state:

From state $00$ (metric 2): input 0 goes to $00$ with output $00$ , distance $d (10, 00) = 1$ , cumulative $2 + 1 = 3$ . Input 1 goes to $10$ with output $11$ , distance $d (10, 11) = 1$ , cumulative $2 + 1 = 3$ .
From state $10$ (metric 0): input 0 goes to $01$ with output $10$ , distance $d (10, 10) = 0$ , cumulative $0 + 0 = 0$ . Input 1 goes to $11$ with output $01$ , distance $d (10, 01) = 2$ , cumulative $0 + 2 = 2$ .

Survivors: $δ_{2} (00) = 3$ , $δ_{2} (10) = 3$ , $δ_{2} (01) = 0$ , $δ_{2} (11) = 2$ .

Time 3, received $r_{3} = 10$ . From each state:

State $00$ (metric 3): to $00$ with output $00$ , cum. $3 + 1 = 4$ . To $10$ with output $11$ , cum. $3 + 1 = 4$ .
State $01$ (metric 0): to $00$ with output $11$ , cum. $0 + 1 = 1$ . To $10$ with output $00$ , cum. $0 + 1 = 1$ .
State $10$ (metric 3): to $01$ with output $10$ , cum. $3 + 0 = 3$ . To $11$ with output $01$ , cum. $3 + 2 = 5$ .
State $11$ (metric 2): to $01$ with output $01$ , cum. $2 + 2 = 4$ . To $11$ with output $10$ , cum. $2 + 0 = 2$ .

Survivors (taking the minimum for each destination state): $δ_{3} (00) = min (4, 1) = 1$ (from $01$ , input 1), $δ_{3} (10) = min (4, 1) = 1$ (from $01$ , input 0), $δ_{3} (01) = min (3, 4) = 3$ (from $10$ , input 0), $δ_{3} (11) = min (5, 2) = 2$ (from $11$ , input 1).

Time 4, received $r_{4} = 01$ . Computing similarly:

State $00$ (metric 1): to $00$ with output $00$ , cum. $1 + 1 = 2$ . To $10$ with output $11$ , cum. $1 + 1 = 2$ .
State $10$ (metric 1): to $01$ with output $10$ , cum. $1 + 2 = 3$ . To $11$ with output $01$ , cum. $1 + 0 = 1$ .
State $01$ (metric 3): to $00$ with output $11$ , cum. $3 + 1 = 4$ . To $10$ with output $00$ , cum. $3 + 1 = 4$ .
State $11$ (metric 2): to $01$ with output $01$ , cum. $2 + 0 = 2$ . To $11$ with output $10$ , cum. $2 + 2 = 4$ .

Survivors: $δ_{4} (00) = min (2, 4) = 2$ , $δ_{4} (10) = min (2, 4) = 2$ , $δ_{4} (01) = min (3, 2) = 2$ (from $11$ , input 0), $δ_{4} (11) = min (1, 4) = 1$ (from $10$ , input 1).

Time 5, received $r_{5} = 01$ . From each state:

State $00$ (metric 2): to $00$ with output $00$ , cum. $2 + 1 = 3$ . To $10$ with output $11$ , cum. $2 + 1 = 3$ .
State $10$ (metric 2): to $01$ with output $10$ , cum. $2 + 2 = 4$ . To $11$ with output $01$ , cum. $2 + 0 = 2$ .
State $01$ (metric 2): to $00$ with output $11$ , cum. $2 + 1 = 3$ . To $10$ with output $00$ , cum. $2 + 1 = 3$ .
State $11$ (metric 1): to $01$ with output $01$ , cum. $1 + 0 = 1$ . To $11$ with output $10$ , cum. $1 + 2 = 3$ .

Survivors: $δ_{5} (00) = min (3, 3) = 3$ , $δ_{5} (10) = min (3, 3) = 3$ , $δ_{5} (01) = min (4, 1) = 1$ (from $11$ , input 0), $δ_{5} (11) = min (2, 3) = 2$ (from $10$ , input 1).

The minimum-metric state at time 5 is state $01$ with metric 1. Tracing back: $01011110101010100$ . Reading the input bits from last to first: $1, 0, 1, 1, 0$ . This matches the original input, confirming the decoder corrects the single error.

Free distance and the transfer-function bound Intermediate+

Definition (Free distance). The free distance $d_{free}$ of a convolutional code is the minimum Hamming weight of any nonzero codeword:

d_{free} = c \neq = 0 min w_{H} (c),

where $w_{H}$ denotes the Hamming weight (number of nonzero symbols) and the minimum is taken over all nonzero codewords produced by any nonzero input sequence starting and ending in state $0$ ^{[source pending]}.

The free distance is the convolutional analogue of the minimum distance of a block code. It determines the error-correcting capability: for maximum-likelihood decoding (Viterbi), any error pattern of weight less than $d_{free} /2$ is guaranteed to be corrected.

Computing $d_{free}$ via the state diagram. The state diagram of the encoder is a directed graph whose nodes are the $2^{ν}$ states and whose edges are the state transitions. Each edge is labelled with $D^{w}$ where $w$ is the Hamming weight of the output symbols on that transition. The free distance is the weight of the lowest-weight closed path through the state diagram that starts and ends at state $00$ and visits at least one nonzero state.

For the $(7, 5)_{8}$ code, the state diagram has 4 states. The all-zero loop (state $00$ to itself with input 0, output weight 0) contributes zero weight and is excluded. The lowest-weight detour from state $00$ is:

00 D^{2} 10 D^{1} 01 D^{2} 00

with total weight $2 + 1 + 2 = 5$ . This detour corresponds to input sequence $1, 0$ (and the register clears after two steps), producing output $11, 10, 11, 01, 01$ . The output weight is $2 + 1 + 2 = 5$ . Therefore $d_{free} = 5$ for the $(7, 5)_{8}$ code.

The transfer function. The augmented state diagram generalizes this by replacing each branch label $D^{w}$ with $D^{w} N^{u} J$ where $u$ is the number of nonzero input bits (information weight) and $J$ counts the number of branches. The transfer function $T (D, N, J)$ from state $00$ back to $00$ (splitting state $00$ into a source and sink) is a generating function whose coefficients enumerate codewords by their output weight, input weight, and length.

Setting $N = J = 1$ gives $T (D) = T (D, 1, 1) = \sum_{d} a_{d} D^{d}$ , where $a_{d}$ counts the number of codewords of weight $d$ . For the $(7, 5)_{8}$ code, $T (D) = D^{5} / (1 - 2 D) = D^{5} + 2 D^{6} + 4 D^{7} + 8 D^{8} + \dots$ , confirming $d_{free} = 5$ with one codeword at that weight, two codewords at weight 6, and so on ^{[source pending]}.

Error probability bound. On the binary symmetric channel with crossover probability $p$ , the first-event error probability (probability that the Viterbi decoder selects a wrong path at the first divergence from the correct path) is bounded by:

P_{e} \leq T (D)_{D = 2 p (1 - p)} .

This union bound counts all possible error events, each weighted by the probability that the noise causes a path of that weight to be selected over the correct path. The bound is tight at low $p$ because the dominant contribution comes from the $d_{free}$ term ^{[source pending]}.

Catastrophic error propagation

Definition (Catastrophic code). A convolutional code is catastrophic if there exists an infinite-weight input sequence that produces a finite-weight codeword. In a catastrophic code, a finite number of channel errors can cause an infinite number of decoding errors.

Theorem (Non-catastrophic condition). For a rate- $1/ n$ convolutional code with generators $g^{(1)} (D), \dots, g^{(n)} (D)$ , the code is non-catastrophic if and only if:

g cd (g^{(1)} (D), g^{(2)} (D), \dots, g^{(n)} (D)) = 1,

i.e., the generators have no common polynomial factor other than $1$ ^{[source pending]}.

Proof sketch. If $h (D)$ divides all generators, then the input $1/ h (D)$ produces output $(g^{(1)} / h, \dots, g^{(n)} / h)$ . Since $1/ h (D)$ has infinite weight (its coefficients do not vanish), this maps an infinite-weight input to a finite-weight output, which is catastrophic. Conversely, if the generators are coprime, no such input exists: by the Bezout identity, there exist polynomials $a^{(j)} (D)$ such that $\sum_{j} a^{(j)} (D) g^{(j)} (D) = 1$ , which means the encoding map is injective on the input weight. $□$

The $(7, 5)_{8}$ code is non-catastrophic: $g cd (1 + D + D^{2}, 1 + D^{2}) = g cd (1 + D + D^{2}, D) = g cd (1, D) = 1$ . A catastrophic example would be generators $(1 + D^{2}, 1 + D)$ which have $g cd = 1 + D$ .

Puncturing

Definition (Punctured convolutional code). Given a rate- $1/ n$ mother code, a puncturing pattern $P$ is a binary matrix of size $n \times p$ where $p$ is the puncturing period. The encoder produces $n$ output symbols per input bit, but only those in positions where $P$ has a $1$ are transmitted; positions with $0$ are deleted ^{[source pending]}.

For a rate- $1/2$ mother code, deleting every fourth parity symbol from the second output stream achieves rate $2/3$ :

P = (1110) .

Over two input bits, the mother code produces 4 output symbols. After puncturing, 3 symbols are transmitted, giving rate $2/3$ . For rate $3/4$ :

P = (111010) .

Over three input bits, 6 symbols become 4 after puncturing, giving rate $3/4$ .

Puncturing allows a single Viterbi decoder to handle multiple rates by inserting "erased" symbols (which contribute zero to the branch metric) at the punctured positions before decoding.

Exercises Intermediate+

Exercise (easy, short answer).

Draw the state transition table for a rate- $1/2$ convolutional encoder with generators $g^{(1)} (D) = 1 + D$ and $g^{(2)} (D) = 1 + D + D^{2}$ (i.e., generators $(3, 7)_{8}$ ). How many states does the trellis have?

Answer

The memory is $ν = 2$ (maximum degree among generators is 2), so the trellis has $2^{2} = 4$ states.

State transitions (state = $(s_{1}, s_{2})$ ):

State	Input	Next state	$c^{(1)} = u \oplus s_{1}$	$c^{(2)} = u \oplus s_{1} \oplus s_{2}$
00	0	00	0	0
00	1	10	1	1
01	0	00	0	1
01	1	10	1	0
10	0	01	1	1
10	1	11	0	0
11	0	01	1	0
11	1	11	0	1

Exercise (medium, numeric).

Run the Viterbi algorithm on the $(7, 5)_{8}$ trellis for the received sequence $r = (11, 01, 10, 11, 00)$ . Assume the encoder starts in state $00$ . Find the ML-decoded input sequence.

Answer

Using the state transition table from the text:

Time 1, $r_{1} = 11$ . From state $00$ : to $00$ (output $00$ , dist $2$ , cum $2$ ); to $10$ (output $11$ , dist $0$ , cum $0$ ). Survivors: $δ_{1} (00) = 2$ , $δ_{1} (10) = 0$ .

Time 2, $r_{2} = 01$ . From $00$ (cum $2$ ): to $00$ (output $00$ , cum $2 + 1 = 3$ ); to $10$ (output $11$ , cum $2 + 2 = 4$ ). From $10$ (cum $0$ ): to $01$ (output $10$ , cum $0 + 1 = 1$ ); to $11$ (output $01$ , cum $0 + 0 = 0$ ). Survivors: $δ_{2} (00) = 3$ , $δ_{2} (10) = 4$ , $δ_{2} (01) = 1$ , $δ_{2} (11) = 0$ .

Time 3, $r_{3} = 10$ . From each: $00 \to 00$ (cum $3 + 1 = 4$ ), $00 \to 10$ (cum $3 + 1 = 4$ ). $01 \to 00$ (output $11$ , cum $1 + 1 = 2$ ), $01 \to 10$ (output $00$ , cum $1 + 1 = 2$ ). $10 \to 01$ (output $10$ , cum $4 + 0 = 4$ ), $10 \to 11$ (output $01$ , cum $4 + 2 = 6$ ). $11 \to 01$ (output $01$ , cum $0 + 2 = 2$ ), $11 \to 11$ (output $10$ , cum $0 + 0 = 0$ ). Survivors: $δ_{3} (00) = 2$ , $δ_{3} (10) = 2$ , $δ_{3} (01) = 2$ , $δ_{3} (11) = 0$ .

Time 4, $r_{4} = 11$ . From each: $00 \to 00$ (output $00$ , cum $2 + 2 = 4$ ), $00 \to 10$ (output $11$ , cum $2 + 0 = 2$ ). $01 \to 00$ (output $11$ , cum $2 + 0 = 2$ ), $01 \to 10$ (output $00$ , cum $2 + 2 = 4$ ). $10 \to 01$ (output $10$ , cum $2 + 1 = 3$ ), $10 \to 11$ (output $01$ , cum $2 + 2 = 4$ ). $11 \to 01$ (output $01$ , cum $0 + 2 = 2$ ), $11 \to 11$ (output $10$ , cum $0 + 1 = 1$ ). Survivors: $δ_{4} (00) = min (4, 2) = 2$ , $δ_{4} (10) = min (2, 4) = 2$ , $δ_{4} (01) = min (3, 2) = 2$ , $δ_{4} (11) = min (4, 1) = 1$ .

Time 5, $r_{5} = 00$ . From each: $00 \to 00$ (output $00$ , cum $2 + 0 = 2$ ), $00 \to 10$ (output $11$ , cum $2 + 2 = 4$ ). $01 \to 00$ (output $11$ , cum $2 + 2 = 4$ ), $01 \to 10$ (output $00$ , cum $2 + 0 = 2$ ). $10 \to 01$ (output $10$ , cum $2 + 1 = 3$ ), $10 \to 11$ (output $01$ , cum $2 + 2 = 4$ ). $11 \to 01$ (output $01$ , cum $1 + 2 = 3$ ), $11 \to 11$ (output $10$ , cum $1 + 1 = 2$ ). Survivors: $δ_{5} (00) = min (2, 4) = 2$ , $δ_{5} (10) = min (4, 2) = 2$ , $δ_{5} (01) = min (3, 3) = 3$ , $δ_{5} (11) = min (4, 2) = 2$ .

Minimum metric at time 5: state $00$ , $10$ , or $11$ all have metric 2. Taking state $00$ (metric 2) and tracing back: $00000001111111100$ . Input sequence (reading backward): $1, 1, 1, 0, 0$ .

Exercise (medium, numeric).

Compute the free distance of the $(3, 7)_{8}$ code (generators $g^{(1)} = 1 + D$ , $g^{(2)} = 1 + D + D^{2}$ ) by finding the lowest-weight nonzero codeword. Use the state diagram approach.

Answer

The state diagram has 4 states. The lowest-weight detour from state $00$ back to $00$ is:

$00 D^{2} 10 D^{2} 01 D^{1} 00$

The branch weights come from the output weights: from state $00$ with input $1$ , outputs are $c^{(1)} = 1, c^{(2)} = 1$ , weight 2. From state $10$ with input $0$ , outputs are $c^{(1)} = 1, c^{(2)} = 1$ , weight 2. From state $01$ with input $0$ , outputs are $c^{(1)} = 0, c^{(2)} = 1$ , weight 1.

Total weight: $2 + 2 + 1 = 5$ . But we must check all possible detours. Another detour: $00 D^{2} 10 D^{0} 11 D^{1} 01 D^{1} 00$ with weight $2 + 0 + 1 + 1 = 4$ . From state $10$ with input $1$ , outputs $c^{(1)} = 0, c^{(2)} = 0$ , weight 0. From state $11$ with input $0$ , outputs $c^{(1)} = 1, c^{(2)} = 0$ , weight 1. From state $01$ with input $0$ , weight 1.

Total: $2 + 0 + 1 + 1 = 4$ . But the first detour has weight 5. The shorter detour has weight 4. Checking: is there a detour of weight 3? No 3-branch detour achieves weight 3 since the initial branch always has weight at least 2.

Therefore $d_{free} = 4$ for the $(3, 7)_{8}$ code. This is less than the $(7, 5)_{8}$ code's $d_{free} = 5$ , illustrating that the choice of generators matters.

Exercise (hard, short answer).

Design a puncturing pattern to achieve rate $3/4$ from the rate- $1/2$ $(7, 5)_{8}$ mother code. Verify the rate by counting transmitted symbols over one puncturing period.

Answer

We need 3 input bits to produce 3 data bits of information, and the transmitted codeword should have 4 channel symbols. The mother code produces $2 \times 3 = 6$ output symbols for 3 input bits. We must puncture (delete) 2 of these 6 symbols.

A standard puncturing pattern for rate $3/4$ from rate $1/2$ is:

P = (111010) .

Over 3 input bits, the mother code produces $(c_{1}^{(1)}, c_{1}^{(2)}, c_{2}^{(1)}, c_{2}^{(2)}, c_{3}^{(1)}, c_{3}^{(2)})$ . The puncturing pattern keeps all first-stream symbols $(c_{1}^{(1)}, c_{2}^{(1)}, c_{3}^{(1)})$ and only the first second-stream symbol $c_{1}^{(2)}$ , deleting $c_{2}^{(2)}$ and $c_{3}^{(2)}$ . This gives $3 + 1 = 4$ transmitted symbols for 3 input bits, achieving rate $3/4$ .

Exercise (hard, short answer).

The Viterbi decoder for a convolutional code with memory $ν = 6$ (64 states) processes a block of $L = 1000$ input bits. What is the computational complexity? Compare this with brute-force ML decoding over all $2^{1000}$ possible input sequences.

Answer

Viterbi complexity: at each of $L = 1000$ time steps, for each of $2^{ν} = 64$ states, the algorithm performs an Add-Compare-Select over 2 incoming branches. Each ACS involves adding two metrics and comparing them: constant work. Total: $O (L \cdot 2^{ν}) = O (1000 \times 64) = 64000$ operations.

Brute-force ML decoding would compute the distance between the received sequence and every possible codeword. There are $2^{1000}$ possible input sequences, each producing a distinct codeword. Computing the distance for one codeword requires $O (1000)$ operations. Total: $O (1000 \times 2^{1000}) \approx 1 0^{304}$ operations, which is infeasible.

The Viterbi algorithm reduces the exponential dependence on $L$ to an exponential dependence on $ν$ (which is small and fixed), with only linear dependence on $L$ .

Lean formalization Intermediate+

Mathlib has Polynomial over Fin 2 (representing $F_{2} [D]$ ), Matrix, and LinearMap infrastructure, but lacks the specific structures needed for convolutional codes. The encoder is a linear map $F_{2} [D]^{k} \to F_{2} [D]^{n}$ specified by a polynomial generator matrix; this could be built from existing components. The trellis is a directed acyclic graph with state-vertex structure indexed by time and state; no such graph type exists in Mathlib. The Viterbi algorithm is shortest-path dynamic programming on this DAG with additive branch metrics, requiring a formalization of path metric accumulation and survivor selection. Free distance computation needs the state-diagram transfer function (a rational function in $D$ ), which requires formalizing signal flow graphs or Mason's gain formula over polynomial rings. A Codex.CodingTheory.Convolutional module defining polynomial encoders, trellis states, and Viterbi decoding would be the load-bearing first step. This unit ships without formalization.

Advanced results Master

Union bound and tangential bound

The transfer-function bound $P_{e} \leq T (D) ∣_{D = 2 p (1 - p)}$ is a union bound: it sums the pairwise error probabilities over all possible error events. This bound is tight at low crossover probabilities $p$ but becomes loose as $p$ approaches the computational cutoff rate $R_{0}$ .

The tangential bound tightens the union bound by accounting for the overlap between error events. For a convolutional code with free distance $d_{free}$ on the BSC with crossover $p$ , the tangential bound on the bit-error probability is:

P_{b} \leq \frac{1}{k} \frac{\partial T ( D , N )}{\partial N}_{N = 1, D = 2 p (1 - p)} .

The derivative with respect to $N$ weights each error event by the number of information-bit errors it causes, giving a bound on the bit-error rate rather than the event-error rate. For the $(7, 5)_{8}$ code, the derivative at $N = 1$ introduces a factor related to the number of nonzero input bits in each detour, which refines the bound ^{[source pending]}.

For the AWGN channel with binary PSK signalling, the pairwise error probability for a codeword at distance $d$ from the correct one is $Q (2 d \cdot E_{b} / N_{0} \cdot R)$ where $Q (x) = (1/ 2 π) \int_{x}^{\infty} e^{- t^{2} /2} d t$ and $R$ is the code rate. The union bound becomes:

P_{e} \leq d = d_{free} \sum \infty a_{d} Q (2 d R E_{b} / N_{0}) .

At high $E_{b} / N_{0}$ , this is dominated by the $d_{free}$ term, giving the asymptotic approximation $P_{e} \approx a_{d_{free}} \cdot Q (2 d_{free} R E_{b} / N_{0})$ ^{[source pending]}.

Sequential decoding

For constraint lengths $ν \geq 10$ (more than 1024 states), the Viterbi algorithm becomes impractical because the number of states grows exponentially. Sequential decoding algorithms --- the Fano algorithm and the stack algorithm --- provide an alternative that avoids exploring the full trellis.

The Fano algorithm (1963) performs depth-first search on the code tree (the tree obtained by "unrolling" the trellis), using a threshold that increases in discrete steps. At each node, the algorithm extends the most promising branch. If the path metric drops below the threshold, the algorithm backs up and tries the other branch, or increases the threshold. The average number of computations per decoded bit is bounded by a constant for rates below the computational cutoff rate $R_{comp} = 1 - lo g_{2} (1 + 2 p (1 - p))$ on the BSC, but the worst case is unbounded (the algorithm can "freeze" on certain noise patterns) ^{[source pending]}.

The stack (Zigangirov-Jelinek) algorithm maintains a sorted list of partial paths ordered by their cumulative metric. At each step, the algorithm extends the top (best) path by one branch and re-inserts the extensions. This avoids the backtracking of the Fano algorithm but requires memory proportional to the stack size.

Sequential decoding achieves near-ML performance with variable computational effort: most frames decode quickly, but a few require extensive searching. This variability makes it unsuitable for real-time applications with strict latency requirements but acceptable for deep-space communication, where throughput can be adjusted via retransmission protocols.

Tail-biting convolutional codes

A tail-biting convolutional code encodes a finite block by starting and ending in the same state. Instead of forcing the encoder to state $00$ by appending $ν$ zero tail bits (which wastes rate), the tail-biting encoder reads the last $ν$ bits of the input block to determine the initial state, so that the final state equals the initial state. This eliminates the rate loss of $ν / L$ caused by termination ^{[source pending]}.

Decoding a tail-biting code is harder than decoding a terminated code because the initial state is unknown. The Viterbi algorithm must be run from all $2^{ν}$ possible initial states, and the best final-to-initial-state match is selected. This multiplies the decoding complexity by $2^{ν}$ , but for small $ν$ (say $ν \leq 8$ ) this is feasible. Tail-biting convolutional codes are used in the GSM cellular standard and in some IEEE 802.11 OFDM modes.

The BCJR algorithm as a soft-output generalization

The Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm computes the a-posteriori probability (APP) for each bit given the entire received sequence. Like Viterbi, it operates on the trellis, but instead of keeping only the best path, it computes the probability of each state transition using a forward-backward procedure ^{[source pending]}.

The forward metric $α_{t} (s)$ is the probability of reaching state $s$ at time $t$ having observed $r_{1}, \dots, r_{t}$ . The backward metric $β_{t} (s)$ is the probability of observing $r_{t + 1}, \dots, r_{L}$ given state $s$ at time $t$ . The branch metric $γ_{t} (s^{'}, s)$ is the joint probability of the transition and the observation. The APP for bit $u_{t}$ is:

Pr (u_{t} = 0 ∣ r) = \frac{\sum _{(s^{'}, s) : u_{t} = 0} α _{t - 1} ( s ^{'} ) γ _{t} ( s ^{'} , s ) β _{t} ( s )}{\sum _{(s^{'}, s)} α _{t - 1} ( s ^{'} ) γ _{t} ( s ^{'} , s ) β _{t} ( s )} .

The log-likelihood ratio $L (u_{t}) = lo g [Pr (u_{t} = 0∣ r) / Pr (u_{t} = 1∣ r)]$ is the soft output. The BCJR algorithm has the same $O (n \cdot 2^{ν})$ complexity as Viterbi but produces per-bit reliability information. This soft output is essential for turbo decoding, where the component decoders exchange reliability information iteratively.

Synthesis. Convolutional codes encode a streaming input through a finite-state shift register, producing a trellis structure that supports optimal ML decoding via the Viterbi algorithm; the free distance determines error-correcting capability and is computed from the state-diagram transfer function; puncturing allows flexible rates from a single mother code; and the BCJR algorithm extends Viterbi to produce soft outputs needed for iterative turbo decoding. The foundational reason convolutional codes dominated practical communications for decades is that the trellis structure provides the right balance: finite-state memory (unlike block codes' memorylessness) enables performance gains through code correlation, while the trellis graph supports efficient optimal decoding (unlike the NP-hard ML decoding of general linear block codes). The central insight is that the Viterbi algorithm exploits the Markov structure of the encoder to convert an exponential search over $2^{L}$ sequences into a tractable $O (L \cdot 2^{ν})$ dynamic program, and this same structure generalizes to the soft-decision BCJR algorithm that underpins modern iterative decoding.

Full proof set Master

Proposition (Transfer function for the $(7, 5)_{8}$ code). The transfer function of the $(7, 5)_{8}$ convolutional code is $T (D) = D^{5} / (1 - 2 D)$ .

Proof. We compute the transfer function using Mason's gain formula on the augmented state diagram. The state diagram has 4 states: $S_{0} = 00$ , $S_{1} = 10$ , $S_{2} = 01$ , $S_{3} = 11$ . We split $S_{0}$ into a source node and a sink node.

The branch gains (using only the output weight variable $D$ ) are:

$S_{0} \to S_{0}$ (input 0, output $00$ ): gain $D^{0} = 1$ . This is the self-loop at state $00$ .
$S_{0} \to S_{1}$ (input 1, output $11$ ): gain $D^{2}$ .
$S_{2} \to S_{0}$ (input 0, output $11$ ): gain $D^{2}$ .
$S_{2} \to S_{1}$ (input 1, output $00$ ): gain $D^{0} = 1$ .
$S_{1} \to S_{2}$ (input 0, output $10$ ): gain $D^{1}$ .
$S_{1} \to S_{3}$ (input 1, output $01$ ): gain $D^{1}$ .
$S_{3} \to S_{2}$ (input 0, output $01$ ): gain $D^{1}$ .
$S_{3} \to S_{3}$ (input 1, output $10$ ): gain $D^{1}$ .

The forward paths from source to sink that avoid revisiting $S_{0}$ are: $S_{0} \to S_{1} \to S_{2} \to S_{0}$ with gain $D^{2} \cdot D^{1} \cdot D^{2} = D^{5}$ , and $S_{0} \to S_{1} \to S_{3} \to S_{2} \to S_{0}$ with gain $D^{2} \cdot D^{1} \cdot D^{1} \cdot D^{2} = D^{6}$ , and so on. The self-loops are at $S_{3}$ (gain $D$ ) and $S_{0}$ (gain $1$ , excluded by splitting).

The state equations (eliminating $S_{1}, S_{2}, S_{3}$ ) give $T (D) = D^{5} / (1 - 2 D)$ , where the denominator arises from the two possible continuations through states $S_{2}$ and $S_{3}$ at each step. The expansion $D^{5} + 2 D^{6} + 4 D^{7} + 8 D^{8} + \dots$ shows that the number of codewords doubles with each additional unit of weight above $d_{free} = 5$ . $□$

Proposition (Free distance lower bound). For a rate- $1/2$ non-catastrophic convolutional code with memory $ν$ and generators of maximum degree $ν$ , the free distance satisfies $d_{free} \leq (ν + 1) \cdot n / k = (ν + 1) \cdot 2$ .

Proof sketch. Any nonzero input sequence of weight 1 produces a codeword. The shortest such input is a single nonzero bit followed by enough zeros to return the encoder to state $0$ . The resulting codeword has at most $(ν + 1)$ nonzero output pairs (one per time step while the nonzero bit is in the register), each contributing at most $n = 2$ nonzero symbols. Thus $d_{free} \leq 2 (ν + 1)$ . For the $(7, 5)_{8}$ code with $ν = 2$ : $d_{free} \leq 6$ , and the actual value is $d_{free} = 5$ , which is close to this upper bound. $□$

Proposition (Viterbi complexity). The Viterbi algorithm for a rate- $1/ n$ convolutional code with memory $ν$ decoding a sequence of $L$ input bits requires $O (L \cdot n \cdot 2^{ν})$ operations.

Proof. The trellis has $L$ sections and $2^{ν}$ states per section. At each state at time $t$ , the algorithm evaluates $2$ incoming branches (one for input 0, one for input 1). Each evaluation requires computing the branch metric (comparing $n$ output symbols to $n$ received symbols, costing $O (n)$ ) and adding it to the predecessor's cumulative metric ( $O (1)$ ). The compare-select operation costs $O (1)$ . Total per state per time step: $O (n)$ . Total over all states and time steps: $O (L \cdot 2^{ν} \cdot n)$ . The traceback costs $O (L)$ , which is dominated. $□$

Connections Master

46.08.02 — Turbo codes use recursive systematic convolutional encoders whose trellis structure is the same as developed here. The BCJR algorithm replaces Viterbi to produce soft outputs for iterative decoding. The puncturing technique from this unit is also used in turbo codes to achieve flexible rates.
40.06.06 — Block codes (Hamming, BCH, Reed-Solomon) are memoryless: each codeword is an independent encoding of a fixed-size block. Convolutional codes introduce finite-state memory, creating correlation between output symbols that spans $ν + 1$ input bits. This memory is what gives convolutional codes their "gain" over memoryless codes of the same rate at short-to-moderate block lengths.
46.08.01 — LDPC codes decode on a bipartite Tanner graph using belief propagation; convolutional codes decode on a trellis using Viterbi/BCJR. The trellis is a chain-structured graph (1D), while the Tanner graph is a sparse bipartite graph (2D). The different graph structures lead to different performance profiles: convolutional codes with Viterbi provide optimal ML decoding at moderate complexity ( $O (2^{ν})$ ), while LDPC codes with belief propagation provide near-ML performance at linear complexity.
46.03.01 — Channel capacity sets the ultimate limit on code performance. Convolutional codes with Viterbi decoding approach within a few dB of capacity for moderate constraint lengths ( $ν \leq 7$ ), but the gap is larger than for turbo or LDPC codes. The computational cutoff rate $R_{comp}$ of sequential decoding is a capacity-like threshold specific to convolutional codes.
37.01.01 — The Viterbi algorithm is a general-purpose shortest-path algorithm for directed acyclic graphs with additive edge weights. It applies to hidden Markov model inference (finding the most likely state sequence given observations), sequence detection in intersymbol interference channels, and speech recognition. The trellis structure is the same as the HMM state-time diagram.

Historical & philosophical context Master

Peter Elias introduced convolutional codes in his 1955 paper "Coding for Noisy Channels" (IRE Convention Record, vol. 3, pp. 37-46). Elias observed that encoding could be given memory by using shift registers, creating a code that operates on continuous data streams rather than fixed blocks. The key advantage over block codes: the decoder can exploit the correlation between consecutive output symbols, providing better performance at short block lengths without the need for algebraic structure.

Andrew Viterbi published his decoding algorithm in 1967, originally as a tool for deriving error bounds rather than as a practical decoder ^{[source pending]}. The algorithm's optimality (it performs maximum-likelihood decoding) was recognized by Forney, who gave it the name "Viterbi algorithm" in his 1973 tutorial paper ^{[source pending]}. Forney demonstrated that the algorithm applies not only to convolutional decoding but to any estimation problem on a finite-state Markov process observed in noise.

Convolutional codes with Viterbi decoding became the standard for satellite and deep-space communication in the 1970s and 1980s. NASA's Voyager program (1977 launch) used a constraint-length-7 convolutional code with Viterbi decoding for the downlink, achieving coding gains of 5-6 dB over uncoded transmission. This coding gain translated directly into transmitter power savings, reducing the size and weight of the spacecraft's antenna and power systems. The same code was used in the Galileo, Magellan, and Cassini missions.

The GSM (2G) cellular standard adopted convolutional codes with constraint lengths 5 and 7 for voice and data channels, decoded by Viterbi. Every mobile phone manufactured between 1991 and the transition to 3G contained a Viterbi decoder. The IEEE 802.11a Wi-Fi standard (1999) used convolutional codes as the mandatory forward error-correction scheme.

The philosophical lesson is that the shift from block codes to convolutional codes represented a change in perspective: from algebraic structure to probabilistic structure. Block codes rely on the algebraic properties of finite fields to guarantee a minimum distance. Convolutional codes rely on the statistical properties of the channel and the encoder's memory to provide coding gain. The Viterbi algorithm is a probabilistic tool (ML estimation on a Markov process), not an algebraic one. This probabilistic perspective prepared the ground for the turbo and LDPC codes of the 1990s, which pushed the probabilistic approach to its logical conclusion: iterative soft-information processing that approaches the Shannon limit.

The transition away from convolutional codes began with the adoption of turbo codes in 3G (1999) and LDPC codes in 5G (2017). However, convolutional codes remain in use for short-block applications (control channels, signalling) where the overhead of iterative decoding is not justified, and in legacy systems. The trellis structure and Viterbi algorithm also live on as subroutines within turbo decoders (as the constituent code) and in equalizers for intersymbol interference channels.

Bibliography Master

@book{macwilliams-sloane1977,
  author    = {MacWilliams, F. J. and Sloane, N. J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977},
}
@article{viterbi1967,
  author  = {Viterbi, A. J.},
  title   = {Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm},
  journal = {IEEE Transactions on Information Theory},
  volume  = {13},
  pages   = {260--269},
  year    = {1967},
}
@article{forney1973,
  author  = {Forney, G. D.},
  title   = {The Viterbi Algorithm},
  journal = {Proceedings of the IEEE},
  volume  = {61},
  pages   = {268--278},
  year    = {1973},
}
@article{elias1955,
  author  = {Elias, P.},
  title   = {Coding for Noisy Channels},
  journal = {IRE Convention Record},
  volume  = {3},
  pages   = {37--46},
  year    = {1955},
}
@article{bahl-cocke-jelinek-raviv1974,
  author  = {Bahl, L. R. and Cocke, J. and Jelinek, F. and Raviv, J.},
  title   = {Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate},
  journal = {IEEE Transactions on Information Theory},
  volume  = {20},
  pages   = {284--287},
  year    = {1974},
}
@article{berrou-glavieux-thitimajshima1993,
  author    = {Berrou, C. and Glavieux, A. and Thitimajshima, P.},
  title     = {Near {Shannon} Limit Error-Correcting Coding and Decoding: {Turbo-Codes}},
  booktitle = {Proc. IEEE Int. Conf. Communications (ICC)},
  pages     = {1064--1070},
  year      = {1993},
}
@book{proakis-salehi2008,
  author    = {Proakis, J. G. and Salehi, M.},
  title     = {Digital Communications},
  edition   = {5th},
  publisher = {McGraw-Hill},
  year      = {2008},
}

Meta Master

This unit introduced convolutional codes from first principles: the shift-register encoder, the trellis as its natural graphical representation, the Viterbi algorithm for optimal ML decoding via dynamic programming on the trellis, and the free distance as the fundamental performance metric computed from the state-diagram transfer function. We covered catastrophic codes, puncturing for rate flexibility, and the BCJR algorithm as the soft-output generalization of Viterbi. The trellis machinery developed here is the direct prerequisite for understanding turbo codes (46.08.02), where recursive systematic convolutional encoders serve as the constituent codes and BCJR provides the soft outputs for iterative decoding. The next step is to see how two such convolutional codes, coupled through an interleaver and decoded iteratively, achieve near-Shannon-limit performance.

Prerequisites

40.06.06
46.03.01

Tier anchors

beginner: MacWilliams & Sloane 1977 The Theory of Error-Correcting Codes (North-Holland) Chapter 11 intro (convolutional encoder as a shift register, trellis diagram as a state machine)
intermediate: MacWilliams & Sloane 1977 The Theory of Error-Correcting Codes (North-Holland) Chapter 11-12 (trellis representation, Viterbi algorithm as dynamic programming, free distance and its bounds)
master: MacWilliams & Sloane 1977 The Theory of Error-Correcting Codes (North-Holland) Chapter 11-12; Viterbi 1967 Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm; Forney 1973 The Viterbi Algorithm

References

MacWilliams, F. J. & Sloane, N. J. A. — The Theory of Error-Correcting Codes · North-Holland (1977). Chapter 11: convolutional codes — encoder as a linear system over a polynomial ring $F_{2} [D]$ , generator matrix $G (D) = [g_{1} (D), g_{2} (D)]$ , trellis diagram, state diagram, and transfer-function bound on error probability. Chapter 12: the Viterbi algorithm as maximum-likelihood sequence detection by dynamic programming on the trellis; complexity $O (2^{ν} \cdot n)$ where $ν$ is the constraint length; truncation depth and path memory.
Viterbi, A. J. — Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm · IEEE Transactions on Information Theory 13 (1967) 260-269. Introduces the Viterbi algorithm as a decoding procedure for convolutional codes: at each time step, for each state, the algorithm selects the path with minimum accumulated Hamming (or Euclidean) distance. Proves optimality (ML decoding) and derives error bounds using the transfer function of the state diagram.
Forney, G. D. — The Viterbi Algorithm · Proceedings of the IEEE 61 (1973) 268-278. Tutorial exposition of the Viterbi algorithm as a general solution to maximum-likelihood estimation in Markov processes. Shows the trellis diagram as the natural state-space representation and the Viterbi algorithm as shortest-path dynamic programming. Applications beyond coding: sequence detection in ISI channels, speech recognition.

Estimated time

beginner: 15m
intermediate: 50m
master: 90m

Intuition Beginner

Visual Beginner

Worked example Beginner

Check your understanding Beginner

Formal definition Intermediate+

Counterexamples to common slips

Key theorem with proof Intermediate+

Trellis construction for the (7,5)8​ code

Viterbi algorithm: worked numerical example

Free distance and the transfer-function bound Intermediate+

Catastrophic error propagation

Puncturing

Exercises Intermediate+

Lean formalization Intermediate+

Advanced results Master

Union bound and tangential bound

Sequential decoding

Tail-biting convolutional codes

The BCJR algorithm as a soft-output generalization

Full proof set Master

Connections Master

Historical & philosophical context Master

Bibliography Master

Meta Master

Trellis construction for the $(7, 5)_{8}$ code