Short note: Convolutional encoding and decoding

Convolutional coding is a forward error-correction method in which each group of k input bits produces n output bits that depend on the current input and the previous (K − 1) inputs stored in a shift register. It is described by (n, k, K), with code rate r = k/n and constraint length K.

Encoding – example (2, 1, 3) encoder, rate 1/2, generators g₁ = 111, g₂ = 101:

 input ->[ m ]->[ s1 ]->[ s2 ]
          |       |       |
          +--(⊕)--+--(⊕)--+---> v1 = m ⊕ s1 ⊕ s2
          |               |
          +------(⊕)------+---> v2 = m ⊕ s2
          output: v1 v2 (alternately)

Input 1011 followed by two flushing zeros gives output 11 10 00 01 01 11. The encoder can be shown as a state diagram, a tree, or a trellis (states = 2ᴷ⁻¹ = 4).

Decoding – the Viterbi algorithm (maximum likelihood) is standard:

1. For each received bit pair, compute branch metrics (Hamming distance) on the trellis.
2. At each state, add-compare-select: keep only the survivor path with the smallest total metric.
3. At the end, trace back from state 00 to get the decoded bits.

Example: received 11 10 10 01 01 11 (one error) is decoded back to 1011, as the best path has metric 1. Soft-decision decoding gives about 2 dB extra gain. Sequential decoding is an alternative for long K.

Used in GSM (rate 1/2, K = 5), IS-95 (K = 9) and satellite links.