Low-delay optimal MAP state estimation in HMM´s with application to symbol decoding

A new algorithm is developed for realizing optimal maximum a posteriori (MAP) estimates of the hidden states associated with a hidden Markov model, given a sequence of observed symbols. The standard MAP algorithm of Bahl et al., requires direct calculation of the a posteriori probabilities using the forward/backward algorithm, with each state estimate based on the entire observation sequence. For decoding applications, this implies huge, practically infinite delay. The new algorithm finds the optimal MAP estimate without directly computing the a posteriori probabilities and is a variable delay method that typically achieves a small average delay. The method is applied, in comparison with known techniques, to the problem of source decoding over noisy channels.