M.Sc Thesis

M.Sc StudentWinshtok Amir
SubjectSource and Channel Coding Problems in the Presence of
Arbitrarily Varying Side Information
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Yossef Steinberg
Full Thesis textFull thesis text - English Version


Channels that depend on random parameters appear frequently in practice. Such models describe fading channels, computer memory with defects and watermarking systems. When the states are known at the transmitter, two main scenarios can be considered: when it is known causally and noncausally. For the noncausal case, Gel'fand and Pinsker derived the capacity of a channel that depends on a state variable chosen with a known probability. However, not in every situation there is a complete knowledge of the law governing the channel. An extension of Gel'fand-Pinsker model to a case where the state variable is chosen in an arbitrarily varying manner was done by Ahlswede, based on his elimination technique. An extension of the Gel'fand-Pinsker result to a degraded broadcast channel was done by Steinberg.

In this work, we first extend Steinberg's result to the case where the state variable is chosen in an arbitrary manner. We then consider an extension of the Wyner-Ziv rate distortion problem. In the classical Wyner-Ziv model one assumes that the joint probability is known. In this work, we consider the case where the joint probability is selected in an arbitrary manner, such that the encoder knows the selected probability from the set.

We then consider a scheme where the compressed codeword is transmitted over an arbitrarily varying Gel'fand-Pinsker channel. We show that a separation principle holds for this scheme: there is no loss in optimality by first encoding the source with optimal encoder for the arbitrarily varying Wyner-Ziv source, and then encoding it with an optimal code for the arbitrarily varying Gel'fand-Pinsker channel. A byproduct of this result is that a separation principle holds also with respect to the operation of the jammer.

Finally, we consider an extension of a model of source coding with side information at the decoder. In this model, a joint probability is used to draw a pair of random variables. One is considered as the source, while the other considered as the side information. The aim in this model is to find all rate pairs that allow separate encodings of the source variable and the side information, such that the source variable can be perfectly represented at the decoder. We extend this model to a case where the joint probability is selected in an arbitrarily varying manner. We characterize the region of all achievable rate pairs, using a randomized encoder code with polynomially large common randomness between the encoders.