Viterbidecoding

Viterbi decoding, named after Andrew J. Viterbi, is a maximum likelihood sequence estimation algorithm used to decode convolutional codes and to perform decoding in certain hidden Markov model applications. It operates on a trellis diagram representing the encoder's finite-state machine, and finds the most probable path through the trellis that could have produced the observed sequence.

For a convolutional encoder with memory m = K-1, the trellis has 2^m states. At each time step, the decoder evaluates transitions from each state to successor states, computes a branch metric from the received symbol and the encoder's expected output for that transition, and updates the best path metric for each state, keeping a predecessor pointer. After processing the whole sequence, the best final state is chosen and the corresponding predecessor pointers are backtracked to produce the estimated input bit sequence.

Hard decision uses simple mismatch counts; soft decision uses Euclidean distances for additive white Gaussian noise channels, producing better performance. Complexity is proportional to (number of states) per time step; memory is O(number of states) for storing path memories.

Applications include decoding convolutional codes in many communication standards; variants such as tail-biting trellises, and soft-output Viterbi for soft decisions. The Viterbi algorithm provides a hard or soft output; it contrasts with the BCJR algorithm, which yields posterior probabilities for each bit.