DSP56300 datasheet(26/108 Pages) FREESCALE

26 / 108 page

2-12

Viterbi Decoder Implementation

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 0Õs and 2Õs. 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.

Freescale Semiconductor, Inc.

For More Information On This Product,

Go to: www.freescale.com

DSP56300 Datasheet(PDF) 26 Page - Freescale Semiconductor, Inc