Forward adaptive transform coding requires a codebook of transform matrices from which the best transform can be chosen for each macroblock in an image. Codebook construction involves designing a vector quantizer for a sample set of KarhunenLoeve transform (KLT) matrices. While several approaches to designing such matrix codebooks have been proposed in previous work [1] , [2] , these non-parametric methods carry out matrix quantization in very high dimensional spaces which can suffer from the curse of dimensionality. Furthermore, the resulting transform matrices are not scalable - if multiple transform block sizes are to be used, such as in video compression, a separate matrix codebook must be designed for each block size.

Recent research indicates that data-driven transforms can outperform the widely used separable two-dimensional discrete cosine transform (2D-DCT) in applications such as video coding. However, unlike the 2D-DCT, data-driven transforms are random matrices with no structure and do not lend themselves to fast computations. In this paper, we investigate a new approach to construct low-complexity data-driven transforms by exploiting a connection between the Givens rotation matrices and coordinate descent on the orthonormal matrix manifold. We propose a multi-path coordinate descent algorithm which is observed to produce better transform matrices than the simple coordinate descent. Our experiments with many images showed that the proposed algorithm can be used to design fast data-driven transforms which achieve a higher coding gain than the 2D-DCT in some image blocks.

This paper proposes a novel data-driven approach to designing orthonormal transform matrix codebooks for adaptive transform coding of any non-stationary vector processes which can be considered locally stationary. Our algorithm, which belongs to the class of block-coordinate descent algorithms, relies on simple probability models such as Gaussian or Laplacian for transform coefficients to directly minimize with respect to the orthonormal transform matrix the mean square error (MSE) of scalar quantization and entropy coding of transform coefficients. A difficulty commonly encountered in such minimization problems is imposing the orthonormality constraint on the matrix solution. We get around this difficulty by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold and leveraging known algorithms for unconstrained optimization on manifolds. While the basic design algorithm directly applies to non-separable transforms, an extension to separable transforms is also proposed. We present experimental results for adaptive transform coding of still images and video inter-frame prediction residuals, comparing the transforms designed using the proposed method and a number of other content-adaptive transforms recently reported in the literature.

We present a novel algorithm for designing a transform codebook for adaptive transform coding a non-stationary source, where the codebook contains a set of or-thonormal transform matrices. The non-stationary source is modeled by a block-wise (locally) stationary process so that all vectors in a given block can be coded using a single transform-matrix chosen from the codebook. The transform-matrix codebook is designed such that the mean-square error (MSE) of coding locally stationary blocks, averaged over the ensemble of blocks (AMSE) is minimized. First, a sequence of training vectors from the non-stationary source (such as blocks of pixels extracted from images) is segmented into locally stationary blocks of vectors. Our design algorithm starts with an initial codebook and iteratively updates the codebook for the training set, similar to the well-known generalized Lloyd algorithm for vector quantizer design. Each iteration consists of two steps: 1) the training set is partitioned into subsets by encoding the training set using the current transform codebook, and 2) the code-book is updated by computing a centroid transform-matrix for each subset. A major difference compared to the standard Lloyd algorithm however is the requirement to enforce an orthonormality constraint on the matrices in the codebook during the computation of centroids. This is accomplished by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold. Gradient-descent on the Stiefel manifold is then used to compute the centroids. Essential to the implementation of manifold gradient-descent is an expression for the AMSE which is differentiable with respect to the transform matrix. Towards this end, we present two expressions whose matrix derivatives can be analytically obtained: 1) an approximate high-rate expression assuming Gaussian distributed source vectors, and 2) an exact finite-rate expression assuming Laplace distributed transform coefficients.

It is known that source-channel separation is sub-optimal for communicating correlated Gaussian sources over a Gaussian multiple access channel (GMAC). Considering a two-to-one GMAC which undergoes Rayleigh block-fading, we present a novel approach to practical joint source-channel coding for the scenario in which the common receiver has instantaneous CSI but only the CSI distribution is available to the individual transmitters. This approach, referred to as source-channel trellis-coded vector quantization (SC-TCVQ), simply relies on using TCVQs as fixed-rate source-channel encoders. One key issue is the optimization of the TCVQ codebooks to the mean channel signal-to-noise ratio (CSNR), and to this end, we present an analytical method to obtain the rates required for codebook design. Another key issue is the joint estimation of the sources at the receiver, for which we present a detector-estimator based on the Cartesian product of the two encoder-trellises. Simulation results show that the proposed SC-TCVQ codes, in some cases, can even beat the asymptotic performance bound for a separate source-channel code consisting of a distributed vector quantizer and capacity achieving channel codes. SC-TCVQ appears to be the best known practical code design to date for the given communication problem.

A new approach to hybrid digital-analog (HDA) video transmission over orthogonal frequency division multiplexing (OFDM) channels is presented. The goal is to achieve the best video quality by optimal power allocation, when the OFDM sub-channels have unequal and time-varying signal-to-noise ratios (SNR). In this method, the quantization error of a video encoder is superimposed on digital quadrature amplitude modulation (QAM) symbols. A solution to the power allocation problem is presented. Experimental comparisons with layered video coding and adaptive modulation shows that the proposed HDA approach is able to achieve a better video quality most of the time, particularly whenever there is a high motion content.

We consider the problem of sending a bivariate Gaussian source over a slow-fading multiple-access channel (MAC) with no channel state information at the transmitters. A joint source-channel coding (JSCC) scheme is constructed using hybrid digital- analog (HDA) coding techniques to minimize the average distortion over the uncertain MAC. Numerical results show that, under Rayleigh fading, the proposed HDA scheme can outperform the source-channel separation approach and the uncoded approach as the power-to-noise ratio increases. A HDA scheme based on orthogonal multiple access is designed for comparison.

An approach to transmitting multiple correlated sources over a Gaussian multiple-access channel (GMAC) using code-division multiple-access (CDMA) is investigated. A block coordinate descent (BCD) algorithm is presented which can be used to optimize CDMA signatures for a given source covariance matrix under individual transmitter power constraints. This algorithm can be used to design non-orthogonal CDMA signatures for GMACs with arbitrary input alphabets, fading, and colored noise. While the main focus has been the design of signatures which minimize the mean square error (MSE) of linear decoding, the algorithm can also be used to design signatures which maximize the input-output mutual information of the channel. This paper investigates the uncoded transmission of Gaussian sources and the coded transmission of binary sources over a GMAC using joint source-channel (JSC) optimized CDMA signatures under constraints on transmitter power and channel bandwidth, scenarios relevant to wireless sensor networks. By using simple coding schemes which only rely on linear multi-user detection and independent channel decoding of a large number of sources, it is demonstrated that CDMA-based JSC coding can exploit inter-source correlation to achieve lower distortion (Gaussian sources) or higher rates (binary sources) compared to conventional separate source-channel (SSC) coding over the same channel bandwidth.

Motivated by potential applications in wireless sensor networks, we consider the problem of communicating a large number of correlated analog sources over a Gaussian multiple-access channel using non-orthogonal code-division multiple-access (CDMA). We present a joint source-channel decoder which exploits the inter-source correlation for interference reduction in the CDMA channel. This decoder uses a linear minimum mean square error (MMSE) multi-user detector (MUD) in tandem with a MMSE joint source decoder for multiple sources to achieve a computational complexity that scales with the number of sources. However, iterative exchange of extrinsic information between the MUD and the joint source decoder leads to improved interference cancellation. Experimental results obtained with decoding observations from Gaussian random fields show that the proposed iterative decoder can achieve a considerable performance gain compared to a non-iterative decoder. The results also show that the iterative decoder is robust against the performance degradation due to correlated interference in a non-orthogonal CDMA channel.

This paper presents a general approach to designing distributed joint source channel (DJSC) codes with arbitrary rates for communication of a pair of correlated binary sources over noisy channels. In this approach, both distributed compression and channel error correction are simultaneously achieved by transmitting, for each source, a fraction of the information bits together with the parity bits of a systematic channel code. This approach is shown to be asymptotically optimal, i.e., any rate-pair in the achievable rate-region can be approached as the codeword length is increased. The practical realization of such a code requi res the design of a pair of channel codes with unequal error protection (UEP) properties determined by the inter-source correlation and the channel capacity available to each source. Towards this end, a linear programming based procedure for jointly optimizing the degree profiles of a pair of irregular LDPC codes to achieve the required UEP properties is presented. Experimental results obtained with both binary symmetric channels and binary-input Gaussian channels are presented, which demonstrate that the proposed UEP-DJSC codes can significantly outperform separate source-channel codes, as well as previously reported joint source-channel coding schemes, particularly for short codeword lengths.

A practical approach to designing distributed transform codes for high-dimensional correlated Gaussian vectors is presented. In this approach, source-splitting based on linear approximations is used to achieve arbitrary rate-pairs, by using only Wyner-Ziv (WZ) quantizers. The optimal bit-allocation among a dependent set of WZ quantizers is found by using a tree-search algorithm. Experimental results obtained with actual designs, which use conditional entropy constrained trellis coded quantizers (CEC-TCQ) and Slepian-Wolf (SW) codes, are presented.

A practical approach to designing distributed joint source channel (DJSC) codes for correlated binary sources using LDPC codes is presented. In this approach, both distributed compression and channel error protection are achieved by optimally puncturing bits of a systematic channel code to match the source correlation and channel error probability. This requires the design of a channel code with a specific unequal error protection (UEP) property. Towards this end, we present a linear-programming based algorithm for optimizing an irregular LDPC code for a given level of source correlation and channel noise. Experimental results are presented for both binary symmetric channels and Gaussian channels, which demonstrate that the proposed DJSC codes can significantly outperform the best code found through random search, tandem source-channel codes and previously reported schemes based on turbo codes when the encoding delay is constrained.

An important transmitter adaptation technique used in multiple-input multiple-output (MIMO) communication systems is precoding based on the dominant right-singular vectors of the channel matrix. These vectors are typically estimated at the receiver, quantized, and fed-back to the transmitter via a low-rate feedback channel. We present a method for designing an efficient low-rate quantizer for the dominant right singular vectors of a MIMO channel matrix, which exploits the memory in the slow-varying channel fading process. A memory-based (recursive) quantizer is considered which quantizes the time-trajectory of points representing the channel subs-spaces on a Grassmannian manifold. The quantizer codebook is optimized with respect to an objective functions which can be directly related to MIMO channel capacity. The main contribution of this paper is the derivation of a stochastic gradient-based algorithm for codebook optimization. Numerical results obtained with channel simulations are presented, which demonstrate the MIMO channel capacity improvement achieved by using the codebooks optimized as proposed in this paper.

The focus of this paper is the modeling of a class of stationary non-Gaussian auto-regressive processes that often find applications in statistical signal processing. We propose a general simulation procedure for constructing a time series model with a near-Laplace marginal distributions. Our approach is based on a class of Monte Carlo rejection algorithms. A theoretical analysis of the average complexity of the proposed algorithms for simulating the time series model is included.

Scalable joint decoding of correlated observations transmitted using distributed quantization in a sensor-network is considered. In particular, quantized observations are modeled as a Markov-random field (MRF), from which we construct a factor-graph for implementing the decoder using the well known sum-product algorithm. An attractive property of this approach is that the decoder complexity can be controlled by the choice of the clique structure used to define the Gibbs distribution of the MRF model. The experimental results obtained with a widely used correlated Gaussian observation model is presented, which demonstrate that substantial performance gains can be achieved by joint decoding based on simple clique structures and potential functions.

This paper presents a low-complexity iterative joint detection and decoding algorithm for finite geometry-low density parity check (FG-LDPC) coded multiple-input multiple-output (MIMO) systems, in which the MIMO channel detector and the FG-LDPC decoder iteratively exchange soft information. The key to the simplicity of the algorithm is the use of a bit flipping-based decoder for FG-LDPC code. An important issue addressed here is the generation of soft information from the binary outputs of the bit-flipping decoder to be fed back to the MIMO detector. Simulation results show that the proposed joint detection and decoding algorithm achieves a substantial reduction in decoding error probability compared to a cascaded detector and a decoder. We also compare the performance with belief-propagation (BP) based detector-decoders which are significantly more complex. The new algorithm provides a practical approach to joint detection and decoding of popular FG-LDPC codes in a MIMO system, a task which is computationally unmanageable with a BP algorithm.

Minimum mean square error (MMSE) decoding in a large-scale sensor network which employs distributed quantization is considered. Given that the computational complexity of the optimal decoder is exponential in the network size, we present a framework based on Bayesian networks for designing a near-optimal decoder whose complexity is only linear in network size (hence scalable). In this approach, a complexity-constrained factor graph, which approximately represents the prior joint distribution of the sensor outputs, is obtained by constructing an equivalent Bayesian network using the maximum likelihood (ML) criterion. The decoder executes the sum-product algorithm on the simplified factor graph. Our simulation results have shown that the scalable decoders constructed using the proposed approach perform close to optimal, with both Gaussian and non-Gaussian sensor data.

We consider minimum mean square error (MMSE) decoding in a dense sensor network where distributed quantization is used to improve the performance. In view of the exponential complexity of the optimal decoder, we present a framework based on Bayesian networks for designing a scalable, but near-optimal decoder. In this approach, a complexity- constrained factor graph is obtained by an algorithm which constructs an equivalent Bayesian network using the maximum likelihood (ML) criterion, based on a training set of sensor observations. Our simulation results show that, the scalable decoders constructed using the proposed approach preform close to optimal, with both Gaussian and non-Gaussian sensor data.

Abstract — This paper derives exact expressions for the symbol error rate (SER) of orthogonal space-time block codes over a spatially correlated multiple-input multiple-output (MIMO) channel, in which the signal propagation suffers from a keyhole effect. A correlated double Rayleigh fading keyhole channel is assumed and easy to evaluate expressions are presented for multi-level phase shift keying (M-PSK), pulse amplitude modulation (M-PAM), and quadrature amplitude modulation (M-QAM). These expressions are verified by estimating the SER via the simulation of the MIMO system. The given expressions are then used to quantify the performance improvements attainable with minimum SER linear precoding over a correlated keyhole channel. I.

This paper investigates the design of a system of predictive vector quantizers for distributed sources with memory, in which linear prediction is used to exploit the source memory, while distributed quantization is used to exploit the correlation between sources. A training-based algorithm is proposed for jointly designing the predictors, binning functions, and reconstruction codebooks of the given system to match the intra-and inter-source correlations. In order to demonstrate the effectiveness of the algorithm, experimental results obtained by designing both scalar and vector quantizers for a set of distributed Gauss-Markov sources are presented. While the optimality of these designs is unknown, it is shown that they convincingly outperform several other alternatives.

An algorithm for designing linear prediction-based two-channel multiple-description predictive-vector quantizers (MD-PVQs) for packet-loss channels is presented. This algorithm iteratively improves the encoder partition, the set of multiple description codebooks, and the linear predictor for a given channel loss probability, based on a training set of source data. The effectiveness of the designs obtained with the given algorithm is demonstrated using a waveform coding example involving a Markov source as well as vector quantization of speech line spectral pairs

An approach to multiple description block quantization of a correlated source for transmission over a lossy communication channel is presented. The main idea is to optimally control the redundancy due to both the quantizer index assignment and the residual temporal correlation within a block of quantizer outputs. This is achieved by using a trellis encoder in which each state has an associated index assignment, a finite-state central decoder, and a set of Markov-model based side-decoders which exploit the encoder residual redundancy to reconstruct the source based on an incomplete set of descriptions. An iterative descent algorithm is presented for optimizing the proposed coding system for source statistics and channel loss probability. Simulation results are given which demonstrate the performance of trellis quantizers designed for a Gauss-Markov source.

A design of a robust predictive vector quantizer for packet-loss channels is presented. A linear prediction-based quantizer is considered, in which the prediction residual is quantized by a multiple description vector quantizer, and a simple procedure is developed for iteratively improving the system components, including the linear predictor, for a given channel loss probability. Experimental results obtained by designing quantizers for a Markov source as well as for speech line spectral pairs are presented

The scenario considered in this paper is the transmission of a continuous information source over a set of erasure channels, by using a multiple description quantizer to deal with channel erasures and a convolutional channel code on each channel to deal with random bit errors. The diversity available in multiple descriptions is subsequently exploited in Viterbi sequence detectors to jointly decode the convolutional codes. Two approaches to joint decoding are presented and investigated. Simulation results are presented for two-channel multiple description quantization of Gaussian sources which demonstrate the potential improvements in end-to-end source distortion achievable with joint decoding of channel codes in a multiple description system. We also compare the performance of joint Viterbi detectors with that of turbo-style iterative decoding of multiple-description codes proposed earlier.

Theoretically, the achievable side-distortion of a multiple description (MD) quantizer has a lower bound for a given level of central distortion, but such rate-distortion bounds cannot be achieved in practice. The paper presents a new decoder which exploits the residual redundancy in a sequence of outputs from a sub-optimal MD encoder to reduce side-distortion, without compromising central distortion. A hidden Markov model-based recursive side-decoder is derived for the reconstruction of a source from an incomplete set of descriptions. Simulation results based on encoding a Gauss-Markov source and a simulated speech process are presented to demonstrate the effectiveness of the proposed decoder.

We investigate joint source-channel decoding for vector quantization over the finite-state Markov channel. In particular, we consider the decoding problem in which the channel state information is not available to the decoder. Based on hidden Markov modeling of the channel output, two decoding strategies are proposed. The first one is a soft-decoder which estimates the source reconstruction vectors directly from the observed channel output samples. The second one is a hard-decoder based on joint MAP estimation of channel symbols and channel states. Application of these decoders to wireless channels with multipath fading is also investigated. Simulation results are provided for a flat fading wireless channel and a Gauss-Markov source.

The practical design of multiple description quantizers for diversity-based communication is investigated. A simulated annealing based method is proposed for obtaining the optimal index assignment for a multiple-description vector quantizer. This method can be used to design quantizers having an arbitrary number of descriptions with equal or unequal transmission rates. According to the simulation results, the proposed method yields multiple-description quantizers with performance comparable with, or better than, previously reported results.

Finite-state vector quantization (FSVQ) over a noisy channel is studied. A major drawback of a finite-state decoder is its inability to track the encoder in the presence of channel noise. In order to overcome this problem, we propose a nontracking decoder which directly estimates the code vectors used by a finite-state encoder. The design of channel-matched finite-state vector quantizers for noisy channels, using an iterative scheme resembling the generalized Lloyd algorithm, is also investigated. Simulation results based on encoding a Gauss-Markov source over a memoryless Gaussian channel show that the proposed decoder exhibits graceful degradation of performance with increasing channel noise, as compared with a finite-state decoder. Also, the channel-matched finite-state vector quantizers are shown to outperform channel-optimized vector quantizers having the same vector dimension and rate. However, the nontracking decoder used in the channel-matched finite-state quantizer has a higher computational complexity, compared with a channel-optimized vector-quantizer decoder. Thus, if they are allowed to have the same overall complexity (encoding and decoding), the channel-optimized vector quantizer can use a longer encoding delay and achieve similar or better performance. Finally, an example of using the channel-matched finite-state quantizer as a backward-adaptive quantizer for nonstationary signals is also presented.

Summary form only given. Channel optimized vector quantization (COVQ) has received considerable attention as an approach to joint source-channel coding. COVQ for hidden Markov channels was studied, with application in wireless communication over fading channels. The optimal VQ decoding was considered for finite state channels when the channel state is not explicitly observed at the receiver. A hidden Markov model (HMM) with a continuous observation space is constructed for the channel by assuming both channel input and channel state are first-order Markov process. A recursive-decoding algorithm is derived for computing the minimum mean square error (MMSE) optimal estimate for the source vector, based on the observed channel output sequence. In simulation experiments, the performance of a communications system based on the proposed quantizer is investigated for a Gauss-Markov signal source and a frequency non-selective Rayleigh fading channel. The results indicate that for fading channels, proposed soft-decoding based COVQ can results in a substantial improvement of performance over detection based COVQ.

In this paper, finite-state vector quantization (FSVQ) over noisy channels is studied. In particular a robust, time-recursive algorithm is proposed for reconstructing the output from a finite-state encoder, observed through a noisy channel. In contrast to an ordinary finite-state decoder, the proposed decoder exhibits graceful degradation of performance with increasing channel noise. We also consider the iterative optimization of encoder and decoder for designing channel optimized FSVQ. Simulation results based on Gauss-Markov source and additive white Gaussian noise channel are presented, and it is shown that robust FSVQ designed by methodology introduced here can outperform memory less channel optimized vector quantization at the same rate. Soft-decoding at the receiver, which provides an additional performance gain, is also considered.

A Lloyd-style iterative algorithm for designing predictive vector quantizers optimized to both source and channel is presented. We consider communication systems which use waveform channels and soft-decoding at the receiver. Based on reasonable assumptions, a set of conditions for the optimality of the predictive encoder and decoder, including the linear predictor, is derived. Simulation results based on a Gauss-Markov source and additive white Gaussian noise channel are presented. These results show that, when hard-decoding is used, the predictive codes designed here perform nearly identically to those obtained by gradient-search optimization techniques. It is also demonstrated that soft-decoding based systems designed with the proposed algorithm significantly outperform the hard-decoding systems.