Iterative joint source-channel decoding of variable-length codes using residual source redundancy

We present a novel symbol-based soft-input a posteriori probability (APP) decoder for packetized variable-length encoded source indexes transmitted over wireless channels where the residual redundancy after source encoding is exploited for error protection. In combination with a mean-square or maximum APP estimation of the reconstructed source data, the whole decoding process is close to optimal. Furthermore, solutions for the proposed APP decoder with reduced complexity are discussed and compared to the near-optimal solution. When, in addition, channel codes are employed for protecting the variable-length encoded data, an iterative source-channel decoder can be obtained in the same way as for serially concatenated codes, where the proposed APP source decoder then represents one of the two constituent decoders. The simulation results show that this iterative decoding technique leads to substantial error protection for variable-length encoded correlated source signals, especially, when they are transmitted over highly corrupted channels.     

On the joint source-channel decoding of variable-length encodedsources: the BSC case

This paper proposes an optimal maximum a posteriori probability decoder for variable-length encoded sources over binary symmetric channels (BSC) that uses a novel state-space to deal with the problem of variable-length source codes in the decoder. This sequential, finite-delay, joint source-channel decoder delivers substantial improvements over the conventional decoder and also over a system that uses a standard forward error correcting code operating at the same over all bit rates. This decoder is also robust to inaccuracies in the estimation of channel statistics     

On the joint source-channel decoding of variable-length encoded sources: the additive-Markov case

We propose an optimal joint source-channel maximum a posteriori probability decoder for variable-length encoded sources transmitted over a wireless channel, modeled as an additive-Markov channel. The state space introduced by the authors in a previous paper is used to take care of the unique challenges posed by variable-length codes. Simulations demonstrate, that this decoder performs substantially better than the standard Huffman decoder for a simple test source and is robust to inaccuracies in channel statistics estimates. The proposed algorithm also compares favorably to a standard forward error correction-based system.     

Low-complexity iterative joint source-channel decoding for variable-length encoded Markov sources

In this paper, we present a novel packetized bit-level decoding algorithm for variable-length encoded Markov sources, which calculates reliability information for the decoded bits in the form of a posteriori probabilities (APPs). An interesting feature of the proposed approach is that symbol-based source statistics in the form of the transition probabilities of the Markov source are exploited as a priori information on a bit-level trellis. This method is especially well-suited for long input blocks, since in contrast to other symbol-based APP decoding approaches, the number of trellis states does not depend on the packet length. When additionally the variable-length encoded source data is protected by channel codes, an iterative source-channel decoding scheme can be obtained in the same way as for serially concatenated codes. Furthermore, based on an analysis of the iterative decoder via extrinsic information transfer charts, it can be shown that by using reversible variable-length codes with a free distance of two, in combination with rate-1 channel codes and residual source redundancy, a reliable transmission is possible even for highly corrupted channels. This justifies a new source-channel encoding technique where explicit redundancy for error protection is only added in the source encoder.     

Robust decoding of variable-length encoded Markov sources using a three-dimensional trellis

In this letter, we present an improved index-based a-posteriori probability (APP) decoding approach for the error-resilient transmission of packetized variable-length encoded Markov sources. The proposed algorithm is based on a novel two-dimensional (2D) state representation which leads to a three-dimensional trellis with unique state transitions. APP decoding on this trellis is realized by employing a 2D version of the BCJR algorithm where all available source statistics can be fully exploited in the source decoder. For an additional use of channel codes the proposed approach leads to an increased error-correction performance compared to a one-dimensional state representation.     

Joint source-channel decoding of variable-length codes for convolutional codes and turbo codes

Several recent publications have shown that joint source-channel decoding could be a powerful technique to take advantage of residual source redundancy for fixed- and variable-length source codes. This letter gives an in-depth analysis of a low-complexity method recently proposed by Guivarch et al., where the redundancy left by a Huffman encoder is used at a bit level in the channel decoder to improve its performance. Several simulation results are presented, showing for two first-order Markov sources of different sizes that using a priori knowledge of the source statistics yields a significant improvement, either with a Viterbi channel decoder or with a turbo decoder.     

A sequence-based approximate MMSE decoder for source coding overnoisy channels using discrete hidden Markov models

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     

Self-synchronizing Huffman codes (Corresp.)

A problem associated with the use of variable-length source codes is that loss of synchronization may lead to extended errors in the decoded text. In this correspondence it is shown that some binary Huffman codes contain a codeword that resynchronizes the decoder regardless of the synchronization slippage preceding that codeword. Such codes are self-synchronizing in a probabilistic sense, yet require no additional system overhead. Some sufficient conditions are found for the existence or nonexistence of self-synchronizing Huffman codes for many classes of source probabilities. One of our results shows that many common languages can be encoded with self-synchronizing Huffman codes.     

Optimal detection of discrete Markov sources over discretememoryless channels-applications to combined source-channel coding

The authors consider the problem of detecting a discrete Markov source which is transmitted across a discrete memoryless channel. Two maximum a posteriori (MAP) formulations are considered: (i) a sequence MAP detection in which the objective is to determine the most probable transmitted sequence given the observed sequence and (ii) an instantaneous MAP detection which is to determine the most probable transmitted symbol at time n given all the observations prior to and including time n. The solution to the first problem results in a “Viterbi-like” implementation of the MAP detector (with Large delay) while the latter problem results in a recursive implementation (with no delay). For the special case of the binary symmetric Markov source and binary symmetric channel, simulation results are presented and an analysis of these two systems yields explicit critical channel bit error rates above which the MAP detectors become useful. Applications of the MAP detection problem in a combined source-channel coding system are considered. Here, it is assumed that the source is highly correlated and that the source encoder (a vector quantizer (VQ)) fails to remove all of the source redundancy. The remaining redundancy at the output of the source encoder is referred to as the “residual” redundancy. It is shown, through simulation, that the residual redundancy can be used by the MAP detectors to combat channel errors. For small block sizes, the proposed system beats Farvardin and Vaishampayan's channel-optimized VQ by wide margins. Finally, it is shown that the instantaneous MAP detector can be combined with the VQ decoder to form an approximate minimum mean-squared error decoder     

Analysis and design of trellis codes optimized for a binarysymmetric Markov source with MAP detection

We consider the problem of transmitting a binary symmetric Markov source (BSMS), over the additive white Gaussian noise (AWGN) channel. The coding technique considered is trellis-coded modulation (TCM), where we utilize decoders which implement the maximum-likelihood (ML) and maximum a posteriori (MAP) criteria. Employing 8-PSK Ungerboeck codes on a BSMS with state transition probability 0.1, we first show that the MAP decoder realizes a 0.8-2.1-dB coding gain over the ML decoder. Motivated by these gains, we consider the design of trellis codes optimized for the BSMS/AWGN/MAP system. An approximate union bound is established for this system. Using this bound, we found codes which exhibit additional 0.4-1.1-dB gains over Ungerboeck codes. Finally, we compare the proposed TCM system with a tandem coding system. At normalized signal-to-noise ratio (SNR) of 10.8 dB and below, the proposed system significantly outperforms the tandem system     

EXIT functions for binary input memoryless symmetric channels

Use of extrinsic information transfer (EXIT) functions, characterizing the amplification of mutual information between the input and output of the maximum a posteriori (MAP) decoder, significantly facilitates analysis of iterative coding schemes. Previously, EXIT functions derived for binary erasure channels (BECs) were used as an approximation for other channels. Here, we improve on this approach by introducing more accurate methods to construct EXIT functions for binary-input memoryless symmetric (BMS) channels. By defining an alternative pseudo-MAP decoder coinciding with the MAP decoder over BEC, we provide an expression for the EXIT functions of block codes over BEC. Furthermore, we draw a connection between the EXIT function over BEC and the EXIT function over the BMS channel under certain conditions. This is used for deriving accurate or approximate expressions of EXIT functions over BMS channels in certain scenarios.     

Vector quantisation with MAP estimator using reliabilityinformation from turbo-codes

Minimum mean-squared distortion can be achieved by a maximum a posteriori probability (MAP) estimator utilising the reliability information available from the turbo-code channel decoder. Using the optimum MAP estimator in vector quantisation, numerical results show that MAP detection provides a significant improvement over the conventional mapping-based hard-decision source decoder     

Optimal soft decoding for combined trellis-codedquantization/modulation

The maximum a posteriori (MAP) algorithm is used as a minimum mean-squared-error decoder for combined trellis-coded quantization and modulation. The optimal trellis-coded quantizer is derived when the soft-decoding MAP algorithm is used as a decoder. The trellis-coded quantizer and the soft decoder are optimized iteratively for minimum overall distortion from transmitter input to receiver output. Significant performance improvement is achieved for both memoryless Gaussian and uniform source, especially for very noisy channels     

Turbo decoding of quantized data

Much of the work on turbo decoding assumes that the decoder has access to infinitely soft (unquantized) channel data. In practice, however, a quantizer is used at the receiver and the turbo decoder must operate on finite precision, quantized data. Hence, the maximum a posteriori (MAP) component decoder which was designed assuming infinitely soft data is not necessarily optimum when operating on quantized data. We modify the well-known normalized MAP algorithm taking into account the presence of the quantizer. This algorithm is optimum given any quantizer and is no more complex than quantized implementations of the MAP algorithm derived based on unquantized data. Simulation results on an additive white Gaussian noise channel show that, even with four bits of quantization, the new algorithm based on quantized data achieves a performance practically equal to the MAP algorithm operating on infinite precision data     

A variable-length source coding theorem for correlated information sources

A variable-length source coding theorem is proved for a pair of discrete memoryless correlated information sources. The average length of codewords per source letter for source X provided the side information Y is bounded below by the conditional entropy H(X|Y) and above by the same entropy plus J/L where L is the number of source letters encoded and J is the size of ensemble Y. The Huffman encoding procedure is also generalized for this case.     

Markov model aided decoding for image transmission usingsoft-decision-feedback

Soft-decision-feedback MAP decoders are developed for joint source/channel decoding (JSCD) which uses the residual redundancy in two-dimensional sources. The source redundancy is described by a second order Markov model which is made available to the receiver for row-by-row decoding, wherein the output for one row is used to aid the decoding of the next row. Performance can be improved by generalizing so as to increase the vertical depth of the decoder. This is called sheet decoding, and entails generalizing trellis decoding of one-dimensional data to trellis decoding of two-dimensional data (2-D). The proposed soft-decision-feedback sheet decoder is based on the Bahl algorithm, and it is compared to a hard-decision-feedback sheet decoder which is based on the Viterbi algorithm. The method is applied to 3-bit DPCM picture transmission over a binary symmetric channel, and it is found that the soft-decision-feedback decoder with vertical depth V performs approximately as well as the hard-decision-feedback decoder with vertical depth V+1. Because the computational requirement of the decoders depends exponentially on the vertical depth, the soft-decision-feedbark decoder offers significant reduction in complexity. For standard monochrome Lena, at a channel bit error rate of 0.05, the V=1 and V=2 soft-decision-feedback decoder JSCD gains in RSNR are 5.0 and 6.3 dB, respectively.     

Weak variable-length source coding

Given a general source X={Xⁿ}_n=1^∞ , source coding is characterized by a pair (φ_n, ψ_n) of encoder φ_n, and decoder ψ_n , together with the probability of error ε_n≡Pr{ψ_n(φ_n(Xⁿ ))≠Xⁿ}. If the length of the encoder output φ _n(Xⁿ) is fixed, then it is called fixed-length source coding, while if the length of the encoder output φ_n (Xⁿ) is variable, then it is called variable-length source coding. Usually, in the context of fixed-length source coding the probability of error ε_n is required to asymptotically vanish (i.e., lim_n→∞ε_n=0), whereas in the context of variable-length source coding the probability of error ε_n is required to be exactly zero (i.e., ε_n =0∀n=1, 2, ...). In contrast to these, we consider the problem of variable-length source coding with asymptotically vanishing probability of error (i.e., lim_n→∞ε_n =0), and establish several fundamental theorems on this new subject     

Universal Algorithms for Channel Decoding of Uncompressed Sources

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.     

Robust Transmission of Multistage Vector Quantized Sources Over Noisy Communication Channels—Applications to MELP Speech Codec

Joint source-channel coding is an effective approach for the design of bandwidth efficient and error resilient communication systems with manageable complexity. An interesting research direction within this framework is the design of source decoders that exploit the residual redundancy for effective signal reconstruction at the receiver. Such source decoders are expected to replace the traditionally heuristic error concealment units that are elements of most multimedia communication systems. In this paper, we consider the reconstruction of signals encoded with a multistage vector quantizer (MSVQ) and transmitted over a noisy communications channel. The MSVQ maintains a moderate complexity and, due to its successive refinement feature, is a suitable choice for the design of layered (progressive) source codes. An approximate minimum mean squared error source decoder for MSVQ is presented, and its application to the reconstruction of the linear predictive coefficient (LPC) parameters in mixed excitation linear prediction (MELP) speech codec is analyzed. MELP is a low-rate standard speech codec suitable for bandwidth-limited communications and wireless applications. Numerical results demonstrate the effectiveness of the proposed schemes     

Memory-Reduced Maximum A Posteriori Probability Decoding for High-Throughput Parallel Turbo Decoders

Wireless communication standards make use of parallel turbo decoder for higher data rate at the cost of large hardware resources. This paper presents a memory-reduced back-trace technique, which is based on a new method of estimating backward-recursion factors, for the maximum a posteriori probability (MAP) decoding. Mathematical reformulations of branch-metric equations are performed to reduce the memory requirement of branch metrics for each trellis stage. Subsequently, an architecture of MAP decoder and its scheduling based on the proposed back trace as well as branch-metric reformulation are presented in this work. Comparative analysis of bit-error-rate (BER) performances in additive white Gaussian noise channel environment for MAP as well as parallel turbo decoders are carried out. It has shown that a MAP decoder with a code rate of 1/2 and a parallel turbo decoder with a code rate of 1/3 have achieved coding gains of 1.28 dB at a BER of 10\(^{-5}\) and of 0.4 dB at a BER of 10\(^{-4}\), respectively. In order to meet high-data-rate benchmarks of recently deployed wireless communication standards, very large scale integration implementations of parallel turbo decoder with 8–64 MAP decoders have been reported. Thereby, savings of hardware resources by such parallel turbo decoders based on the suggested memory-reduced techniques are accounted in terms of complementary metal oxide semiconductor transistor count. It has shown that the parallel turbo decoder with 32 and 64 MAP decoders has shown hardware savings of 34 and 44 % respectively.