Content deleted Content added
added "trellis diagram" paragraph |
|||
Line 13:
<i>n<sub>3</sub></i> = mod2 (<i>m<sub>1</sub></i> + <i>m<sub>-1</sub></i>)<br>
[[Image:Convolutional_encoder.png|frame|none|
===Recursive and non-recursive codes===
Line 19:
The encoder on the picture above is a ''non-recursive'' encoder. Here's an example of a recursive one:
[[Image:Convolutional_encoder_recursive.png|left|thumb|340px|none|
One can see that a data sequence being encoded is here a part of the output (encoded) sequence too (look at the output 2). Such codes are referred to as ''systematic'', other are called ''non-systematic''.
Line 44:
Given that maximum polynom's power (in the transfer functions) is <math>m</math>, ''constraint length'' can be defined as <math>K=m+1</math>.
===Trellis diagram===
A convolutional encoder is a [[finite state machine]]. An encoder with <math>n</math> binary cells will have <math>2^n</math> states.
Imagine that the encoder (shown on Img.1) has '1' in the left memory cell (<math>m_0</math>), and '0' in the right one (<math>m_{-1}</math>). (<math>m_1</math> 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 "01" state or in "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:
[[Image:Convolutional_code_trellis_diagram.png|left|thumb|340px|none|Img.2. A trellis diagram for the encoder on Img.1]]
An actual encoded sequence can be represented as a path on this graph.
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.
===Free distance and error distribution===
| |||