Short note: Viterbi decoding algorithm

The Viterbi algorithm is a maximum-likelihood decoding method for convolutional codes. It finds the path through the code trellis whose output sequence is closest to the received sequence (minimum Hamming distance for hard decision, or Euclidean distance for soft decision).

Steps

1. Draw the trellis: 2ᴷ⁻¹ states (K = constraint length), with branches labelled by encoder output bits.
2. For each received symbol group, compute the branch metric = Hamming distance between received bits and each branch's output.
3. Add–compare–select: for every state, add branch metric to the path metric of each incoming path; keep the smaller one as the survivor, discard the other.
4. Repeat for the whole sequence (the encoder is flushed to state 00 with tail zeros).
5. Trace back the survivor ending in state 00 with the smallest metric; its input bits are the decoded data.

Example: rate 1/2, K = 3 code, g₁ = 111, g₂ = 101.

• Data 1011 + two tail zeros → transmitted 11 10 00 01 01 11.
• Received with one error: 11 10 10 01 01 11.
• The survivor ending in state 00 has metric 1 and gives 1 0 1 1 0 0, so the error is corrected.

Features: complexity grows as 2ᴷ⁻¹ (linear in message length); soft-decision gives about 2 dB extra gain. Used in GSM, IS-95 and as the MLSE equalizer.