Ph.D Thesis

Ph.D StudentReani Avraham
SubjectCausal and Delay-Limited Coding in the Presence of
Side Information
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Neri Merhav


The classical source coding theorems and their converse counterparts provide fundamental limits which are usually asymptotic in the sense that they can be achieved by systems that introduce delay and/or require exponentially growing complexity. In many practical scenarios, however, delay is limited and complexity is, of course, constrained.

This research unifies and builds on two active research areas: the problem of delay - and/or complexity-constrained information theory, and that of coding in the presence of side information. Our research focuses on information theoretic questions that this unification gives rise to.

In our first work, we introduce new lower bounds on the distortion of scalar fixed-rate codes for lossy compression with side information available at the receiver. These bounds are derived by presenting the relevant random variables as a Markov chain and applying generalized data processing inequalities a la Ziv and Zakai. We show that by replacing the logarithmic function with other functions, in the data processing theorem we formulate, we obtain new lower bounds on the distortion of scalar coding with side information at the decoder. The usefulness of these results is demonstrated for uniform sources and the convex function Q(t)=t1-α , α>1. The bounds in this case are shown to be better than one can obtain from the Wyner-Ziv rate-distortion function.

In our second work, we consider a multi-user lossy source-coding problem for continuous alphabet sources. In this problem, two correlated sources are observed separately by two non-cooperative encoders which communicate with one decoder. In previous work, Ziv proposed a universal coding scheme, for the single-user setting, which uses uniform quantization with dither, followed by a lossless source encoder (entropy coder). In our research, we generalize Ziv's scheme to the multi-user setting. For this generalized scheme, upper bounds are derived for the redundancies, defined as the differences between the actual rates and the closest rate pair on the boundary of the rate region. It is shown that this scheme can achieve redundancies of no more than 0.754 bits per sample, for each user. These results are obtained without making any assumptions on the multi-user rate region which is unknown in general. As a direct consequence of the above, inner and outer bounds on the achievable region are obtained.

Yet another work deals with exploring universal source-coding schemes with dither. In previous works, the dither used in the quantization has been customarily assumed uniform. Our goal is to investigate the use of non-uniform dither. We express the rate and distortion for general dither and their differences relative to the uniform case. The idea is to derive the optimal quantizer design for a given family of source distributions.