On the Complexity of Joint Source-Channel Decoding of Markov Sequences Over Memoryless Channels

We investigate the complexity 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. As established previously the MAP decoding can be performed by a Viterbi-like algorithm on a trellis whose states are triples of the states of the Markov source, source coder and convolutional coder. The large size of the product space (in the order of $K^{2}N$, where $K$ is the number of source symbols and $N$ is the number of states of the convolutional coder) appears to prohibit such a scheme. We show that in the case of finite impulse response convolutional codes the state space size can be reduced to $O(K^{2}+N\log N)$, hence the decoding time becomes $O(TK^{2}+TN\log N)$, where $T$ is the length in bits of the decoded bitstream. We further show that an additional complexity reduction can be achieved when $K > N$, if the source satisfies a certain property, which is the case for a scalar quantized Gaussian-Markov source. This decrease becomes more significant as the tree structure of the source code is more unbalanced. The reduction factor ranges between $O(K/N)$ (for a fixed-length source code) and $O(K/\log N)$ (for Golomb-Rice code).