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 (KN)-N-2, 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(TK2 + 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 GolombRice code).