Joint source-channel decoding based on residual source redundancy is an effective paradigm for error-resilient data compression. While previous work only considered fixed-rate systems, the extension of these techniques for variable-length encoded data was independently proposed by the authors and by Demir and Sayood (see Proc. Data Comp. Conf., Snowbird, UT, p.139-48, 1998). We describe and compare the performance of a computationally complex exact maximum a posteriori (MAP) decoder, its efficient approximation, an alternative approximate decoder, and an improved version of this decoder are suggested. Moreover, we evaluate several source and channel coding configurations. The results show that our approximate MAP technique outperforms other approximate methods and provides substantial error protection to variable-length encoded data.

Summary form only given. We develop improved joint source-channel (JSC) methods for decoding variable length encoded data based on residual source redundancy. Until very recently, all JSC methods based on residual redundancy assumed fixed length codewords. Recently, a practically realizable system which performed best over a significant range of channel conditions consisting of inner binary convolutional (BC) (bit-level) decoding, followed by outer (symbol-level) approximate maximum a posteriori (MAP) JSC decoding was suggested. Here we suggest two ways of improving on this method. First, a straightforward improvement is realized by using soft/probabilistic bit decisions output by the BC decoder, rather than hard decisions. Second, the JSC decoder can itself generate soft/probabilistic output, at the symbol level. The exact VLC minimum mean-squared error (MMSE) decoder has large complexity, similar to the exact MAP method, because the number of states increases with time. Thus we suggest an approximate MMSE method. In this approximate scheme, we first form a reduced directed graph, using the same MAP state reduction procedure as used for approximate MAP JSC decoding. Next, we rearrange the remaining states to form an (equivalent) directed graph. We then apply the forward/backward algorithm and a state merging procedure to this reduced graph to get approximate a posteriori probabilities, used for MMSE estimation.

Joint source-channel decoding based on residual source redundancy is an effective paradigm for error-resilient data compression. While previous work only considered fixed rate systems, the extension of these techniques for variable-length encoded data was previously independently proposed by the authors, Park and Miller (see Proc. of Conf. on Info. Sciences and Systems, Princeton, N.J., 1998) and by Demir and Sayood (see Proc. of the Data Compression Conf., Snowbird, U.T., p.139-48, 1998). In this paper, we describe and compare the performance of a computationally complex exact maximum a posteriori (MAP) decoder, its efficient approximation, an alternative approximate MAP decoder, and an improved version of this decoder suggested here. Moreover, we evaluate several source and channel coding configurations. Our results show that the approximate MAP technique from Park et al. outperforms other approximate methods and provides substantial error protection to variable-length encoded data.

Joint source-channel (JSC) decoding based on residual source redundancy is a technique for providing channel robustness to quantized data. Previous work assumed a model equivalent to viewing the encoder/noisy channel tandem as a discrete hidden Markov model (HMM) with transmitted indices the hidden states. We generalize this HMM-based (1-D) approach for images, using the more powerful hidden Markov mesh random field (HMMRF) model. While previous state estimation methods for HMMRFs base estimates on only a causal subset of the observed data, our new method uses both causal and anticausal subsets. For JSC-based image decoding, the new method provides significant benefits over several competing techniques.

In previous work on source coding over noisy channels it was recognized that when the source has memory, there is typically "residual redundancy" between the discrete symbols produced by the encoder, which can be capitalized upon by the decoder to improve the overall quantizer performance. Sayood and Borkenhagen (1991) and Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, p.186-93, 1994) proposed "detectors" at the decoder which optimize suitable criteria in order to estimate the sequence of transmitted symbols. Phamdo and Farvardin also proposed an instantaneous approximate minimum mean-squared error (IAMMSE) decoder. These methods provide a performance advantage over conventional systems, but the maximum a posteriori (MAP) structure is suboptimal, while the IAMMSE decoder makes limited use of the redundancy. Alternatively, combining aspects of both approaches, we propose a sequence-based approximate MMSE (SAMMSE) decoder. For a Markovian sequence of encoder-produced symbols and a discrete memoryless channel, we approximate the expected distortion at the decoder under the constraint of fixed decoder complexity. For this simplified cost, the optimal decoder computes expected values based on a discrete hidden Markov model, using the wellknown forward/backward (F/B) algorithm. Performance gains for this scheme are demonstrated over previous techniques in quantizing Gauss-Markov sources over a range of noisy channel conditions. Moreover, a constrained delay version is also suggested.

Recently, we developed a sequence-based minimum mean-squared error (MMSE) estimator for decoding quantized data transmitted over noisy channels. The method effectively views the encoder and noisy channel tandem as a discrete hidden Markov model (HMM), with transmitted indices the unknown states and received indices the observable symbols. Here, we extend this 1D approach to images, using a Markov mesh random field to model the encoded image. Our decoder is based on an approximate forward/backward algorithm for calculating pixel "label probabilities" in Markov meshes which may also have application to image labeling and segmentation. For a DPCM-based image coding system and a high error-rate channel, the new decoder obtains significant performance gains, both objective and visually discernable, over the standard decoder, as well as over several other competing techniques.

A new algorithm is developed for realizing optimal maximum a posteriori (MAP) estimates of the hidden states associated with a hidden Markov model, given a sequence of observed symbols. The standard MAP algorithm of Bahl et al., requires direct calculation of the a posteriori probabilities using the forward/backward algorithm, with each state estimate based on the entire observation sequence. For decoding applications, this implies huge, practically infinite delay. The new algorithm finds the optimal MAP estimate without directly computing the a posteriori probabilities and is a variable delay method that typically achieves a small average delay. The method is applied, in comparison with known techniques, to the problem of source decoding over noisy channels.