DSP56300 datasheet(39/108 Pages) FREESCALE

39 / 108 page

Expanding the Viterbi Algorithm

Storing the Paths

Viterbi Decoder Implementation

3-11

3.5

STORING THE PATHS

For some applications of the Viterbi algorithm, the paths will not need to be stored. This

occurs when the memory of the encoder (or channel, for maximum likelihood sequence

estimation) is small enough for the paths in the algorithm to merge quickly. In other

situations, this may not be adequate. To clarify the storage process, we introduce the

idea of traceback.

Assume the decoder has been processing data for some time. If we examine the paths

up to the time of the current input, it is not clear what path should be chosen. In fact,

choosing a path to decide what decoder output should correspond to the current input

would lead to poor performance. This is because we do not have all the data we can get.

Because the current encoder input has an effect on the decoder inputs for some time

into the future, future decoder inputs can be used to increase the reliability of current

decoder output decision values. As a result, we introduce delay into the decoder,

waiting for future inputs to be processed before making a decision.

For the Viterbi algorithm, this means that while the current array of paths may not have

reliable decisions about the present, they do contain reliable data about the past. In

practice, there is a traceback depth for the decoder, the number of states we need to look

back before the decision data is assumed to be reliable. For this depth, it is highly likely

that the paths have converged. This means that all current paths have the same data up

to this time in the past. If this depth is less than the register size used for the paths (i.e.,

16 bits for the DSP56600 and the DSP56300 in 16-bit arithmetic mode, 24 bits for

DSP56300 otherwise), we can choose a path and output the most significant bits of the

If this is not the case, we must make some provision to store the paths. For our example,

a traceback depth of 16 bits is inadequate. A depth of 24 bits is extremely marginal for

this example, while 35 bits is probably more than needed. Hence, we implement

traceback storage. For this example, we actually store paths for the entire sequence

length (assumed to be 168 bits here), and produce the entire output at the end. It should

be easy to modify the code to produce partial output data in stages if desired.

The critical concept in storing paths is to arrange the path data so that we can connect the

paths for consecutive storage times. The path bits of the survivor path bits at the end

must be joined with their preceding path bits. Because we stored the preceding path bits

in memory, we must know where in memory to look for the survivor path. Where in

memory do we look?

To see how this is done, consider an example path in register B0 just after a Viterbi

butterfly update. Assume there are 13 pairs of decoder inputs processed so far.

Freescale Semiconductor, Inc.

For More Information On This Product,

Go to: www.freescale.com

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

DSP56300 Datasheet(HTML) 39 Page - Freescale Semiconductor, Inc

Html Pages

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...More

Datasheet Download

Link URL