Convolutional codes and Viterbi decoding

A convolutional code has memory. Where a block code such as Reed-Solomon chops the data into independent chunks, a convolutional encoder pushes the input bits through a shift register and, for every bit that goes in, emits several bits computed from the current bit and the last few. There is no block boundary. Each input bit influences a run of output bits, and it is that overlap the decoder exploits.

Viterbi decoding is the matching receiver algorithm: it finds the single most likely transmitted sequence given what arrived, rather than deciding each bit in isolation.

What it is

Three numbers describe a convolutional code:

• the code rate k/n: k bits in, n bits out per step. Rate 1/2 doubles the data;
• the constraint length K: how many input bits the register holds, so how far each bit's influence reaches;
• the generator polynomials: which register taps are XORed to form each output.

CCSDS 131.0-B specifies rate 1/2, K = 7, generators 0o171 and 0o133, with one output inverted, and that combination is so widespread that "the standard convolutional code" usually means exactly it. It buys roughly 5 dB of coding gain with soft decision, which on a link budget is the difference between a dish and no dish.

How Viterbi decoding works

The encoder is a state machine: with K = 7 the register holds 6 past bits, so there are 2^6 = 64 states, and each state has exactly two outgoing transitions, one per input bit. Draw those states against time and you get a trellis.

The decoder walks the trellis one step per received symbol pair:

1. compute a branch metric for every transition, the distance between what that transition would have transmitted and what actually arrived;
2. for each state, add the branch metric to the path metric of each of the two paths reaching it, compare, and keep only the better one (this is the add-compare-select step, and discarding the loser is what stops the work from growing exponentially);
3. once you are far enough ahead, trace back through the surviving decisions to read out the bits. A traceback depth of about 5K, so around 35 symbols for K = 7, is deep enough that the surviving paths have almost certainly merged.

Soft decision is where the free performance is. If the demodulator hands the decoder a confidence value per symbol rather than a hard 0 or 1, the branch metrics carry that confidence and the code gains roughly 2 dB over hard decision, for no extra bandwidth. Throwing away the soft values before the decoder is a common and expensive mistake.

Puncturing

Rate 1/2 is often more redundancy than a good link needs. Puncturing deletes selected output bits according to a fixed pattern, giving rate 2/3, 3/4, 5/6 or 7/8 out of the same mother code. The decoder inserts a neutral, zero-confidence symbol at each punctured position and runs the same trellis. One encoder and one decoder therefore serve a whole family of rates, which is why puncturing is everywhere from satellite links to Wi-Fi.

Why it sits next to Reed-Solomon

Convolutional codes are excellent against random bit errors and poor against bursts, because a burst corrupts several consecutive trellis steps at once. When a Viterbi decoder does fail it fails in a run, which is precisely the error pattern a symbol-oriented block code handles best. So the classic chain is Reed-Solomon outer, interleaver, convolutional inner, and the receiver undoes it in reverse. See Wiki: reed-solomon for the outer half.

Working with it

• Phil Karn's libfec is the reference C implementation for the CCSDS K = 7, rate 1/2 code, with the create_viterbi27 / init_viterbi27 / update_viterbi27_blk / chainback_viterbi27 sequence.
• GNU Radio's gr-fec provides fec.cc_decoder, parameterised by constraint length, rate and generator polynomials, with a negative polynomial marking an inverted output.
• gr-satellites and satdump both ship ready-made CCSDS Viterbi blocks and are the practical route for a real downlink.
• In Python, commpy is enough to experiment on the bench:

import numpy as np
from commpy.channelcoding import Trellis, conv_encode, viterbi_decode

trellis = Trellis(np.array([6]), np.array([[0o171, 0o133]]))   # K = 7, rate 1/2
coded = conv_encode(bits, trellis)
decoded = viterbi_decode(coded.astype(float), trellis, tb_depth=35,
                         decoding_type="unquantized")

Pitfalls

• Generator polynomials are octal by convention. 0o171 is 121 decimal, not 171. Writing them as decimal silently builds a different code.
• Phase and inversion ambiguity. After demodulation you may have the two output streams swapped, or every bit inverted. A Viterbi decoder given the wrong one of the four combinations produces confident noise, so real receivers simply try them and keep the one whose path metric is best.
• The decoder needs the state cleared between blocks if the encoder terminated the trellis; run it as a continuous stream when the encoder did not.
• Convolutional is legacy on new missions. CCSDS now specifies turbo and LDPC codes for high-rate links, which get closer to the Shannon limit. The convolutional code survives on low-rate and older spacecraft, which is exactly the traffic an amateur ground station hears.
• Coding gain is not free bandwidth. Rate 1/2 doubles the symbol rate for the same data rate, so it widens the occupied spectrum.

Further reading

• Wiki: reed-solomon
• Wiki: ccsds
• Wiki: sdr
• Wiki: lora
• Wiki: gnss