Expanding the Viterbi Algorithm
The Inner Loop: Viterbi Butterflies
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
3-5
We now explain the routine line by line. Begin by moving the address of the
precomputed branch metric table to the r2 address register. In our final, combined
routine, this is unnecessary because the desired value already exists in r2, but we include
it as a comment here to make it clear that this value is needed. Branch metric creation
will be discussed in
Section 4.2
.
Next, we update the address register that points to the states used to update. The
memory that stores the path metrics is divided into two parts. In this routine, r5 points to
the old path metrics, used to update the new ones. Address register r4 points to the new
states, those being updated. For each new decoder input, we swap the memory used to
store the updated path metrics with the memory pointing to the old path metrics. To do
this, we initialize address registers r4 and r5 to be modulo registers, with a modulus of
twice the number of states. Address incrementing for the butterfly is so designed that at
the end of the loop, r4 and r5 have automatically swapped pointer values. Thus, no
instructions need be dedicated to swapping the memory.
The path metrics are stored in X memory. Collocated with them in Y memory are the
paths. By paths, we mean a word that contains the bit decisions describing the recreated
encoder input data that would produce that path in the decoder. How we get these will
become clear below as we go through this code. By collocating the path metrics with
their respective paths, we can get both by doing long memory moves. The next two
moves load the first branch metric, and the first (state 00000) path metric/path pair.
Now we are ready for the loop. It is necessary to update every state, and we update
states in pairs. Hence, the number of loop passes is equal to the number of states divided
by 2. In our example, this is the value of NoOfAcsButt (i.e., 16).
Because we have polynomials with taps at both ends of the encoder, we can use one
branch metric, and add and subtract to update our states. We begin by subtracting the
branch, loading the second path metric/path pair at the same time.
Next, we add the branch metric to the path metric we just fetched. Note that for both the
subtract and add of the metric, the path metrics in A1 and B1 are affected, but because
we are not performing a long word add, the paths in A0 and B0 are not.
To compute an updated metric, choose the largest result of the subtract/add operations.
The MAX instruction puts the updated result in B. Note that all of A is transferred if A1
is the survivor path, which means that B0 holds the path bits that represent the survivor
path. This instruction also reloads the first path metric/path pair for use in updating the
lower state later in the loop.
F
Freescale Semiconductor, Inc.
n
.