On optimum conventional quantization for source coding with side information at the decoder

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 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 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 ≥ 0 is RˆWZ(D) = minX [I(X; Xˆ ) -- I(Y; Xˆ)], where the minimum is taken over all auxiliary random variables Xˆ such that Ed(X; Xˆ) ≤ D and Xˆ → X → Y is a Markov chain.; Further, we are interested in designing practical Wyner-Ziv coding. With the characterization at RˆWZ(D), this reduces to investigating 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 Xˆ that achieves RˆWZ( D) which provides guidelines for designing practical Wyner-Ziv coding.; In most cases, the random variable Xˆ that achieves RˆWZ(D) is different from the random variable 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 Xˆ = 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 X, Y, and 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.