MAP decoding of variable length code with substitution, insertion and deletion

We propose a soft decision decoding algorithm for a variable-length encoded Markov source transmitted via a 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 (BSC), and the input of the channel is a first order Markov source. We convert the MAP (maximum a posteriori) problem to one of finding a single-source longest path in a directed acyclic graph, which can be solved by dynamic programming. We also present a generalization of the BSC to include both insertion and deletion errors, and the development of a soft decision MAP decoding algorithm for this more challenging case, which is our main contribution.