
Viterbi Decoder Implementation
For More Information On This Product,
Go to: www.freescale.com
iii
TABLE OF CONTENTS
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1
1.1
Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-3
1.2
Viterbi Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-3
1.3
Manual Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-4
The Viterbi Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-1
2.1
IS-136. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-3
2.2
Convolutional Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-3
2.3
Viterbi Decoder. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-4
2.4
Algorithmic Enhancements. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-12
Expanding the Viterbi Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1
3.1
Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.2
Partitioning the Task. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.3
The Inner Loop: Viterbi Butterflies . . . . . . . . . . . . . . . . . . . . . . . 3-3
3.4
Creating the Branch Metrics. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-6
3.5
Storing the Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-11
3.6
Traceback: Obtaining the Decoder Output. . . . . . . . . . . . . . . . 3-13
3.7
Main: Gluing the Pieces Together . . . . . . . . . . . . . . . . . . . . . . 3-17
3.8
Memory Organization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-19
Algorithmic Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1
4.1
Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-3
4.2
Allowing More General Branch Metrics . . . . . . . . . . . . . . . . . . . 4-3
4.2.1
Modify Viterbi Butterfly. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-4
4.2.2
Modify Branch Metric Generation . . . . . . . . . . . . . . . . . . . . . 4-6
4.3
Starting from 0: The Pre ACS Macro . . . . . . . . . . . . . . . . . . . . . 4-8
4.4
Collapsing the States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-10
4.5
Main: Putting the Pieces Back Together . . . . . . . . . . . . . . . . . 4-12
Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-1
5.1
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-3
F
Freescale Semiconductor, Inc.
n
.