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.     

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.     

基于参数冗余量分配方案和可变参数估计准则的GSM EFR信源信道联合解码算法

该文利用GSM EFR(Enhanced Full Rate)语音编码参数的冗余信息,提出了一种新的基于迭代结构和参数估计的联合解码算法框架;针对GSM EFR编码参数由非等概分布和帧间相关性提供的冗余量,本文提出了联合解码算法中两类冗余信息在信道解码,信源解码的分配方案。同时针对不同语音编码参数的特性,引入不同的估计准则。仿真结果表明,该文算法显著提高了GSM EFR参数接收性能,提高了解码语音信噪比,改善了接收系统性能。     

Fast algorithm for rate-based optimal error protection of embedded codes

Embedded image codes are very sensitive to channel noise because a single bit error can lead to an irreversible loss of synchronization between the encoder and the decoder. P.G. Sherwood and K. Zeger (see IEEE Signal Processing Lett., vol.4, p.191-8, 1997) introduced a powerful system that protects an embedded wavelet image code with a concatenation of a cyclic redundancy check coder for error detection and a rate-compatible punctured convolutional coder for error correction. For such systems, V. Chande and N. Farvardin (see IEEE J. Select. Areas Commun., vol.18, p.850-60, 2000) proposed an unequal error protection strategy that maximizes the expected number of correctly received source bits subject to a target transmission rate. Noting that an optimal strategy protects successive source blocks with the same channel code, we give an algorithm that accelerates the computation of the optimal strategy of Chande and Farvardin by finding an explicit formula for the number of occurrences of the same channel code. Experimental results with two competitive channel coders and a binary symmetric channel showed that the speed-up factor over the approach of Chande and Farvardin ranged from 2.82 to 44.76 for transmission rates between 0.25 and 2 bits per pixel.     

Joint source-channel coding using real BCH codes for robust image transmission.

In this paper, a new still image coding scheme is presented. In contrast with standard tandem coding schemes, where the redundancy is introduced after source coding, it is introduced before source coding using real BCH codes. A joint channel model is first presented. The model corresponds to a memoryless mixture of Gaussian and Bernoulli-Gaussian noise. It may represent the source coder, the channel coder, the physical channel, and their corresponding decoder. Decoding algorithms are derived from this channel model and compared to a state-of-art real BCH decoding scheme. A further comparison with two reference tandem coding schemes and the proposed joint coding scheme for the robust transmission of still images has been presented. When the tandem scheme is not accurately tuned, the joint coding scheme outperforms the tandem scheme in all situations. Compared to a tandem scheme well tuned for a given channel situation, the joint coding scheme shows an increased robustness as the channel conditions worsen. The soft performance degradation observed when the channel worsens gives an additional advantage to the joint source-channel coding scheme for fading channels, since a reconstruction with moderate quality may be still possible, even if the channel is in a deep fade.     

Trellis decoding of Reed-Solomon codes in low bit rate speechcommunications

The residual redundancy that persists in the transmitted parameters of a low bit rate speech coder are exploited to reduce the computational complexity of a Reed-Solomon (RS) trellis decoder. The use of RS codes for mobile telephony provides the opportunity for avoiding channel interleaving and so reduces one-way delay     

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.     

Arithmetic coding algorithm with embedded channel coding

A joint lossless source and channel coding approach that incorporates error detection and correction capabilities in arithmetic coding is exploited. The encoded binary data representation allows the source decoder to recover the source symbols, even with channel errors. The self-synchronisation property of arithmetic coding, the knowledge of the source statistics, and some added redundancy are used for error detection and correction     

Combined Huffman and convolutional codes: concatenated form without feedback

The authors present a new scheme for joint source and channel coding is introduced in which both Huffman coding and convolutional coding are used in a concatenated form. This is a reduction in overall complexity, in comparison with a hard decision decoder followed by a Huffman decoder.<>     

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     

Quantizer design for channel codes with soft-output decoding

A new method of combined source-channel coding for the scalar quantization of a discrete memoryless source is presented, which takes advantage of the reliability information produced by a soft-output channel decoder. Numerical results are presented for a memoryless Gaussian source in conjunction with turbo code showing up to 1-dB improvement in the end-to-end distortion with respect to a traditional channel optimized scalar quantizer. The results include a Gaussian source designed using closed-form expression without the need for a training sequence, as well as image pixels using a training sequence. Furthermore, certain issues related to the effect of the channel mismatch and spectral efficiency of the system are studied. It is shown that the increase in distortion due to a channel mismatch can be substantially reduced by using an adaptive receiver.     

Turbo codes for image transmission-a joint channel and sourcedecoding approach

This paper studies an application of turbo codes to compressed image/video transmission and presents an approach to improving error control performance through joint channel and source decoding (JCSD). The proposed approach to JCSD includes error-free source information feedback, error-detected source information feedback, and the use of channel soft values (CSV) for source signal postprocessing. These feedback schemes are based on a modification of the extrinsic information passed between the constituent maximum a posteriori probability (MAP) decoders in a turbo decoder. The modification is made according to the source information obtained from the source signal processor. The CSVs are considered as reliability information on the hard decisions and are further used for error recovery in the reconstructed signals. Applications of this joint decoding technique to different visual source coding schemes, such as spatial vector quantization, JPEG coding, and MPEG coding, are examined. Experimental results show that up to 0.6 dB of channel SNR reduction can be achieved by the joint decoder without increasing computational cost for various channel coding rates     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

Efficient source decoding over memoryless noisy channels using higher order Markov models

Exploiting the residual redundancy in a source coder output stream during the decoding process has been proven to be a bandwidth-efficient way to combat noisy channel degradations. This redundancy can be employed to either assist the channel decoder for improved performance or design better source decoders. In this work, a family of solutions for the asymptotically optimum minimum mean-squared error (MMSE) reconstruction of a source over memoryless noisy channels is presented when the redundancy in the source encoder output stream is exploited in the form of a /spl gamma/-order Markov model (/spl gamma//spl ges/1) and a delay of /spl delta/,/spl delta/>0, is allowed in the decoding process. It is demonstrated that the proposed solutions provide a wealth of tradeoffs between computational complexity and the memory requirements. A simplified MMSE decoder which is optimized to minimize the computational complexity is also presented. Considering the same problem setup, several other maximum a posteriori probability (MAP) symbol and sequence decoders are presented as well. Numerical results are presented which demonstrate the efficiency of the proposed algorithms.     

Universal variable-to-fixed length source codes

A universal variable-to-fixed length algorithm for binary memoryless sources which converges to the entropy of the source at the optimal rate is known. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's (1984) result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these source codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of coders. All the codes that we consider are prefix-free and complete     

Iterative decoding of serially concatenated arithmetic and channel codes with JPEG 2000 applications.

In this paper, an innovative joint-source channel coding scheme is presented. The proposed approach enables iterative soft decoding of arithmetic codes by means of a soft-in soft- out decoder based on suboptimal search and pruning of a binary tree. An error-resilient arithmetic coder with a forbidden symbol is used in order to improve the performance of the joint source/channel scheme. The performance in the case of transmission across the AWGN channel is evaluated in terms of word error probability and compared to a traditional separated approach. The interleaver gain, the convergence property of the system, and the optimal source/channel rate allocation are investigated. Finally, the practical relevance of the proposed joint decoding approach is demonstrated within the JPEG 2000 coding standard. In particular, an iterative channel and JPEG 2000 decoder is designed and tested in the case of image transmission across the AWGN channel.     

Joint source/channel coding using arithmetic codes

Reserving space fur a symbol that is not in the source alphabet has been shown to provide excellent error detection. In this paper, we show how to exploit this capability using two sequential decoder structures to provide powerful error correction capability. This joint source/channel coder design provides significant packet loss recovery with minimal rate overhead, and compares favorably with conventional schemes     

On causal source codes with side information

We study the effect of the introduction of side information into the causal source coding setting of Neuhoff and Gilbert. We find that the spirit of their result, namely, the sufficiency of time-sharing scalar quantizers (followed by appropriate lossless coding) for attaining optimum performance within the family of causal source codes, extends to many scenarios involving availability of side information (at both encoder and decoder, or only on one side). For example, in the case where side information is available at both encoder and decoder, we find that time-sharing side-information-dependent scalar quantizers (at most two for each side-information symbol) attains optimum performance. This remains true even when the reproduction sequence is allowed noncausal dependence on the side information and even for the case where the source and the side information, rather than consisting of independent and identically distributed (i.i.d.) pairs, form, respectively, the output of a memoryless channel and its stationary ergodic input.     

Joint design of block source codes and modulation signal sets

The problem of designing block source codes and modulation signal sets that are both energy and bandwidth constrained is considered. For the class of linear estimator-based decoders, necessary conditions for optimality for the encoder, decoder and modulation signal set are derived. An algorithm that iteratively solves these necessary conditions to converge to a locally optimum solution has been developed. By studying the performance of the previous class of digital communication systems in the limit of infinite encoding rates, it is demonstrated that the MSE of a bandwidth and energy constrained digital system is bounded from below by that of a block pulse amplitude modulation system. This bound is readily computable in terms of the eigenvalues of the source and channel covariance matrices. The results indicate that for a correlated source, a sufficiently noisy channel and specific source block sizes and bandwidths, the digital system performance coincides with the optimum performance theoretically attainable. Further, significant performance improvements over the standard VQ-based system are demonstrated when the channel is noisy     

Parallel concatenated codes with unequal error protection

We show how parallel concatenated codes (PCCs, also known as “turbo codes”) can be endowed with unequal error protection (UEP). Given the two component encoders of the PCC encoder and the desired interleaver size, UEP is achieved by: (1) suitably positioning the different importance classes of information symbols into the encoder input frame; (2) puncturing the PCC redundancy symbols with a nonuniform pattern; and (3) choosing the interleaver of the PCC encoder in a class of interleavers that guarantees isolation of the importance classes. By controlling the amount of redundancy assigned to each importance class and the class positioning in the input frame, a whole family of UEP PCCs with different UEP levels can be obtained from the same component encoders and interleaver size. From a practical viewpoint, a family of UEP PCCs can be decoded by the same “turbo” iterative decoder, provided that the decoder hardware implementation allows for programmable puncturing and interleaving