© 1997 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Communications
Volume 45 Number 2, February 1997

Table of Contents for this issue

Complete paper in PDF format

High-Performance VLSI Architecture for the Viterbi Algorithm

Montse Boo, Francisco Arguello, Javier D. Bruguera, Ramon Doallo, Associate Member, IEEE, and Emilio L. Zapata

Page 168.

Abstract:

The Viterbi algorithm (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. In this paper, 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 PE's 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.

References

  1. A. Viterbi, "Error bounds for convolutional coding and an asymptotically optimum decoding algorithm," IEEE Trans. Inform. Theory, vol. IT-13, pp 260-269, Apr. 1967.
  2. G. D. Forney, "The Viterbi Algorithm," Proc. IEEE, vol. 61, no 3, pp. 268-278, Mar. 1973.
  3. G. Ungerboeck, "Channel coding with multilevel/phase signals," IEEE Trans. Inform. Theory, vol. 28, pp. 55-67, Jan 1982.
  4. M. W. Marcellin and T. R. Fischer, "Trellis coded quantization of memoryless and Gauss-Markov sources," IEEE Trans. Commun., vol. 28, pp. 92-93, Jan 1990.
  5. S. C. Glinski, T. M. Lalumia, D. R. Cassiday, T. Koh, C. M. Gerveshi, A. Wilson, and J. Kumar, "A processor for graph search algorithms," in Proc. ISSCC'87, New York, 1987, pp. 162-163.
  6. C. Y Chang and K. Yao, "Systolic array processing of the Viterbi algorithm," IEEE Trans. Inform. Theory, vol. 35, no 1, pp. 76-86, Jan. 1989.
  7. --, "Viterbi decoding by a systolic array," in Proc. 23rd Annu. Alleron Conf. Commun., Contr., Computing, Monticello, IL, 1985, pp. 430-439.
  8. P. G. Gulak and T. Kailath, "Locally connected VLSI architectures for the Viterbi algorithm," IEEE J. Select. Areas Commun., vol. 6, pp. 527-538, Apr. 1988.
  9. G. Feygin, G. Gulak, and P. Chow, "A multiprocessor architecture for Viterbi decoders with linear speed up," IEEE Trans. Signal Processing, vol. 41, no 9, pp. 2907-2917, Sept. 1993.
  10. C. B. Shung, H-D. Ling, R. Cypher, P. H. Siegel, and H. K. Thapar, "Area-efficient architectures for the Viterbi algorithm--Part I: Theory," IEEE Trans. Commun., vol. 41, pp. 636-644, Apr. 1993.
  11. --, "Area-efficient architectures for the viterbi algorithm--Part II: Applications," IEEE Trans. Commun., vol. 41, no 5, pp. 802-807, May. 1993.
  12. S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications.Englewood Cliffs, NJ: Prentice-Hall, 1983.
  13. F. Arguello, J. D. Bruguera, R. Doallo, and E. L. Zapata, "Parallel architecture for fast transforms with trigonometric kernel," IEEE Trans. Parallel Distrib. Syst., vol. 5, pp. 1091-1099, 1994.
  14. E. L. Zapata and F. Arguello, "Application-specific architecture for fast transforms based on the succesive doubling method," IEEE Trans. Signal Processing, vol. 41, pp. 1476-1481, 1993.
  15. J. Lopez and E. L. Zapata, "Unified architecture for divide and conquer based tridiagonal system solvers," IEEE Trans. Comput., vol. 43, pp. 1413-1425, 1994.
  16. G. Fettweis and H. Meyr, "High-speed parallel Viterbi decoding: algorithm and VLSI-architecture," IEEE Commun. Mag., pp. 46-55, May 1991.
  17. P. J. Black and T. H.-Y. Meng, "Hybrid survivor path architectures for Viterbi decoders," in Proc. ICASSP 93, 1993, pp. 1433.
  18. E. Paaske, S. Pedersen, and J. Spars\phi, "An area-efficient path memory structure for VLSI implementation of high speed Viterbi decoders, Integration," IEEE Trans. VLSI Syst., vol. 1, pp. 79-91, 1991.