Short note: Trellis diagram of convolutional encoder

A trellis diagram is a time-expanded state diagram of a convolutional encoder. The encoder states (contents of the memory) are drawn as rows of nodes, time runs left to right, and each branch shows the transition caused by one input bit, labelled with the output bits. Each message traces one path through the trellis; the Viterbi decoder searches the trellis for the closest path.

Assumed encoder ("3-state memory" read as a three-stage shift register, i.e. constraint length $K=3$: the present bit plus 2 memory flip-flops, giving $2^2=4$ states), rate 1/2, generators $g^{(1)}=111$, $g^{(2)}=101$:

$$c_1=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_2=m_i\oplus m_{i-2}$$

States $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11.

Encoding 1010 (with two 0s to flush)

Encoded sequence: 11 10 00 10 11 00.

Trellis with the message path

      t0     t1     t2     t3     t4     t5     t6
a 00  *      o      o      o      o      *======*
        \                               /
           \                           /
b 10  o      *      o      *      o   /  o      o
               \         /   \      /
                  \   /         \  /
c 01  o      o      *      o      *      o      o


d 11  o      o      o      o      o      o      o
in:      1      0      1      0      0      0
out:    11     10     00     10     11     00

In the full trellis every state has two branches leaving it (input 0 and input 1). After $K-1=2$ steps the pattern of branches repeats at every stage. The path marked with * (= for a horizontal branch) is the unique path for 1010; any received sequence is decoded by finding the path with the minimum Hamming distance from it.