The Viterbi Algorithm
Viterbi Decoder
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
2-11
Fortunately, we do not have to examine all of this trellis at once! For an idea of the basic
processing, we can examine states in pairs. In particular, note that we only need path
metrics of two source states to update a pair of destination states. Note that the source
state pairs are not the same as the destination state pairs.
For our example code, the source state pair 0ABCD and 1ABCD provides the path
metrics needed to update the destination state pair ABCD0 and ABCD1, where ABCD is
fixed for each state pair update. Lets examine a single pair update. This is sometimes
called a Viterbi butterfly. An example butterfly is shown in
Figure 2-7
.
.
Figure 2-7
Example Viterbi Butterfly
To compare the input paths to the state being updated, we must take the path metric for
each state on connecting input branches and add the branch metric associated with that
path. In the example shown in
Figure 2-7
, the lower branch from state 00100 has a
recreated encoder output of 00. As noted before, this can be determined by finding the
encoder output for a state of 00100, along with an input bit of 1 because we are taking the
lower branch. Assuming a decoder input of 11, we find that neither bit of the recreated
encoder output agrees with the decoder input. We assign a branch metric of 0 (no
agreements). We can do similar assignments for the other branches, as shown in
Figure 2-7
.
To update the states, we add the path metrics to the branch metrics. Then we compare
the sums and choose the larger as the surviving branch. The sum of the surviving path
becomes the path metric for the updated state. We must do this update for all state pairs,
for each decoder input. When implementing a Viterbi decoder in software, this update is
the most computation-intensive and creates a do loop that should be optimized to obtain
good performance. In the next section, we will develop DSP56300 assembly code to
implement this algorithm.
00100
10100
01000
01001
5
6
11
00/0
11/2
11/2
00/0
00100
10100
01000
01001
5
6
11
11/2
11/2
7
8
State
Path metric
Encoder out/
branch metric
Decoder
input
F
Freescale Semiconductor, Inc.
n
.