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. $$

$$ 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

The

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