In many scenarios, side information naturally exists in point-to-point communications. Although side information can be present in the encoder and/or decoder and thus yield several cases, the most important case that worths particular attention is source coding with side information at the decoder (Wyner-Ziv coding) which requires different design strategies compared to the the conventional source coding problem. Due to the difficulty caused by the joint design of random variable and reconstruction function, a common approach to this lossy source coding problem is to apply conventional vector quantization followed by Slepian-Wolf coding. In this thesis, we investigate the best rate-distortion performance achievable asymptotically by practical Wyner-Ziv coding schemes of the above approach from an information theoretic viewpoint and a numerical computation viewpoint respectively.From the information theoretic viewpoint, we establish the corresponding rate-distortion function $\hat{R}_{WZ}(D)$ for any memoryless pair $(X,Y)$ and any distortion measure. Given an arbitrary single letter distortion measure $d$, it is shown that the best rate achievable asymptotically under the constraint that $X$ is recovered with distortion level no greater than $D \geq 0$ is $\hat{R}_{WZ}(D) = \min_{\hat{X}} [I(X; \hat{X}) - I(Y; \hat{X})]$, where the minimum is taken over all auxiliary random variables $\hat{X}$ such that $Ed(X, \hat{X}) \leq D$ and $\hat{X}\to X \to Y$ is a Markov chain.Further, we are interested in designing practical Wyner-Ziv coding. With the characterization at $\hat{R}_{WZ}(D)$, this reduces to investigating $\hat{X}$. Then from the viewpoint of numerical computation, the extended Blahut-Arimoto algorithm is proposed to study the rate-distortion performance, as well as determine the random variable $\hat{X}$ that achieves $\hat{R}_{WZ}(D)$ which provids guidelines for designing practical Wyner-Ziv coding.In most cases, the random variable $\hat{X}$ that achieves $\hat{R}_{WZ}(D)$ is different from the random variable $\hat{X}'$ that achieves the classical rate-distortion $R(D)$ without side information at the decoder. Interestingly, the extended Blahut-Arimoto algorithm allows us to observe an interesting phenomenon, that is, there are indeed cases where $\hat{X} = \hat{X}'$. To gain deep insights of the quantizer's design problem between practical Wyner-Ziv coding and classic rate-distortion coding schemes, we give a mathematic proof to show under what conditions the two random quantizers are equivalent or distinct. We completely settle this problem for the case where ${\cal X}$, ${\cal Y}$, and $\hat{\cal X}$ are all binary with Hamming distortion measure.We also determine sufficient conditions (equivalent condition) for non-binary alphabets with Hamming distortion measure case and Gaussian source with mean-squared error distortion measure case respectively.

In many scenarios, side information naturally exists in point-to-point communications. Although side information can be present in the encoder and/or decoder and thus yield several cases, the most important case that worths particular attention is source coding with side information at the decoder (Wyner-Ziv coding) which requires different design strategies compared to the the conventional source coding problem. Due to the difficulty caused by the joint design of random variable and reconstruction function, a common approach to this lossy source coding problem is to apply conventional vector quantization followed by Slepian-Wolf coding. In this thesis, we investigate the best rate-distortion performance achievable asymptotically by practical Wyner-Ziv coding schemes of the above approach from an information theoretic viewpoint and a numerical computation viewpoint respectively.From the information theoretic viewpoint, we establish the corresponding rate-distortion function $\hat{R}_{WZ}(D)$ for any memoryless pair $(X,Y)$ and any distortion measure. Given an arbitrary single letter distortion measure $d$, it is shown that the best rate achievable asymptotically under the constraint that $X$ is recovered with distortion level no greater than $D \geq 0$ is $\hat{R}_{WZ}(D) = \min_{\hat{X}} [I(X; \hat{X}) - I(Y; \hat{X})]$, where the minimum is taken over all auxiliary random variables $\hat{X}$ such that $Ed(X, \hat{X}) \leq D$ and $\hat{X}\to X \to Y$ is a Markov chain.Further, we are interested in designing practical Wyner-Ziv coding. With the characterization at $\hat{R}_{WZ}(D)$, this reduces to investigating $\hat{X}$. Then from the viewpoint of numerical computation, the extended Blahut-Arimoto algorithm is proposed to study the rate-distortion performance, as well as determine the random variable $\hat{X}$ that achieves $\hat{R}_{WZ}(D)$ which provids guidelines for designing practical Wyner-Ziv coding.In most cases, the random variable $\hat{X}$ that achieves $\hat{R}_{WZ}(D)$ is different from the random variable $\hat{X}'$ that achieves the classical rate-distortion $R(D)$ without side information at the decoder. Interestingly, the extended Blahut-Arimoto algorithm allows us to observe an interesting phenomenon, that is, there are indeed cases where $\hat{X} = \hat{X}'$. To gain deep insights of the quantizer's design problem between practical Wyner-Ziv coding and classic rate-distortion coding schemes, we give a mathematic proof to show under what conditions the two random quantizers are equivalent or distinct. We completely settle this problem for the case where ${\cal X}$, ${\cal Y}$, and $\hat{\cal X}$ are all binary with Hamming distortion measure.We also determine sufficient conditions (equivalent condition) for non-binary alphabets with Hamming distortion measure case and Gaussian source with mean-squared error distortion measure case respectively.

Driven by a host of emerging applications (e.g., sensor networks and wireless video), distributed source coding (i.e., Slepian-Wolf coding, Wyner-Ziv coding and various other forms of multiterminal source coding), has recently become a very active research area. In this thesis, we first design a practical coding scheme for the quadratic Gaussian Wyner-Ziv problem, because in this special case, no rate loss is suffered due to the unavailability of the side information at the encoder. In order to approach the Wyner-Ziv distortion limit D??W Z(R), the trellis coded quantization (TCQ) technique is employed to quantize the source X, and irregular LDPC code is used to implement Slepian-Wolf coding of the quantized source input Q(X) given the side information Y at the decoder. An optimal non-linear estimator is devised at the joint decoder to compute the conditional mean of the source X given the dequantized version of Q(X) and the side information Y . Assuming ideal Slepian-Wolf coding, our scheme performs only 0.2 dB away from the Wyner-Ziv limit D??W Z(R) at high rate, which mirrors the performance of entropy-coded TCQ in classic source coding. Practical designs perform 0.83 dB away from D??W Z(R) at medium rates. With 2-D trellis-coded vector quantization, the performance gap to D??W Z(R) is only 0.66 dB at 1.0 b/s and 0.47 dB at 3.3 b/s. We then extend the proposed Wyner-Ziv coding scheme to the quadratic Gaussian multiterminal source coding problem with two encoders. Both direct and indirect settings of multiterminal source coding are considered. An asymmetric code design containing one classical source coding component and one Wyner-Ziv coding component is first introduced and shown to be able to approach the corner points on the theoretically achievable limits in both settings. To approach any point on the theoretically achievable limits, a second approach based on source splitting is then described. One classical source coding component, two Wyner-Ziv coding components, and a linear estimator are employed in this design. Proofs are provided to show the achievability of any point on the theoretical limits in both settings by assuming that both the source coding and the Wyner-Ziv coding components are optimal. The performance of practical schemes is only 0.15 b/s away from the theoretical limits for the asymmetric approach, and up to 0.30 b/s away from the limits for the source splitting approach.

The growing popularity of video sensor networks and video celluar phones has generated the need for low-complexity and power-efficient multimedia systems that can handle multiple video input and output streams. While standard video coding techniques fail to satisfy these requirements, distributed source coding is a promising technique for ??uplink?? applications. Wyner-Ziv coding refers to lossy source coding with side information at the decoder. Based on recent theoretical result on successive Wyner-Ziv coding, we propose in this thesis a practical layered Wyner-Ziv video codec using the DCT, nested scalar quantizer, and irregular LDPC code based Slepian-Wolf coding (or lossless source coding with side information) for noiseless channel. The DCT is applied as an approximation to the conditional KLT, which makes the components of the transformed block conditionally independent given the side information. NSQ is a binning scheme that facilitates layered bit-plane coding of the bin indices while reducing the bit rate. LDPC code based Slepian-Wolf coding exploits the correlation between the quantized version of the source and the side information to achieve further compression. Different from previous works, an attractive feature of our proposed system is that video encoding is done only once but decoding allowed at many lower bit rates without quality loss. For Wyner-Ziv coding over discrete noisy channels, we present a Wyner-Ziv video codec using IRA codes for Slepian-Wolf coding based on the idea of two equivalent channels. For video streaming applications where the channel is packet based, we apply unequal error protection scheme to the embedded Wyner-Ziv coded video stream to find the optimal source-channel coding trade-off for a target transmission rate over packet erasure channel.

Thèse doctorat : Informatique : Rennes 1 : 2008. / Titre provenant de la page du titre du document électronique. Bibliogr. p. 209-218.

This thesis addresses the optimal scalar quantizer design for two problems, i.e. the two-stage Wyner-Ziv coding problem and the multiple description coding problem for finite-alphabet sources. The optimization problems are formulated as the minimization of a weighted sum of distortions and rates. The proposed solutions are globally optimal when the cells in each partition are contiguous. The solution algorithms are both based on solving the single-source or the all-pairs minimum-weight path (MWP) problems in certain weighted directed acyclic graphs (WDAG). When the conventional dynamic programming technique is used to solve the underlying MWP problems the time complexity achieved is $O(N^3)$ for both problems, where $N$ is the size of the source alphabet. We first present the optimal design of a two-stage Wyner-Ziv scalar quantizer with forwardly or reversely degraded side information (SI) {for finite-alphabet sources and SI}. We assume that binning is performed optimally and address the design of the quantizer partitions. A solution based on dynamic programming is proposed with $O(N^3)$ time complexity. %The solution relies on finding the single-source or the all-pairs MWP in several one dimensional WDAGs. Further, a so-called {\it partial Monge property} is additionally introduced and a faster solution algorithm exploiting this property is proposed. Experimental results assess the practical performance of the proposed scheme. Then we present the optimal design of an improved modified multiple-description scalar quantizer (MMDSQ). The improvement is achieved by optimizing all the scalar quantizers. %are optimized under the assumption that all the central and side quantizers have contiguous codecells. The optimization is based on solving the single-source MWP problem in a coupled quantizer graph and the all-pairs MWP problem in a WDAG. Another variant design with the same optimization but enhanced with a better decoding process is also presented to decrease the gap to theoretical bounds. Both designs for the second problem have close or even better performances than the literature as shown in experiments. / Thesis / Master of Applied Science (MASc)

Following recent theoretical works on successive Wyner-Ziv coding, we propose a practical layered Wyner-Ziv video coder using the DCT, nested scalar quantiza- tion, and irregular LDPC code based Slepian-Wolf coding (or lossless source coding with side information at the decoder). Our main novelty is to use the base layer of a standard scalable video coder (e.g., MPEG-4/H.26L FGS or H.263+) as the decoder side information and perform layered Wyner-Ziv coding for quality enhance- ment. Similar to FGS coding, there is no performance di®erence between layered and monolithic Wyner-Ziv coding when the enhancement bitstream is generated in our proposed coder. Using an H.26L coded version as the base layer, experiments indicate that Wyner-Ziv coding gives slightly worse performance than FGS coding when the channel (for both the base and enhancement layers) is noiseless. However, when the channel is noisy, extensive simulations of video transmission over wireless networks conforming to the CDMA2000 1X standard show that H.26L base layer coding plus Wyner-Ziv enhancement layer coding are more robust against channel errors than H.26L FGS coding. These results demonstrate that layered Wyner-Ziv video coding is a promising new technique for video streaming over wireless networks. For scalable video transmission over the Internet and 3G wireless networks, we propose a system for receiver-driven layered multicast based on layered Wyner-Ziv video coding and digital fountain coding. Digital fountain codes are near-capacity erasure codes that are ideally suited for multicast applications because of their rate- less property. By combining an error-resilient Wyner-Ziv video coder and rateless fountain codes, our system allows reliable multicast of high-quality video to an arbi- trary number of heterogeneous receivers without the requirement of feedback chan- nels. Extending this work on separate source-channel coding, we consider distributed joint source-channel coding by using a single channel code for both video compression (via Slepian-Wolf coding) and packet loss protection. We choose Raptor codes - the best approximation to a digital fountain - and address in detail both encoder and de- coder designs. Simulation results show that, compared to one separate design using Slepian-Wolf compression plus erasure protection and another based on FGS coding plus erasure protection, the proposed joint design provides better video quality at the same number of transmitted packets.

Quantization of multimodal vector data in Realtime Interactive Communication Networks (RICNs) associated with application areas such as speech, video, audio, and haptic signals introduces a set of unique challenges. In particular, achieving the necessary distortion performance with minimum rate while maintaining low end-to-end delay and handling packet losses is of paramount importance. This dissertation presents vector quantization schemes which aim to satisfy these important requirements based on two source coding paradigms; 1) Predictive coding 2) Distributed source coding. Gaussian Mixture Models (GMMs) can be used to model any probability density function (pdf) with an arbitrarily small error given a sufficient number of mixture components. Hence, Gaussian Mixture Models can be effectively used to model the underlying pdfs of a variety of data in RICN applications. In this dissertation, first we present Gaussian Mixture Models Kalman predictive coding, which uses transform domain predictive GMM quantization techniques with Kalman filtering principles. In particular, we show how suitable modeling of quantization noise leads to a signal-adaptive GMM Kalman predictive coder that provides improved coding performance. Moreover, we demonstrate how running a GMM Kalman predictive coder to convergence can be used to design a stationary GMM Kalman predictive coding system which provides improved coding of GMM vector data but now with only a modest increase in run-time complexity over the baseline. Next, we address the issues of packet loss in the networks using GMM Kalman predictive coding principles. In particular, we show how an initial GMM Kalman predictive coder can be utilized to obtain a robust GMM predictive coder specifically designed to operate in packet loss. We demonstrate how one can define sets of encoding and decoding modes, and design special Kalman encoding and decoding gains for each mode. With this framework, GMM predictive coding design can be viewed as determining the special Kalman gains that minimize the expected mean squared error at the decoder in packet loss conditions. Finally, we present analytical techniques for modeling, analyzing and designing Wyner-Ziv(WZ) quantizers for Distributed Source Coding for jointly Gaussian vector data with imperfect side information. In most of the DSC implementations, the side information is not explicitly available in the decoder. Thus, almost all of the practical implementations obtain the side information from the previously decoded frames. Due to model imperfections, packet losses, previous decoding errors, and quantization noise, the available side information is usually noisy. However, the design of Wyner-Ziv quantizers for imperfect side information has not been widely addressed in the DSC literature. The analytical techniques presented in this dissertation explicitly assume the existence of imperfect side information in the decoder. Furthermore, we demonstrate how the design problem for vector data can be decomposed into independent scalar design subproblems. Then, we present the analytical techniques to compute the optimum step size and bit allocation for each scalar quantizer such that the decoder's expected vector Mean Squared Error(MSE) is minimized. The simulation results verify that the predicted MSE based on the presented analytical techniques closely follow the simulation results.

No description available.

Driven by a host of emerging applications (e.g., sensor networks and wireless video), distributed source coding (i.e., Slepian-Wolf coding, Wyner-Ziv coding and various other forms of multiterminal source coding), has recently become a very active research area. This dissertation focuses on multiterminal (MT) source coding problem, and consists of three parts. The first part studies the sum-rate loss of an important special case of quadratic Gaussian multi-terminal source coding, where all sources are positively symmetric and all target distortions are equal. We first give the minimum sum-rate for joint encoding of Gaussian sources in the symmetric case, and then show that the supremum of the sum-rate loss due to distributed encoding in this case is 1 2 log2 5 4 = 0:161 b/s when L = 2 and increases in the order of º L 2 log2 e b/s as the number of terminals L goes to infinity. The supremum sum-rate loss of 0:161 b/s in the symmetric case equals to that in general quadratic Gaussian two-terminal source coding without the symmetric assumption. It is conjectured that this equality holds for any number of terminals. In the second part, we present two practical MT coding schemes under the framework of Slepian-Wolf coded quantization (SWCQ) for both direct and indirect MT problems. The first, asymmetric SWCQ scheme relies on quantization and Wyner-Ziv coding, and it is implemented via source splitting to achieve any point on the sum-rate bound. In the second, conceptually simpler scheme, symmetric SWCQ, the two quantized sources are compressed using symmetric Slepian-Wolf coding via a channel code partitioning technique that is capable of achieving any point on the Slepian-Wolf sum-rate bound. Our practical designs employ trellis-coded quantization and turbo/LDPC codes for both asymmetric and symmetric Slepian-Wolf coding. Simulation results show a gap of only 0.139-0.194 bit per sample away from the sum-rate bound for both direct and indirect MT coding problems. The third part applies the above two MT coding schemes to two practical sources, i.e., stereo video sequences to save the sum rate over independent coding of both sequences. Experiments with both schemes on stereo video sequences using H.264, LDPC codes for Slepian-Wolf coding of the motion vectors, and scalar quantization in conjunction with LDPC codes for Wyner-Ziv coding of the residual coefficients give slightly smaller sum rate than separate H.264 coding of both sequences at the same video quality.