DocumentCode :
3006493
Title :
A modular architecture for dynamic programming and maximum likelihood sequence estimation
Author :
Bliss, W. ; Girard, J. ; Avery, J. ; Lightner, M. ; Scharf, L.
Author_Institution :
University of Colorado, Boulder, Co
Volume :
11
fYear :
1986
fDate :
31503
Firstpage :
357
Lastpage :
360
Abstract :
The communication problems of phase tracking [1-3], convolutional decoding [4,5], and dynamic time warping [6], can all be solved with a Dynamic Programming algorithm to find the shortest path through a graph. We present a modular systolic architecture for the specific problem of forming the maximum a posteriori (MAP) estimate of the sequence of visited states of an M-state Markov chain, using noisy observations of a memoryless function of the chain. The architecture is composed of three main sections: (1) a Metric Processor which pre-processes each input datum into M input metrics, (2) a Likelihood Processor which uses the input metrics and the apriori Markov model to update the likelihood measures of the M implicit survivor paths, and (3) a Path Processor which stores the array of back-pointers used to explicitly construct the single most likely survivor path. The likelihood processor is composed of a systolic ring of M simple processing elements which perform the O(M2) computations for each input in O(M) time. If the length N of the sequence is long, the pipe-lined path processor can implement sub-optimal periodic path truncation decoding, which includes the familiar fixed-lag and fixed-interval decoding.
Keywords :
Computer architecture; Dynamic programming; Heuristic algorithms; Markov processes; Maximum a posteriori estimation; Maximum likelihood decoding; Maximum likelihood estimation; Phase estimation; State estimation; State-space methods;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '86.
Type :
conf
DOI :
10.1109/ICASSP.1986.1169069
Filename :
1169069
Link To Document :
بازگشت