Algorithms and architectures for dynamic programming on Markov chains

1 June 1989

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Acoustics, Speech, and Signal Processing

Vol. 37 (6) , 900-912
https://doi.org/10.1109/assp.1989.28061

Abstract

Algorithms and architectures are developed for dynamic programming on finite-state Markov chains. The results are applied to phase tracking of a phase-jitter carrier, Viterbi decoding of convolutional codes, and isolated-word recognition using hidden Markov models and dynamic time warping. It is argued that a computing ring, which is really a cyclic systolic array of cells, provides a good tradeoff between performance and complexity for implementation in VLSI. The computing ring may be pipelined with a preprocessor and a memory management unit to achieve a modular design.

Keywords

This publication has 16 references indexed in Scilit:

A modular architecture for dynamic programming and maximum likelihood sequence estimation
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2005
VLSI Array processors
IEEE ASSP Magazine, 1985
On the Application of Vector Quantization and Hidden Markov Models to Speaker-Independent, Isolated Word Recognition
Bell System Technical Journal, 1983
Aspects of dynamic programming in signal and image processing
IEEE Transactions on Automatic Control, 1981
Optimizing synchronous systems
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981
A dynamic programming algorithm for simultaneous phase estimation and data decoding on random-phase channels
IEEE Transactions on Information Theory, 1981
Performance tradeoffs in dynamic time warping algorithms for isolated word recognition
IEEE Transactions on Acoustics, Speech, and Signal Processing, 1980
Modulo-2piphase sequence estimation (Corresp.)
IEEE Transactions on Information Theory, 1980
Minimum prediction residual principle applied to speech recognition
IEEE Transactions on Acoustics, Speech, and Signal Processing, 1975
Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference
IEEE Transactions on Information Theory, 1972