## JPL's Wireless Communication Reference Website## Chapter: Analog and Digital Transmission, Receiver Design |

*Contributed by Olivier Swedor, EPFL*

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:

lnwherep(r|c)

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

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:

*Initilization:*

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

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

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

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.