Fast Length-Constrained MAP Decoding of Variable Length Coded Markov Sequences over Noisy Channels

We consider the problem of maximum a posterior probability (MAP) decoding of a Markov sequence that is variable length coded and transmitted over a binary symmetric channel (BSC). The number of source symbols in the sequence, if made known to the decoder, can improve MAP decoding performance. But adding a sequence length constraint to MAP decoding problem increases its complexity. In this paper we convert the length-constrained MAP decoding problem into one of maximum-weight k-link path in a weighted directed acyclic graph. The corresponding graph optimization problem can be solved by a fast parameterized search algorithm that finds either the exact solution with high probability or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than the previous heuristic algorithms.