Optimal use of Markov models for DPCM picture transmission over noisy channels

Joint source/channel decoders that use the residual redundancy in the source are investigated for differential pulse code modulation (DPCM) picture transmission over a binary symmetric channel. Markov sequence decoders employing the Viterbi algorithm that use first-order source statistics are reviewed, and generalized for decoders that use second-order source statistics. To make optimal use of the source correlation in both horizontal and vertical directions, it is necessary to generalize the conventional Viterbi decoding algorithm for a one higher-dimensional trellis. The paths through the trellis become two-dimensional "sheets", thus, the technique is coined "sheet decoding". By objective [reconstruction signal-to-noise ratio (SNR)] and subjective measure, it is found that the sheet decoders outperform the Markov sequence decoders that use a first-order Markov model, and outperform two other known decoders (modified maximum a posteriori probability and maximal SNR) that use a second-order Markov model. Moreover, it is found that the use of a simple rate-2/3 block code in conjunction with Markov model-aided decoding (MMAD) offers significant performance improvement for a 2-bit DPCM system. For the example Lenna image, it is observed that the rate-2/3 block code is superior to a rate-2/3 convolutional code for channel-error rates higher than 0.035. The block code is easily incorporated into any of the MMAD DPCM systems and results in a 2-bit MMAD DPCM system that significantly outperforms the noncoded 3-bit MMAD DPCM systems for channel-error rates higher than 0.04.     

Nonadaptive DPCM Transmission of Monochrome Pictures Over Noisy Communication Channels

The present study is a sequel to the authors' 1972 paper [1] where the output signal-to-noise ratio SNRois obtained for nonadaptive differential pulse-code modulation (DPCM) systems with an arbitrary linear predictor operating on noisy digital channels. Important stability constraints for an arbitrary linear predictor are obtained. A complete analytical study of previous line-line-and-sample feedback systems is presented. The SNRoimprovement over previoussample feedback is found to increase from approximately 2.6 dB for error-free channels to 4.1 dB for noisy channels. Optimization of the predictor for noisy channel usage is shown to greatly reduce the sensitivity of SNRoto variations in message and channel parameters, while use of the resulting predictor on error-free channels yields SNRovalues which are almost as good as those obtained when the predictor is optimized for error-free channels. Reduction of the effects of digital channel errors on SNRousing various methods, including periodic or pseudorandom resetting are considered briefly. Hardcopy results from computer-simulated DPCM monochrome image transmission systems corroborate our analytical results.     

Hybrid Coding of Pictorial Data

Two hybrid coding systems utilizing a cascade of a unitary transformation and differential pulse code modulators (DPCM) systems are proposed. Both systems encode the transformed data by a bank of DPCM systems. The first system uses a one-dimensional transform of the data where the second one employs two-dimensional transformations. Theoretical results for Markov data and experimental results for a typical picture are presented for Hadamard, Fourier, cosine, slant, and the KarhunenLoeve transformations. The visual effects of channel error and also the impact of noisy channel on the performance of the hybrid system, measured in terms of the signal-to-noise ratio of the encoder, is examined and the performance of this system is compared to the performances of the two-dimensional DPCM and the standard two-dimensional transform encoders.     

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.     

Iterative joint source–channel decoding of H.264 compressed video

This paper proposes an Iterative Joint Source–Channel Decoding (IJSCD) scheme for error resilient transmission of H.264 compressed video over noisy channels by using the available H.264 compression, e.g., Context-based Adaptive Binary Arithmetic Coding (CABAC), and channel coding, i.e., rate-1/2 Recursive Systematic Convolutional (RSC) code, in transmission. At the receiver, the turbo decoding concept is explored to develop a joint source–channel decoding structure using a soft-in soft-out channel decoder in conjunction with the source decoding functions, e.g., CABAC-based H.264 semantic verification, in an iterative manner. Illustrative designs of the proposed IJSCD scheme for an Additive White Gaussian Noise (AWGN) channel, including the derivations of key parameters for soft information are discussed. The performance of the proposed IJSCD scheme is shown for several video sequences. In the examples, for the same desired Peak Signal-to-Noise Ratio (PSNR), the proposed IJSCD scheme offers a savings of up to 2.1 dB in required channel Signal-to-Noise Ratio (SNR) as compared to a system using the same RSC code alone. The complexity of the proposed scheme is also evaluated. As the number of iterations is controllable, a tradeoff can be made between performance improvement and the overall complexity.     

Partial response continuous phase modulation and DPCM coding for speech transmission in cellular mobile radio systems

The performance of a speech transmission scheme with application to cellular digital mobile radio systems is considered. The source coder is embedded differential pulse code modulation (DPCM) and the modulation schemes belong to the class of partial response continuous phase modulation (CPM). Both quantizing noise and transmission errors contribute to the overall mean square error. The performance measure is the audio signal-to-noise ratio (SNR). It is seen that in a fading environment space diversity is very effective in bringing down the threshold of channel SNR to maintain the required audio SNR. The number of channels the system can support is evaluated under various conditions.     

DPCM Picture Coding with Adaptive Prediction

Adaptive prediction is a method of improving the prediction in differential pulse-code modulation (DPCM) systems. The information on contour directions derived from neighboring picture elements is used to select a suitable prediction value for the actual sample. An effective way for determining the contour direction, taking into account signal-source noise, quantization distortions and hardware complexity, is given. Adaptive prediction can be favorably combined with a switched quantizer. Simulations both with critical test signals and broadband TV pictures have shown that adaptive prediction can substantially improve the quality of pictures with high-definition contours. The sensitivity to signal-source noise and to transmission errors is small and comparable to fixed prediction DPCM systems.     

On joint estimation and decoding for channels with noise memory

In this letter we consider coded transmission over interference channels where the interference occurs in bursts and hence is considered to be impulsive. The bursty nature of the interference leads to memory in the overall noise process which is modeled as a 2-state Markov chain. Recent work on coded transmission for such channels has proposed decoding techniques assuming that perfect knowledge of the interference statistics are available at the receiver. In this work, we aim at completing the picture by proposing a novel algorithm that decodes without the knowledge of the interference statistics and highlighting the differences between the two cases.     

Interframe DPCM with robust median-based predictors fortransmission of image sequences over noisy channels

A new image sequence coding technique based on robust median-based predictors is presented for the transmission of image sequences over noisy channels. We analyze the robustness of median-based predictors against channel errors. A heuristic algorithm for the design of a robust predictor from a given median-based predictor is presented. It is shown that with small modifications in terms of a necessary requirement for a median-based predictor to be robust against channel errors, the robustness of a given median-based predictor can be considerably improved. Simulations on a real image sequence show significant improvement over the conventional differential pulse code modulation (DPCM) at high bit error rate (BER) using this new technique. The technique does not increase the transmission rate. It is shown that the quality of reconstructed images obtained by robust median-based predictors can be further improved by postprocessing the image using a nonlinear detail-preserving noise-smoothing filter.     

Unified design of iterative receivers using factor graphs

Iterative algorithms are an attractive approach to approximating optimal, but high-complexity, joint channel estimation and decoding receivers for communication systems. We present a unified approach based on factor graphs for deriving iterative message-passing receiver algorithms for channel estimation and decoding. For many common channels, it is easy to find simple graphical models that lead directly to implementable algorithms. Canonical distributions provide a new, general framework for handling continuous variables. Example receiver designs for Rayleigh fading channels with block or Markov memory, and multipath fading channels with fixed unknown coefficients illustrate the effectiveness of our approach     

Achievable rate for three-node discrete memoryless relay channel with generalized feedbacks

This paper studies the achievable rate for three-node discrete memoryless relay channel.Specifically in this mode,we explore two generalized feedbacks simultaneously:the source node actively collects feedback signals from the channel;and at the same time,the destination node actively transmits feedback signals to the relay node.These two feedback signals,which are called generalized feedback overheard from the channel that is likely to be noisy,induce that all the three nodes are in full duplex mode.The basic coding strategies of Cover and El Gamal are applied to the relay-source feedback transmission by the source forwarding the compressions of the channel output sequences at the relay node to the destination,and are also applied to the destination-relay feedback transmission to improve the decoding ability at the relay.Based on Cover and El Gamal coding,a new coding scheme adopting rate splitting and four-block Markov superposition encoding is proposed and the corresponding achievable rate is achieved.The proposed scheme is able to exploit two feedbacks simultaneously which can effectively eliminate underlying transmission bottlenecks for the channels.The derived achievable rate result generalizes several previously known results by including them as special cases.     

Coding for noisy channels with input-dependent insertions

Tree encoding and sequential decoding are considered for noisy channels that respond a random number of times to each input. Such channels appear in mathematical models of certain speech recognition systems. The decoding error probability and the channel capacity are bounded by extension of the methods of Jelinek and Zigangirov to noisy multilevel channels with input-dependent insertions. Certain analytical difficulties peculiar to the channels in question are indicated.     

Sequence MAP decoding of trellis codes for Gaussian and Rayleighchannels

This paper considers the use of sequence maximum a posteriori (MAP) decoding of trellis codes. A MAP receiver can exploit any “residual redundancy” that may exist in the channel encoded signal in the form of memory and/or a nonuniform distribution, thereby providing enhanced performance over very noisy channels, relative to maximum likelihood (ML) decoding. The paper begins with a first-order two-state Markov model for the channel encoder input. A variety of different systems with different source parameters, different modulation schemes, and different encoder complexities are simulated. Sequence MAP decoding is shown to substantially improve performance under very noisy channel conditions for systems with low-to-moderate redundancy, with relative gain increasing as the rate increases. As a result, coding schemes with multidimensional constellations are shown to have higher MAP gains than comparable schemes with two-dimensional (2-D) constellations. The second part of the paper considers trellis encoding of the code-excited linear predictive (CELP) speech coder's line spectral parameters (LSPs) with four-dimensional (4-D) QPSK modulation. Two source LSP models are used. One assumes only intraframe correlation of LSPs while the second one models both intraframe and interframe correlation. MAP decoding gains (over ML decoding) as much as 4 dB are achieved. Also, a comparison between the conventionally designed codes and an I-Q QPSK scheme shows that the I-Q scheme achieves better performance even though the first (sampler) LSP model is used     

On the design of globally optimal communication strategies for real-time noisy communication systems with noisy feedback

A real-time communication system with noisy feedback is considered. The system consists of a Markov source, forward and backward discrete memoryless channels, and a receiver with limited memory. The receiver can send messages to the encoder over the backward noisy channel. The encoding at the encoder and the decoding, the feedback, and the memory update at the receiver must be done in real-time. A distortion metric that does not tolerate delays is given. The objective is to design an optimal real-time communication strategy, i.e., design optimal real-time encoding, decoding, feedback, and memory update strategies to minimize a total expected distortion over a finite horizon. This problem is formulated as a decentralized stochastic optimization problem and a methodology for its sequential decomposition is presented. This results in a set of nested optimality equations that can be used to sequentially determine optimal communication strategies. The methodology exponentially simplifies the search for determining an optimal real-time communication strategy.     

Decoding of trellis-encoded signals in the presence of intersymbolinterference and noise

A novel receiver for data-transmission systems using trellis-coded modulation is investigated. It comprises a whitened-matched filter and a trellis decoder which combines the previously separated functions of equalization and trellis-coded modulation (TCM) decoding. TCM encoder, transmission channel, and whitened-matched filter are modeled by a single finite-state machine with combined intersymbol interference and code states. Using ISI-state truncation techniques and the set-partitioning principles inherent in TCM, a systematic method is then developed for reducing the state complexity of the corresponding ISI and code trellis. A modified branch metric is used for canceling those ISI terms which are not represented by the trellis states. The approach leads to a family of Viterbi decoders which offer a tradeoff between decoding complexity and performance. An adaptive version of the proposed receiver is discussed, and an efficient structure for reduced-state decoding is given. Simulation results are presented for channels with severe amplitude and phase distortion. It is shown that the proposed receiver achieves a significant gain in noise margin over a conventional receiver which uses separate linear equalization and TCM decoding     

Capacity-achieving codes for finite-state channels with maximum-likelihood decoding

Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.     

Unitary space-time modulation via Cayley transform

A prevoiusly proposed method for communicating with multiple antennas over block fading channels is unitary space-time modulation (USTM). In this method, the signals transmitted from the antennas, viewed as a matrix with spatial and temporal dimensions, form a unitary matrix, i.e., one with orthonormal columns. Since channel knowledge is not required at the receiver, USTM schemes are suitable for use on wireless links where channel tracking is undesirable or infeasible, either because of rapid changes in the channel characteristics or because of limited system resources. Previous results have shown that if suitably designed, USTM schemes can achieve full channel capacity at high SNR and, moreover, that all this can be done over a single coherence interval, provided the coherence interval and number of transmit antennas are sufficiently large, which is a phenomenon referred to as autocoding. While all this is well recognized, what is not clear is how to generate good performing constellations of (nonsquare) unitary matrices that lend themselves to efficient encoding/decoding. The schemes proposed so far either exhibit poor performance, especially at high rates, or have no efficient decoding algorithms. We propose to use the Cayley transform to design USTM constellations. This work can be viewed as a generalization, to the nonsquare case, of the Cayley codes that have been proposed for differential USTM. The codes are designed based on an information-theoretic criterion and lend themselves to polynomial-time (often cubic) near-maximum-likelihood decoding using a sphere decoding algorithm. Simulations suggest that the resulting codes allow for effective high-rate data transmission in multiantenna communication systems without knowing the channel. However, our preliminary results do not show a substantial advantage over training-based schemes.     

Embedding Data Into Pictures by Modulo Masking

Three systems are proposed for embedding data into industrial quality monochrome analog pictures. The video signal on each scan line is sampled, and a data bit is inserted into a block of three or five pels by modulo masking scrambling the luminance level of only one pel in the block. Prior to transmission, the combined data and video sequence is converted into a continuous signal with a bandwidth that is no greater than that of the original video signal. Using six images each containing 65 536 pels, Systems 1 and 2 embedded an average of 17 430 and 8713 bits per image, while System 3 accommodated data at a constant rate of 21 760 bits/image. The data embedding procedures of Systems 1, 2, and 3 operated with average picture SNR's of 41, 44, and 30 dB, respectively, when the transmission channel was ideal. When the transmission was over a channel composed of a second-order Butterworth filter plus additive noise that yield a channel SNR of 40 dB, no bit errors occurred but System 3 offered the greater safety margin to bit errors than Systems 1 and 2.     

Turbo codes-based image transmission for channels with multiple types of distortion

Product codes are generally used for progressive image transmission when random errors and packet loss (or burst errors) co-exist. However, the optimal rate allocation considering both component codes gives rise to high-optimization complexity. In addition, the decoding performance may be degraded quickly when the channel varies beyond the design point. In this paper, we propose a new unequal error protection (UEP) scheme for progressive image transmission by using rate-compatible punctured Turbo codes (RCPT) and cyclic redundancy check (CRC) codes only. By sophisticatedly interleaving each coded frame, the packet loss can be converted into randomly punctured bits in a Turbo code. Therefore, error control in noisy channels with different types of errors is equivalent to dealing with random bit errors only, with reduced turbo code rates. A genetic algorithm-based method is presented to further reduce the optimization complexity. This proposed method not only gives a better performance than product codes in given channel conditions but is also more robust to the channel variation. Finally, to break down the error floor of turbo decoding, we further extend the above RCPT/CRC protection to a product code scheme by adding a Reed-Solomon (RS) code across the frames. The associated rate allocation is discussed and further improvement is demonstrated.     

A simple SNR representation method for AMC schemes of MIMO systems with ML detector

Adaptive modulation and coding (AMC) is a powerful technique to enhance the link performance by adjusting the transmission power, channel coding rates and modulation levels according to channel state information. In order to efficiently utilize the AMC scheme, an accurate signal-to-noise ratio (SNR) value is normally required for determining the AMC level. In this paper, we propose a simple method to represent the SNR values for maximum likelihood (ML) detector in multi-input multi-output (MIMO) systems. By analyzing the relation between the upper bound and the lower bound of the ML detector performance, we introduce an efficient way to determine the SNR for the ML receiver. Based on the proposed SNR representation, an AMC scheme for single antenna systems can be extended to MIMO systems with ML detector. From computer simulations, we confirm that the proposed SNR representation allows us to achieve almost the same system throughput as the optimum AMC systems in frequency selective channels with reduced complexity.