Ph.D Thesis

Ph.D StudentPereg Uziahu
SubjectSingle and Multi User Arbitrarily Varying Channels
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Yossef Steinberg
Full Thesis textFull thesis text - English Version


In practical communication systems, the statistics of the channels involved are not necessarily known in advance, and may even change over time, due to fading in wireless communication, cyber-physical warfare, etc. The arbitrarily varying channel (AVC) is an appropriate model to describe such a situation. In this work, we study four models.

First, we study the AVC with input and state constraints, when the encoder has state information in a causal or noncausal manner. For the causal setting, we develop lower and upper bounds on the random code capacity, and a deterministic code lower bound in the case of a message-averaged input constraint. In the case where a state constraint is imposed on the jammer, while the user is under no constraints, the random code bounds coincide, and the random code capacity is determined. Furthermore, for this scenario, a generalized non-symmetrizability condition is stated, under which the deterministic and random code capacities coincide. For the noncausal setting, we determine the random code capacity, and state a condition under which the deterministic and random code capacities coincide. We also consider several implications of our results on joint source-channel coding.

A second model considered in our work is the arbitrarily varying broadcast channel with degraded message sets and causal side information at the encoder. We establish inner and outer bounds on the random code and deterministic code capacity regions. Furthermore, we give conditions under which the bounds coincide, and the capacity region is determined. As an example, we consider the arbitrarily varying binary symmetric broadcast channel. We show that in some cases, the conditions hold and the capacity region is determined. Whereas, in other cases, there is a gap between the bounds. We discuss the game theoretic connection and show that the generalized minimax property does not necessarily hold for rate regions. That is, as opposed to the single-user case where the order of min and max can be reversed, the order of union and intersection of rate regions cannot necessarily be reversed.

The third model is the arbitrarily varying relay channel. We establish the cutset bound and the full/partial decode-forward bound. We further determine the random code capacity for special cases. Then, we consider conditions under which the deterministic code capacity is determined as well. Additional results are established for the arbitrarily varying Gaussian relay channel and the primitive arbitrarily varying relay channel. We show that Kim’s assertion (2007) ? that “the primitive relay channel captures most essential features and challenges of relaying, and thus serves as a good testbed for new relay coding techniques” ? is not necessarily true in the arbitrarily varying scenario.

Finally, we consider the arbitrarily varying multiple access channel. We determine the capacity region, both with and without constraints. Without constraints, the characterization due to Ahlswede and Cai (1999) is complete except for two cases, pointed out in the literature as an open problem. The missing piece is obtained as a special case of our results.