MAP Decoding of Variable Length Code with Substitution, Insertion and Deletion

In this paper we propose a soft 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. 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 soft decision MAP decoding algorithm for this more challenging case, which is our main contribution.