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