High-performance VLSI architecture for the Viterbi algorithm

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on communications 1997-02, Vol.45 (2), p.168-176
Main Authors: Boo, M., Arguello, F., Bruguera, J.D., Doallo, R., Zapata, E.L.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Associate members
Computer architecture
Convolutional codes
Hardware
Maximum likelihood decoding
Partitioning algorithms
Shift registers
Very large scale integration
Viterbi algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages.
ISSN:0090-6778
1558-0857
DOI:10.1109/26.554365