Convolutional coder with example

A convolutional coder is a forward error-correcting encoder with memory. It passes the message bits through a shift register and forms output bits as modulo-2 sums of selected stages, so each output depends on the present bit and the previous $K-1$ bits. With $k$ inputs and $n$ outputs per step, the code rate is $r=k/n$; $K$ is the constraint length.

Example: rate 1/2, K = 3

Generators $g^{(1)}=(1,1,1)$, $g^{(2)}=(1,0,1)$:

$$c_i^{(1)}=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_i^{(2)}=m_i\oplus m_{i-2}$$

 Encoder: g1 = 111, g2 = 101 (K = 3, rate 1/2)

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |          |           |
        +---(+)----+-----------+---> c1 = mi+mi-1+mi-2
        |                      |
        +---(+)----------------+---> c2 = mi+mi-2
            output per bit: c1 c2

Encoding message $10011$ (plus 00 to flush):

Output: 11 10 11 11 01 01 11.

Representations

• Code tree: each input bit splits a branch (up = 0, down = 1), labelled with output bits.
• State diagram: 4 states (a = 00, b = 10, c = 01, d = 11), e.g. a goes to b with output 11 on input 1.
• Trellis: the state diagram drawn over time; used by the decoder.

Decoding

The Viterbi algorithm compares the received sequence with every trellis path, keeps the best (minimum distance) path into each state, and outputs the survivor; it is a maximum-likelihood decoder. The free distance of this code is $d_{free}=5$, so it can correct 2 errors within a short span.