Delayed decision decoding of variable length coded Markov source over noisy channel with insertion and deletion

In this paper we propose a delayed decision decoding algorithm for variable-length encoded Markov source transmitted via noisy channel that has all three types of errors: substitution, deletion, and insertion. The decoder aims to find a sequence X that maximizes the posterior probability given a received sequence Y. First, we assume the channel is a binary symmetric channel, and input of the channel is a first order Markov source. In this case we convert the MAP (maximum a posteriori) problem to one of finding a single-source longest path in a directed acyclic graphic, which can be solved by dynamic programming. We also analyze the complexity of MAP decoding of high order Markov sources. The second half of this paper is devoted to a generalization of the BSC channel to include both insertion and deletion errors, and to the development of a delayed decision MAP decoding algorithm for this more challenging case, which is our main contribution.