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 …