Abstract
We consider the problem of communicating a message in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to bits, out of transmitted bits . The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit depends on his observations was recently characterized to be . In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit depends only on (and is independent of the "current bit" ) then the capacity increases to when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword is a deterministic function of the message ) then no rate asymptotically larger than is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of against a one-bit-delayed Calvin.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.