
2-12
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
The Viterbi Algorithm
Algorithmic Enhancements
2.4
ALGORITHMIC ENHANCEMENTS
There are a number of modifications that can be made to the algorithm in order to
improve its effectiveness as well as our ability to implement it. In our example, we count
agreements. This produces branch metrics of 0, 1, and 2. In our example butterfly,
however, the branch metrics into the state pair are all 0s and 2s. This is not entirely a
coincidence. For this code, the encoding polynomials both have taps at both extremes.
What this means is that a 1/0 at the end of the encoder will invert/not invert the encoder
output. For our trellis, this means that the pair of branches into a given state will always
have complementary branch metrics (0 and 2, or 1 and 1). By combining this observation
with one more property, we can simplify the Viterbi butterfly computation.
The additional property for this code (shown in
Figure 2-8
) is that a 1/0 at the input bit
will invert/not invert the encoder output. For our trellis, this means that the two states
of a state pair being updated will have the same branch metrics, but with their order
reversed (0 and 2 will become 2 and 0, etc.). These polynomial conditions are not true in
general but do occur quite often. To take advantage of them, we subtract 1 from every
branch metric we produce. This gives branch metric pairs of (-1,1) and (0,0).
As shown in
Figure 2-9
, each pair now has odd symmetry in the two components.
Hence, we need not compute branch metrics for both branches in an update. Instead, we
can find just the uppermost branch metric, and add it as usual for the upper branch.
Next, subtract rather than add it to do the lower branch processing. To process the lower
state update, we subtract the branch metric for the upper path and add to update the
lower path. The total path metrics change, but their relative values do not. Since we are
only looking for the path with the maximum path metric, the results are the same.
F
Freescale Semiconductor, Inc.
n
.