Ferkans — Interactive Telecom Tutor

Definition:
Convolutional Code

A convolutional code with rate $1/n$ and constraint length $K$ encodes one input bit at a time by combining it with the $K - 1$ previous input bits through $n$ linear modulo-2 functions (generator polynomials).

The encoder has $K - 1$ memory elements (shift registers), so the encoder state is one of $2^{K-1}$ possible states. The output at each time step is $n$ coded bits.

The generator polynomials $g_1, g_2, \ldots, g_n$ specify which register taps are XOR-ed to produce each output bit.

Unlike block codes, convolutional codes operate on a continuous stream. The constraint length $K$ determines the code's memory and, together with the generators, its free distance.

Definition:
Trellis Representation

The trellis of a convolutional code is a graph that unfolds the encoder state diagram over time. At each time step $t$ :

Each node represents one of the $2^{K-1}$ encoder states.
Each branch represents a state transition caused by an input bit, labelled with the $n$ output bits.

The trellis has a regular structure: every column (time step) has the same set of $2^{K-1}$ states, and the branching pattern repeats.

A valid codeword corresponds to a path through the trellis starting from the all-zero state.

The trellis provides the foundation for efficient ML decoding via the Viterbi algorithm and soft-output decoding via the BCJR algorithm.

Viterbi Algorithm (ML Sequence Decoding)

The Viterbi algorithm finds the maximum-likelihood path through

the trellis in

O(L \cdot 2^{K-1})

operations, where

L

is the

sequence length.

Steps:

1. Initialise: Set the metric of the all-zero state to 0 and

all other states to

-\infty

.

2. Recursion (for each time step $t = 1, \ldots, L$ ):

For each state

s

, compute the path metric for each incoming

branch:

M_t(s) = \max_{s' \to s} \left[ M_{t-1}(s') + \lambda(\mathbf{r}_t, \mathbf{c}(s' \to s)) \right]

where

\lambda(\mathbf{r}_t, \mathbf{c})

is the branch metric

(correlation for soft decoding, Hamming distance for hard).

Store the winning predecessor (survivor) for each state.

3. Termination: Select the state with the largest final metric

(or the zero state if the trellis is terminated).

4. Traceback: Follow the stored survivors backwards to recover

the ML input sequence.

,

Theorem: Free Distance and Error Probability Bound

The free distance $d_{\text{free}}$ of a convolutional code is the minimum Hamming distance between any two distinct paths in the trellis that diverge from and re-merge to the same state:

$d_{\text{free}} = \min_{\mathbf{c} \neq \mathbf{0} \in \mathcal{C}} w_H(\mathbf{c})$

The bit error probability under ML (Viterbi) decoding with soft decisions on an AWGN channel is bounded by

$P_b \lesssim c_{d_{\text{free}}} \cdot Q\!\left(\sqrt{2 R_c \cdot d_{\text{free}} \cdot E_b/N_0}\right)$

where $c_{d_{\text{free}}}$ counts the information-bit errors associated with paths at distance $d_{\text{free}}$ .

The free distance plays the same role for convolutional codes as $d_{\min}$ does for block codes. The asymptotic coding gain is $\gamma_c = R_c \cdot d_{\text{free}}$ .

Proof

Union bound

The probability that the decoder selects a wrong path diverging at any trellis step is upper-bounded by the union of pairwise error events. Each event at Hamming distance $d$ contributes $Q(\sqrt{2 R_c d E_b/N_0})$ .

Dominant term

At moderate-to-high SNR, the sum is dominated by paths at the minimum distance $d_{\text{free}}$ , giving the stated bound. $\blacksquare$

,

Viterbi Algorithm Step-by-Step

Watch the Viterbi algorithm decode a received sequence on a rate-1/2,

K=3

trellis. The animation shows branch metrics accumulating, survivor paths being selected, and the final traceback recovering the ML sequence.

The Viterbi algorithm finds the maximum-likelihood path through the trellis using dynamic programming in

O(L \cdot 2^{K-1})

time.

Trellis Diagram and Viterbi Decoding

Visualise the trellis of a rate-1/2 convolutional code and watch the Viterbi algorithm find the ML path. Adjust the constraint length and SNR to see how the survivor paths evolve.

Parameters

Constraint length K3

SNR (dB)8

Example: Rate-1/2 Convolutional Code with K = 3

Consider the rate-1/2 convolutional code with constraint length $K = 3$ and generator polynomials $g_1 = (1, 1, 1)$ and $g_2 = (1, 0, 1)$ (in octal: 7 and 5).

(a) Draw the state diagram and determine the number of states.

(b) Find the free distance $d_{\text{free}}$ .

(c) Compute the asymptotic coding gain.

Solution

State diagram

The encoder has $K - 1 = 2$ memory elements, so there are $2^2 = 4$ states: $S_0 = 00$ , $S_1 = 10$ , $S_2 = 01$ , $S_3 = 11$ .

From state $00$ : input 0 $\to$ output $00$ , stay in $00$ ; input 1 $\to$ output $11$ , go to $10$ .

The full state transition table defines the trellis.

Free distance

The minimum-weight path diverging from and re-merging to state $00$ is: $00 \xrightarrow{1/11} 10 \xrightarrow{1/10} 11 \xrightarrow{0/01} 01 \xrightarrow{0/11} 00$ ... actually the minimum path gives output $11, 10, 11$ with weight 5.

$d_{\text{free}} = 5$ for this code (a well-known result).

Coding gain

Asymptotic coding gain: $\gamma_c = R_c \cdot d_{\text{free}} = \frac{1}{2} \times 5 = 2.5$

In dB: $10\log_{10}(2.5) = 3.98$ dB. $\blacksquare$

BCJR/MAP Decoding for Soft Outputs

The BCJR algorithm (Bahl, Cocke, Jelinek, Raviv, 1974) computes the a posteriori probability (APP) for each information bit given the entire received sequence. Unlike the Viterbi algorithm (which finds the best sequence), BCJR minimises the bit error probability.

The key outputs are log-likelihood ratios (LLRs):

$L(u_t \mid \mathbf{r}) = \ln \frac{P(u_t = 0 \mid \mathbf{r})}{P(u_t = 1 \mid \mathbf{r})}$

The BCJR algorithm uses forward ( $\alpha$ ) and backward ( $\beta$ ) recursions through the trellis, combined with branch metrics ( $\gamma$ ), to compute these LLRs. Its complexity is the same order as Viterbi: $O(L \cdot 2^{K-1})$ .

BCJR is essential for iterative decoding in turbo codes, where the soft outputs of one decoder are fed as soft inputs to another.

Quick Check

A rate-1/2 convolutional code has constraint length $K = 9$ . How many states does the Viterbi decoder track at each time step?

9

256

512

81

Correction:

256

The decoder tracks $2^{K-1} = 2^8 = 256$ states. This is why large constraint lengths become computationally expensive.

Common Mistake: Viterbi Complexity Grows Exponentially with K

Mistake:

Assuming that increasing the constraint length $K$ always gives better performance at manageable complexity.

Correction:

The Viterbi decoder complexity is $O(2^{K-1})$ per decoded bit. Doubling $K$ squares the number of states. In practice, $K \leq 9$ (256 states) is typical for Viterbi decoding. For larger effective memories, turbo codes or LDPC codes achieve better performance with iterative decoding at linear complexity per iteration.

Historical Note: Andrew Viterbi and the Viterbi Algorithm (1967)

1967

Andrew Viterbi published his dynamic-programming decoding algorithm in 1967 while at UCLA. Initially considered of theoretical interest, the Viterbi algorithm became the dominant decoding method for convolutional codes in the 1970s when hardware implementations became feasible. It was adopted in the NASA deep-space probes, the GSM mobile standard, and countless other systems. Viterbi co-founded Qualcomm in 1985, which applied convolutional coding to CDMA cellular systems.

Trellis

A time-indexed graph representing the state transitions of a convolutional encoder. Each path through the trellis corresponds to a valid coded sequence.

Viterbi Algorithm

A dynamic-programming algorithm that finds the maximum-likelihood path through a trellis in complexity linear in the sequence length and exponential in the constraint length.

Free Distance

The minimum Hamming distance between any two paths in the trellis of a convolutional code. Determines the asymptotic error performance under ML decoding.

Constraint Length

The parameter $K$ of a convolutional code, equal to the number of input bits that influence the current output (one current + $K-1$ past bits). The encoder has $2^{K-1}$ states.

Convolutional Codes

Definition: Convolutional Code

Definition: Trellis Representation