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 (m0), and '0' in the right one (m-1). (m1 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.
Read more about this topic: Convolutional Code
Famous quotes containing the words trellis and/or diagram:
“Then a small rainbow like a trellis gate,
A very small moon-made prismatic bow,
Stood closely over us through which to go.”
—Robert Frost (1874–1963)
“If a fish is the movement of water embodied, given shape, then cat is a diagram and pattern of subtle air.”
—Doris Lessing (b. 1919)