DSP56300 datasheet(21/108 Pages) FREESCALE

21 / 108 page

The Viterbi Algorithm

Viterbi Decoder

Viterbi Decoder Implementation

2-7

Comparing the recreated encoder output with the decoder input, we determine the

number of agreements, shown in Figure 2-3 as the branch metric. We find a branch

metric for each transition. For each state, we track the cumulative branch metrics to form

the path metrics. These are shown as a number appearing above each state box.

To recreate the correct input sequence, we choose the recreated encoder path that best

agrees with the decoder input data. In this case, the best path is the one with the largest

final path metric. For clarity, the path metrics for the best path are distinguished with a

larger font size and bolder arrows. To recreate the input sequence (so far), we can use

two methods. The easiest is to use the state as the decoder output. Unfortunately, this

method will not work after we finish the development of the decoder. The second

method will work when we are done. To obtain the decoder output, trace the best path

(the one with the largest final path metric) back to the beginning. Now, follow the same

path forward again to obtain the input sequence by placing a 0 at the decoder output

each time we choose an upper transition, and a 1 output each time we choose the lower

transition. Using this method on the tree in Figure 2-3 gives us 10110, which agrees with

the encoder input example.

The most troublesome aspect of this decoder is that the number of states we have to

track for each decoder input is actually the number of possible paths. For this coding

example, the number of states doubles for each input. For any reasonable number of

inputs, the amount of work and storage needed for this decoder is far too large to be

practical. To solve this problem, begin by noting that we donÕt really need all the data

generated by the decoder. In particular, all the work goes toward finding the path that

best agrees with the input. We only need the path that gives us the largest path metric. If

we determine that a path cannot ever have the largest path metric, we can ignore that

path for all future calculations.

To collapse the ever-growing tree in Figure 2-3, consider what happens if we continue

the tree for one more pair of decoder inputs. The total number of states would be 64 for

the next input pair. To keep the diagram manageable, only a pair of specially chosen

states appears in Figure 2-4. When we extend the tree to the next state, we get states with

six bits. Note, however, that the encoder we are attempting to trace only needs five bits

to determine its output bits. To emphasize this, the sixth (leading) bit is separated in the

state boxes. Because the extra (leading) bits do not affect the recreated encoder outputs,

we can ignore them. As a result, the 64 states collapse into 32 states again. The only

resulting complication is that each state now has two rather than one entering paths.

Figure 2-4

shows this state collapse as well as each stateÕs multiple input paths in two

example states. To correctly process the decoder input, we must next determine which of

the input paths to keep for each state.

Freescale Semiconductor, Inc.

For More Information On This Product,

Go to: www.freescale.com

DSP56300 Arkusz danych(PDF) 21 Page - Freescale Semiconductor, Inc

DSP56300 Arkusz danych(HTML) 21 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

Arkusz danych Pobierz

Link URL