Back to Search
Start Over
The Interplay of Causality and Myopia in Adversarial Channel Models
- Source :
- ISIT
- Publication Year :
- 2019
- Publisher :
- IEEE, 2019.
-
Abstract
- The difference in capacity formulae between worst-case and average-case channel noise models has been part of information theory since the early days of the field. This paper continues a line of work studying intermediate models in which the channel behavior can depend partially on the transmitted codeword. In particular, we consider a model in which a binary erasure channel (with maximum fraction of erasures p) is controlled by an adversary who can observe the transmitted codeword through an independent and memoryless erasure channel (with erasure probability q). Upper and lower bounds on the capacity are given for two models: a noncausal model, in which the adversary can choose their erasures based on the entire (partially observed) codeword, and a causal model, in which at each time the adversary must choose its erasures based on the current and previously observed codeword bits. The achievable rate for the noncausal case is larger than the Gilbert-Varshamov bound and for some parameter ranges exceeds the linear programming (LP) bound; we also provide a non-trivial outer bound on the capacity. For the causal case, we show the capacity is 1−2p+q for p ≥ q (prior work shows the capacity to equal 1−p when p
- Subjects :
- Discrete mathematics
0202 electrical engineering, electronic engineering, information engineering
Code (cryptography)
Code word
Erasure
020206 networking & telecommunications
02 engineering and technology
Information theory
Binary erasure channel
Encoder
Upper and lower bounds
Mathematics
Communication channel
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- 2019 IEEE International Symposium on Information Theory (ISIT)
- Accession number :
- edsair.doi...........5d761395856517e796675c06b148c32f