Expanding the Viterbi Algorithm
Creating the Branch Metrics
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
3-7
Thus, by using a shifted version of the branch metrics, we only need one branch metric
for each state pair update. This metric is the one that gets subtracted from one path and
added into the other. We need only generate and store 16 branches.
Any given branch will, for a specified input, have one of four values. The four values
will represent how well the decoder input compares to the recreated encoder outputs of
00, 01, 10, 11. For our example, we assume some soft decision input. The decoder input
data is shifted and scaled so that 1 is changed to 16, and 0 is changed to -16. We obtain
two partial branch metrics B
0
and B
1
, where B
0
is the partial branch metric for the
encoder polynomial 1+D+D
3
+D
5
output, and B
1
is the partial branch metric for the
1+D
2
+D
3
+D
4
+D
5
polynomial output. We can then compute the four branches as B
0
+B
1
,
B
0
-B
1
, -B
0
+B
1
, and -B
0
-B
1
, corresponding to recreated encoder values of
11, 10, 01, and 00.
The butterfly loop needs the branches in a specific order dictated by the encoding
polynomials. As seen in
Figure 2-2
, we update states 2i and 2i+1 using states i and i+16.
We only need the 16 branches for the 16 state pairs. The state gives us five of the six
values needed to determine the encoder output. The remaining value can be found by
examining the butterfly loop assembly code. In the loop, note that we subtract the
branch metric first (from the upper branch), then add it to the lower branch. The
butterfly loop is written assuming that the single branch metric value has the correct
sign to be added in the lower branch. This is equivalent to assuming the encoder input
bit is a 1 (for the purposes of computing the branch metric table). We account for this in
the code by choosing positive 16 for 1s and minus 16 for 0s (as noted in the preceding
paragraph). The resulting recreated encoder outputs for the first 16 states are shown in
the following table.
F
Freescale Semiconductor, Inc.
n
.