DSP56300 datasheet(23/108 Pages) FREESCALE

23 / 108 page

The Viterbi Algorithm

Viterbi Decoder

Viterbi Decoder Implementation

2-9

To understand why this is so, note that the total path metric for

is PM1+QM1.

Similarly,

has path metric PM1+QM2,

has path metric PM2+QM1, and

has path metric PM2+QM2. Suppose

is a candidate for largest path

metric. Then

is still larger, as PM1+QM2 >PM2+QM2 (remembering we

assumed that PM1 >PM2). This is true for any Q2. So, if PM1 > PM2, we can eliminate P2

from further consideration at time j, without waiting for the ÒfutureÓ inputs from time j to

time k.

Figure 2-5

Using Intermediate States to Eliminate Partial Paths

In our example, each state will have two paths entering it at any time. The number of

paths doubles each time, but we can now eliminate half of the paths each time as well.

This is the basis of the Viterbi algorithm. To use it, we must keep track of the best path

metric for each state up to the current time. By eliminating paths that can never have the

largest path metric, however, we keep the amount of computation constant with time.

To diagram what is going on, we need a different figure than the tree in Figure 2-3. We

need only keep track of each (encoder) state at each time. The result is called a trellis

because it resembles one. A diagram of a trellis for our IS-136 code appears in Figure 2-6.

The beginning of the trellis does not look the same for each time (each decoder input is a

stage in the diagram). This is because we assumed the encoder started in state 00000. In

general, the encoder can be in any state, and the trellis repeats. For our figure, this can be

seen in stages 6 and 7 (after 5 stages, our encoder can be in any state, so we get a Òsteady

stateÓ in our trellis diagram). Each line in the trellis is a transition, just like the ones in the

tree. For the trellis, however, the number of states is bounded. The number of states for

this trellis is determined by the encoder which has five state bits. This means there are

25 = 32 states in the trellis.

State S

time i

time j

time k

Freescale Semiconductor, Inc.

For More Information On This Product,

Go to: www.freescale.com

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