JPL's Wireless Communication Reference Website

Chapter: Analog and Digital Transmission, Receiver Design



The Viterbi algorithm

Contributed by Olivier Swedor, EPFL

Maximum likelihood decoding

When a decoder receives a sequence, it has to estimate the sequence that was really sent. The decoder will be optimum if it choses the estimate that maximizes the log-likelihood  function, given by: 

 ln p( r | c )
where r is the received  bits sequence and c the c the code vector applied by the encoder to the input of a discrete memoryless channel. p stands for probability.

For a binary symmetric channel, a maximum-likelihood decoder is equivalent to a minimum distance decoder.
 

The Viterbi algorithm

Since maximum likelihood decoding and minimum distance decoding are the same for a binary symmetric channel, we can decode a convolutional code by choosing the path in the code tree whose output bits are the closest to those from the received sequence. We can also do it in the trellis, because the two representations are equivalent.

The Viterbi algorithm is a maximum-likelihood decoding procedure for convolutional codes.

Let's use the trellis representation of the encoder:

  

We observe that (apart the first levels), there are two branches, wich means two paths, entering each of the states. This means that a minimum distance decoder may make a decision at each level, choosing one of the two entering paths entering each state. The Viterbi algorithm computes a metric (the metric of a path is defined as the Hamming distance between the sequence represented by that pat hand the received sequence)  for every possible path, and chooses the one with the smallest metric. The paths that are retained are called the survivors. In our example, no more than 2K-1 = 4 survivors will ever be stored, and the maximum-likelihood path is always guarateed to be among them.
If the metrics of two paths are the same, then we choose one of them arbitrarily.

The Viterbi algorithm performs step-by-step as follows:

  1. Initilization:
    Set the metric of the left-most state of the trellis at 0.

  2. Computation step j+1:
    We suppose that at the previous step we have identified all survivor paths and stored each state's survivor path. For each state at level j+1, we compute the metric of the incoming paths as the addition of the metric of the incoming branch and the metric of the survivor path. We then choose the path with the smallest metric for each state.

  3. Final step
    We continue the computation until the algorithm reaches the termination node (the all-zero state), at wich time it makes a decision on the maximum-likelihood path. Then the decoded sequence is the sequence of bits corresponding to this optimum path's branches.
 

contents chapter next

JPL's Wireless Communication Reference Website © 1999

Source: Applet by Olivier Swedor. The development of this page has been carried out as a semester project in the mobile communications laboratory of the Swiss Federal Institute of Technology, EPFL, Lausanne.