Short note: Convolutional codes

A convolutional code is an error-correcting code in which the encoder has memory: each group of output bits depends on the current input bit and on the previous $K-1$ input bits stored in a shift register. The code is described by $(n,k,K)$: $k$ input bits produce $n$ output bits, giving code rate $r=k/n$, and $K$ is the constraint length.

Encoder

A rate-1/2, $K=3$ encoder with generators $g^{(1)}=(1,1,1)$ and $g^{(2)}=(1,0,1)$:

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |  \        |         /  |
        |   \--(+)--+--------/   |   c1 = mi+mi-1+mi-2
        |                        |
        +---------(+)------------+   c2 = mi+mi-2
                 output: c1 c2 c1 c2 ...

Each output is the modulo-2 convolution of the input with a generator sequence: $c_i^{(j)}=\sum_l g_l^{(j)}m_{i-l}$.

Example: input 1 0 0 1 1 (plus two flushing 0s) gives 11 10 11 11 01 01 11.

Representations

• Code tree: branches up for 0, down for 1, labelled with output bits.
• Trellis diagram: states (contents of memory) against time; repeats after $K-1$ steps.
• State diagram: $2^{K-1}$ states with transitions labelled input/output.

Decoding

The Viterbi algorithm (maximum-likelihood) finds the trellis path with minimum Hamming distance from the received sequence; sequential decoding is used for large $K$.

Features

• Works on a continuous bit stream, no block division.
• Strong error correction with soft-decision decoding; free distance $d_{free}$ measures power.
• Used in GSM, satellite and deep-space links, Wi-Fi (often with interleaving).