Fast Joint Source-Channel Decoding of Convolutional Coded Markov Sequences with Monge Property

We address the problem of joint source-channel maximum a posteriori (MAP) decoding of a Markov sequence which is first encoded by a source code, then encoded by a convolutional code, and sent through a noisy memoryless channel. The existing joint source-channel decoding algorithm for the case of general convolutional encoder has $O(MK^{2} N)$ time complexity, where $M$ is the length in bits of the information sequence, $K$ is the size of the Markov source alphabet and $N$ is the number of states of the convolutional encoder. We show that for Markov sources satisfying the so-called Monge property the decoding complexity can be decreased to $O(MKN)$ by applying a fast matrix search technique.