Logo der Uni Stuttgart
Viterbi algorithm
The Viterbi algorithm is a maximum-likelihood decoding algorithm. It is a routing algorithm to find the path with the minimal accumulated Hamming distance $ d_{\mathrm{H}} $ or squared Euclidean distance $ \Delta[\cdot] $. It decodes a received sequence by comparing to the codeword bits along trellis diagrams. To find the most likely codeword bits, the Viterbi algorithm calculates the branch metric $b_{i,p}$ of each trellis edge and adds them up to a comparable path metric $B_{I,p}$ of all previous edges of one path:

$$ B_{I,p} = \sum_{i=0}^{I}b_{i,p}. $$

When two edges enter a state, the Viterbi algorithm selects the one with smaller path metric as the survivor path, while the path with larger path metric dies.

The hard decision Viterbi algorithm calculates branch metrics based on the Hamming distance $ d_{\mathrm{H}} $ between codeword bits $c_{i,p}$ and the received symbols from a binary symmetric channel $r_{i,p}$: $$ b_{\mathrm{H},i,p} = d_{\mathrm{H}}(c_{i,p},r_{i,p}) = |c_{i,p}-r_{i,p}|. $$

The soft decision Viterbi algorithm calculates branch metrics based on the squared Euclidean distance $ \Delta[\cdot] $ between codeword bits $c_{i,p}$ and the received symbols from an additive white Gaussian noise channel $r_{i,p}$:

$$ b_{\mathrm{S},i,p} = \Delta [c_{i,p},r_{i,p}]= (c_{i,p}-r_{i,p})^2. $$