Algorithmic Extensions
Introduction
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
4-3
4.1
INTRODUCTION
This section shows how to adjust the code of
Section 3
to include several enhancements.
Generalized branch metrics are allowed, as well as optimizing the code to reduce the
computations when data occurs in blocks.
The code in this section introduces several modifications to the code discussed in
Section 3
.
Section 4.2
modifies the handling of branch metrics to allow nonsymmetrical
branch metrics.
Section 4.3
and
Section 4.4
develop two additional macros useful if the
data is blocked and the encoder is periodically forced through a known state. We put all
of these routines together to produce a modified Viterbi algorithm decoder that has
autonormalized path metrics and efficient coding for blocked data. Note that a complete
listing of this code appears in
Appendix B
.
4.2
ALLOWING MORE GENERAL BRANCH METRICS
The code introduced so far is efficient for algorithms that have special branch metrics. In
particular, the branch metrics are assumed to be inverses of each other and flipped
between state pairs. Although this is true for many popular codes in use today, it is not
necessarily the case. If a polynomial set is specified where one of the encoding
polynomials does not have a tap at one end, the branch metrics lose some of their
symmetry. A simple example is the polynomial set (1,1+D), whose trellis appears in
Figure 4-1
.
Figure 4-1
Polynomial (1,1+D) Trellis
Note that the input branches to State 0 are not complements of each other! We might
accommodate this with a fractional branch offset to make branch 00 and branch 01
negatives, but note that the offset for the lower state would have to be different. Another
approach is to compute separate branch offsets for the upper and lower state updates.
This requires a different version of the branch metric generation as well as the butterfly
loop. We consider modified code for each of these functions in the examples that follow.
00
+
0
1
11
01
10
S
0
S
0
F
Freescale Semiconductor, Inc.
n
.