M.Sc Thesis

M.Sc StudentHof Eran
SubjectOn the Deterministic-Code Capacity of the Two-User Discrete
Memoryless Arbitrarily Varying General
Broadcast Channel
DepartmentDepartment of Electrical and Computer Engineering
Supervisor DR. Shraga Bross


An inner bound on the deterministic-code capacity region of the two-user discrete memoryless arbitrarily varying general broadcast channel (AVGBC) was characterized by Jahn, using the average probability of error criterion with deterministic codes and assuming that the common message capacity is nonzero. This region is obtained via the “elimination” technique due to Ahlswede, namely by concatenating short prefixes to the broadcast deterministic codes in order to inform the decoder which of the exponentially few broadcast deterministic codes is actually used. However, he did not indicate how one could decide whether the latter capacity is positive - i.e., he did not give a computable characterization of AVGBC’s for deciding whether such a prefix code exists.

In fact, Csisz´ar and Narayan’s result for the single user AVC establishes the missing part in Jahn’s characterization of an achievable region for the AVGBC. However, when the channel is symmetrizable the elimination technique is no longer applicable and therefore Csisz´ar and Narayan considered alternative ways of proving achievable rates for the singleuser symmetrizable AVC in the presence of a state constraint.

In this work we follow Csisz´ar and Narayan’s approach and consider alternative coding techniques that are not based on Ahlswede’s elimination technique. The various notions of symmetrizability for the two-user broadcast AVC are defined. Sufficient nonsymmetrizability condition that renders the common message capacity of the AVGBC positive is identified using an approach different from Jahn’s. The decoding rules we use, establish an achievable region under state and input constraints for the family of degraded message sets codes over the AVGBC. Similarly to the single user case, we show using a simple example of a deterministic AVGBC that under a state constraint, the deterministic code capacity region may not be empty even for a symmetrizable channel.