4.6.3 Viterbi Decoding Algorithm
The Viterbi decoding algorithm is a cost-effective, near-optimum method for decoding convolutional codes and is widely used in modern digital communication systems, including satellite, mobile, and deep-space links. The algorithm provides maximum-likelihood sequence estimation by efficiently searching the trellis for the most probable path corresponding to the transmitted sequence.
Viterbi decoding is considered sub-optimal only in the sense that the search depth through the trellis is truncated to a limited “traceback depth,” typically four to five times the constraint length (4–5 × K), to reduce complexity. The resulting performance degradation is negligible for most practical systems.
The algorithm is based on the principle that when two or more paths in the trellis converge to the same state, only the path with the lowest cumulative path metric can possibly belong to the optimal path; the others can be discarded. The branch metric represents the distance between a received codeword and the expected codeword associated with a particular branch in the trellis. For hard-decision decoding, this distance is the Hamming distance; for soft-decision decoding, it is the Euclidean distance.
Branch metrics are calculated by determining the minimum distance between each received codeword and the codeword on the corresponding branch of the trellis. Figure 4.23 illustrates how each branch on the decoder trellis is then labelled with the branch metric representing the difference between the branch codeword and the received codeword.
As illustrated in Figure 4.24, the decoder uses the branch metrics to determine the most likely (minimum distance) path through the trellis to arrive each of the states. The path metric or a state is computed as the sum of branch metrics along the path leading to that state. When multiple paths merge into a state, the decoder compares their path metrics and retains only the path with the smallest cumulative metric, discarding all others. This recursive selection process continues through the trellis until the end of the sequence, at which point the traceback identifies the most likely transmitted bit sequence. Since the path metric for the upper path in Figure 4.24 is lower than the metric for the lower path, the upper path is assumed to be a portion of the optimum path.
So, at any point in the decoding trellis, there will be two options for candidate paths into each state. The decoder compares the path metrics for each state and discards the path with the largest path metric as being the least likely to belong to the optimal path through the decoder. If two paths have the same metric one is discarded arbitrarily.
The preceding discussion of Viterbi decoding assumed hard decisions. Soft-decision Viterbi decoding is similar except that, instead of the Hamming distance being used as branch metrics, the Euclidean distance between the received symbol and the transition symbol is used. Pruning then continues as for hard-decision coding.
Soft-decision Viterbi decoding offers approximately a 2-dB improvement in performance compared with hard-decision decoding, as it makes fuller use of the analog information in the demodulated signal. However, it is computationally more intensive and is typically used where link budgets are tight, such as in satellite and deep-space communication systems.
Back to reading