EC-23.3 Convolutional Codes, and the Viterbi Decoder

What this is and why it exists

A convolutional encoder has no block boundary.

It is a small shift register whose output depends on the last few inputs. The code is therefore a continuous stream rather than separate words. That suits a link that never stops.

Decoding it optimally means finding the most likely path through a trellis. The algorithm that does so is one of the genuinely beautiful results in engineering. Working through a small example by hand is worth more than reading about it three times.

The vocabulary

• Constraint length — how many input bits influence the current output.
• State — the contents of the encoder's shift register.
• State diagram — the graph of states and the transitions between them.
• Trellis — the state diagram unrolled through time.
• Path — one route through the trellis, corresponding to one input sequence.
• Survivor — the best path found so far into a given state.
• Branch metric — the cost of one transition, given what was received.
• Traceback depth — how far back the decoder looks before committing to a decision.
• Free distance — the smallest distance between two distinct paths.

The mental model

The encoder is a shift register with a few taps. At each moment the output depends on the current input and on the last few, and how many is the constraint length. That number sets both the strength of the code and the cost of decoding it, because the number of states grows exponentially with it.

Draw the machine twice. The state diagram shows which state each transition leads to. The trellis shows the same transitions repeated column by column through time. Decoding is a search over the trellis, so being able to draw one accurately is the prerequisite for everything after.

Now the insight. At each stage, several paths arrive at each state. Only the best of them can ever be part of the best overall path, because any continuation is available to all of them equally. So all the others are discarded immediately. That single observation turns an exponential search into a linear one, and it is the whole of the Viterbi algorithm.

The bookkeeping is small. For each state, keep one survivor path and its accumulated cost. At each new column, extend every survivor, keep the best arrival at each state, and discard the rest.

Soft decisions improve this for free. Instead of comparing decided bits, accumulate a cost built from the demodulator's confidence. The algorithm is otherwise unchanged, and the improvement is around two decibels, which is a rare bargain.

Two practical points. The survivors converge after a few constraint lengths. A decoder can therefore output a decision that far behind the present, rather than waiting for the end. That traceback depth sets both memory and latency. And the free distance predicts the error rate at high signal-to-noise ratio, which lets two candidate codes be compared before either is built.

What you should now be able to explain or do

• Draw the state diagram and trellis for a small convolutional encoder.
• Trace the Viterbi algorithm through several columns by hand.
• Explain why discarding all but one survivor per state loses nothing.
• Say what soft decisions change in the algorithm and what they buy.
• Choose a traceback depth and say what it costs in memory and latency.
• Use free distance to compare two codes before implementing either.

Check yourself