The problem of rate-distortion efficient constructions is studied for the problem of source coding with side information (SCSI), which has assumed heightened interest. While the Wyner-Ziv theorem from information theory has prescribed rate-distortion performance bounds for the SCSI problem, the gap between theory and practice has remained large. To reduce this gap, two different frameworks are proposed based on a trellis construction and a turbo-based construction respectively. Simulation results on the Gaussian SCSI problem reveal the promise of the proposed approaches: at 1 bit per sample, 0.5 bits/sample, 0.25 bits/sample and 0.125 bits/sample, these constructions attain performance within 1.3 dB, 1.1 dB, 0.85 dB and 0.5 dB respectively of the theoretical Wyner-Ziv rate-distortion bound.

There has been a lot of interest recently in applying channel coding with side information (CCSI) concepts to data hiding. Part of the interest stems from the fact that information theoretic bounds can be derived for such systems. In this paper, we model the audio data embedding problem as a parallel CCSI problem. This is done by dividing the audio spectrum into frequency bins and then treating each bin as a separate CCSI channel. A perceptual mask is derived from the audio signal to determine the amount of power to use in each channel. It acts as a "water-filling" formula by determining the amount of distortion that can be introduced into each frequency bin without introducing audible distortion. As a result, our data embedding scheme will be imperceptible to the human ear. An exciting application for our audio data embedding solution is to embed data within the audio signal that will enable surround sound at the receiver. The resulting surround sound system will be better than existing surround sound systems that are based on manipulating two stereo channels to derive the other surround channels.

We propose a novel approach to reducing energy consumption in sensor networks using a distributed adaptive signal processing framework and efficient algorithm. While the topic of energy-aware routing to alleviate energy consumption in sensor networks has received attention recently (C. Toh, 2001; R. Shah et al., 2002), in this paper, we propose an orthogonal approach to previous methods. Specifically, we propose a distributed way of continuously exploiting existing correlations in sensor data based on adaptive signal processing and distributed source coding principles. Our approach enables sensor nodes to blindly compress their readings with respect to one another without the need for explicit and energy-expensive intersensor communication to effect this compression. Furthermore, the distributed algorithm used by each sensor node is extremely low in complexity and easy to implement (i.e., one modulo operation), while an adaptive filtering framework is used at the data gathering unit to continuously learn the relevant correlation structures in the sensor data. Our simulations show the power of our proposed algorithms, revealing their potential to effect significant energy savings (from 10%-65%) for typical sensor data corresponding to a multitude of sensor modalities.

We explore the information-theoretic duality between source coding with side information at the decoder and channel coding with side information at the encoder. We begin with a mathematical characterization of the functional duality between classical source and channel coding, formulating the precise conditions under which the optimal encoder for one problem is functionally identical to the optimal decoder for the other problem. We then extend this functional duality to the case of coding with side information. By invoking this duality, we are able to generalize the result of Wyner and Ziv (1976) relating to no rate loss for source coding with side information from Gaussian to more arbitrary distributions. We consider several examples corresponding to both discrete- and continuous-valued cases to illustrate our formulation. For the Gaussian cases of coding with side information, we invoke geometric arguments to provide further insights into their duality. Our geometric treatment inspires the construction and dual use of practical coset codes for a large class of emerging applications for coding with side information, such as distributed sensor networks, watermarking, and information-hiding communication systems.

Channel coding with side information (CCSI) provides a powerful framework for constructing data embedding codes. As a result, there has been a considerable amount of work done in trying to apply these CCSI codes to the field of image and video watermarking. The CCSI codes that exist in the literature however, are relatively far from theoretical bounds. Furthermore, these codes, by themselves, are not well-suited for dealing with geometrical distortions which often appear in watermarking attacks. In this paper we propose a CCSI code that is closer to the theoretical bounds (within 2.0 dB) than the codes that exist in the literature. In addition, we show how this code construction can be combined with a synchronization code to deal with geometrical distortions.

Channel coding with side information (CCSI) provides a powerful framework for constructing data embedding codes. As a result, there has been a considerable amount of work done in trying to apply these CCSI codes to the field of image and video watermarking. The CCSI codes that exist in the literature (see Chou, J. et al., 1999; Kesal, M. et al., 2000; Eggers, J. et al., 2001), however, are relatively far from theoretical bounds. Furthermore, these codes, by themselves, are not well-suited for dealing with geometrical distortions which often appear in watermarking attacks. We propose a CCSI code that is closer to the theoretical bounds (within 2.0 dB) than the codes that exist in the literature. In addition, we show how this code construction can be combined with a synchronization code to deal with geometrical distortions.

We combine recent theoretical and algorithmic advances in the area of information-hiding with the current mature knowledge-base in the human audio perception system to propose a novel audio data-hiding technique that significantly pushes the state-of-the-art in the field. Our work is based on a combination of advances in two disjoint fields: information-hiding and human auditory masking. The field of information-hiding has recently seen a resurgence due to advances in the understanding of fundamental bounds from information theory. By integrating this with the human perceptual system knowledge that has been successfully exploited for several years in the audio compression community, we derive a new and improved audio data-hiding technique that finds application in a number of exciting scenarios like music enhancement and digital communications over analog data channels. Our preliminary results show that we can embed data at a rate an order of magnitude higher than existing audio data hiding systems, while being robust to channel noise.

Inspired by a previously proposed constructive framework for the distributed source coding problem. We propose a powerful constructive approach to the watermarking problem, emphasizing the dual rules of distributed source coding with side information at the decoder and channel coding with side information at the encoder. In our framework, we explore various source and channel codes to close the gap on the achievable capacity of watermarking systems. We propose two methods of solution, one which is based on optimal rate-distortion quantizers and the other based on robust optimization and convex programming. The resulting watermarking schemes, when subjected to additive white gaussian noise (AWGN) attacks, achieve results which are comparable to or better than the best watermarking schemes in the literature.

We propose a powerful new solution to the multimedia watermarking problem by exploiting its duality with another problem for which we have recently made pioneering constructive contributions. This latter problem is that of distributed source coding, or compression of correlated sources that are distributed. We show how these two seemingly unrelated problems are actually duals of each other. We exploit this duality by transforming our recently introduced powerful constructive framework for the distributed compression problem in [13] to a corresponding dual framework for the watermarking problem. Simulations expose the significant performance gains attained by our proposed watermarking approach and reveal its exciting potential for next-generation watermarking techniques. This can be accredited to the exploitation of the dual roles played by source codes and channel codes in the two problems.

Block cyclic redundancy check (CRC) codes are typically used to perform error detection in automatic repeat request (ARQ) protocols for data communications. Although efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. This method of error detection, first introduced by Bell, Witten, and Cleary (1990), is achieved through the use of an arithmetic codec, and has the attractive feature that it can be combined physically with arithmetic source coding, which is widely used in state of-the-art image coders. We analytically optimize the tradeoff between added redundancy and error-detection time, achieving significant gains in bit rate throughput over conventional ARQ schemes for binary symmetric channel models for all probabilities of error.

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how the new error detection framework improves the overall performance of transmission systems, and show how sizeable performance gains can be attained. We focus on two popular scenarios: (i) automatic repeat request (ARQ) based transmission; and (ii) forward error correction frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code.

Despite their widespread popularity, the JPEG and MPEG compression standards can lead to noticeable "blocking" artifacts-artifical rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.

Despite their widespread popularity, the Joint Photographers Expert Group (JPEG) and Motion Pictures Expert Group (MPEG) compression standards can lead to noticeable "blocking" artifacts-artificial rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.