DSP56300 datasheet(25/108 Pages) FREESCALE

25 / 108 page

The Viterbi Algorithm

Viterbi Decoder

Viterbi Decoder Implementation

2-11

Fortunately, we do not have to examine all of this trellis at once! For an idea of the basic

processing, we can examine states in pairs. In particular, note that we only need path

metrics of two source states to update a pair of destination states. Note that the source

state pairs are not the same as the destination state pairs.

For our example code, the source state pair 0ABCD and 1ABCD provides the path

metrics needed to update the destination state pair ABCD0 and ABCD1, where ABCD is

fixed for each state pair update. LetÕs examine a single pair update. This is sometimes

called a Viterbi butterfly. An example butterfly is shown in Figure 2-7.

Figure 2-7

Example Viterbi Butterfly

To compare the input paths to the state being updated, we must take the path metric for

each state on connecting input branches and add the branch metric associated with that

path. In the example shown in Figure 2-7, the lower branch from state 00100 has a

recreated encoder output of 00. As noted before, this can be determined by finding the

encoder output for a state of 00100, along with an input bit of 1 because we are taking the

lower branch. Assuming a decoder input of 11, we find that neither bit of the recreated

encoder output agrees with the decoder input. We assign a branch metric of 0 (no

agreements). We can do similar assignments for the other branches, as shown in

Figure 2-7

To update the states, we add the path metrics to the branch metrics. Then we compare

the sums and choose the larger as the surviving branch. The sum of the surviving path

becomes the path metric for the updated state. We must do this update for all state pairs,

for each decoder input. When implementing a Viterbi decoder in software, this update is

the most computation-intensive and creates a do loop that should be optimized to obtain

good performance. In the next section, we will develop DSP56300 assembly code to

implement this algorithm.

00100

10100

01000

01001

00/0

11/2

00/0

00100

10100

01000

01001

11/2

State

Path metric

Encoder out/

branch metric

Decoder

input

Freescale Semiconductor, Inc.

For More Information On This Product,

Go to: www.freescale.com

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

DSP56300 Datasheet(HTML) 25 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