Field Guide · algorithm

Also known as: convolutional code, convolutional coding

A convolutional code is a forward-error-correction code in which each output bit depends not on one input bit but on a sliding window of the most recent input bits.1 Unlike a block code, which chops data into independent codewords, a convolutional encoder produces a continuous coded stream whose redundancy is spread across time — which is exactly what lets a decoder like the Viterbi algorithm exploit context to correct errors.

in ⊕ ⊕ out1 out2
A convolutional code outputs parity bits computed from the current and recent input bits via a shift register.

How it works

The encoder is a shift register: input bits march through a chain of memory cells, and after each shift the encoder XORs together a fixed pattern of taps to form its output bits. A few parameters fully describe it:

  • Constraint length (K) — the number of input bits that influence each output, i.e. the register length plus one. Larger K means more error-correcting power but an exponentially larger decoding trellis (2^(K−1) states).
  • Code rate (k/n) — input bits per output bits. A rate-1/2 encoder emits two bits per input bit; rate 1/3 emits three, adding more protection at the cost of bandwidth.
  • Generator polynomials — the tap patterns, one per output, conventionally written in octal (the classic K=7, rate-1/2 code uses generators 171 and 133).

Because the output is a running (convolution-like) function of the input, the code has a trellis structure, and the receiver finds the most likely transmitted path through that trellis with the Viterbi algorithm, recovering the bits even when several are wrong.

Variants

  • Puncturing — a base rate-1/2 code can be turned into rate 2/3, 3/4, and so on by deliberately not transmitting some coded bits according to a fixed puncturing pattern; the decoder inserts erasures where the bits were dropped. This lets one encoder/decoder serve many rates.
  • Recursive systematic convolutional (RSC) codes — feed part of the output back into the register and transmit the raw data bits alongside the parity. Two RSC codes joined by an interleaver form a turbo code, whose iterative decoding approaches the Shannon limit.
  • Trellis-coded modulation — combining the convolutional trellis with the modulation mapping, TCM wins coding gain without spending extra bandwidth.

Relevance to SDR

Convolutional coding is one of the workhorses of digital radio: it protects GSM, satellite and deep-space links, 802.11a/g, and, close to the scanner world, M17 (a K=5 code). GopherTrunk decodes these convolutionally coded fields with a Viterbi decoder to lower the bit-error rate before framing and payload extraction.

Sources

  1. Convolutional code — Wikipedia, for the sliding-window encoder, constraint length, code rate, generator polynomials, and puncturing. ↩

See also

Learn it step by step

From the blog