
3-12
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
Expanding the Viterbi Algorithm
Storing the Paths
Figure 3-1
Stored B0 Path
Note that the current encoder state is part of the path! In retrospect, this must be so, as
both the state (the recreated encoder state) and its path (the potential decoder output
the recreated encoder input) represent the same data stream. To use this, store the path
byte in a memory location with address defined by the time the path bytes are stored,
offset by the current encoder state. Then, make sure the saved partial path does not
contain the current encoder state. Instead, save the current encoder state part of the path
to be stored the next time we save paths.
To do the traceback, start with the survivor path at the end, and trace the path bits back
in time to recover the decoder output. When we recover the stored path as part of our
traceback, the final bits in that path point to the offset memory location where we need
to read to continue the traceback.
Hence, if we omit the most recent 5 bits of the path, we can potentially store up to 11 bits
of path (assuming 16-bit registers). We have chosen to store 8 in this example because
reconstruction is a little easier if we have data in bytes. There is a trade-off. Storing more
path bits at a time means we dont need to store paths as often (fewer instructions
executed, less memory used), but the traceback reconstruction is more difficult because
we have to piece together 11-bit data into 16-bit words.
The code in our example code makes one more assumption. We assume that the data is
sent in a block, and that the transmitter ends the block by 0 filling the encoder. The effect
of 0 filling the encoder is to end everything at state 0. Hence, for traceback, start
everything at state 0.
Bit #
15
0 0 0 1 0 0 1 1
8
7
0
1 0 1 0 1 1 1 0
B0
Encoder state
Stored path byte
F
Freescale Semiconductor, Inc.
n
.