Convolutional Code - Trellis Diagram

Trellis Diagram

A convolutional encoder is a finite state machine. An encoder with n binary cells will have 2n states.

Imagine that the encoder (shown on Img.1, above) has '1' in the left memory cell (m₀), and '0' in the right one (m_-1). (m₁ is not really a memory cell because it represents a current value). We will designate such a state as "10". According to an input bit the encoder at the next turn can convert either to the "01" state or the "11" state. One can see that not all transitions are possible (e.g., a decoder can't convert from "10" state to "00" or even stay in "10" state).

All possible transitions can be shown as below:

An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example.

This diagram gives us an idea about decoding: if a received sequence doesn't fit this graph, then it was received with errors, and we must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea.