Editing Convolutional code (section)

== Trellis diagram ==
{{See also|Trellis (graph)|Trellis coded modulation}}

A convolutional encoder is a [[Finite-state machine|finite state machine]]. An encoder with ''n'' binary cells will have 2<sup>''n''</sup> states.

Imagine that the encoder (shown on Img.1, above) has '1' in the left memory cell (''m''<sub>0</sub>), and '0' in the right one (''m''<sub>−1</sub>). (''m''<sub>1</sub> 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 for (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:

[[Image:Convolutional code trellis diagram.svg|left|thumb|340px|Img.6. A trellis diagram for the encoder on Img.1. A path through the trellis is shown as a red line. The solid lines indicate transitions where a "0" is input and the dashed lines where a "1" is input.]]

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.