Binary causal-adversary channels

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x 1 , ..., x n ) bit-by-bit over a communication channel. The adversarial jamme...

Full description

Saved in:
Bibliographic Details
Main Authors: Langberg, M., Jaggi, S., Dey, B.K.
Format: Conference Proceeding
Language:English
Subjects:
Codes
Communication channels
Computer interfaces
Computer science
Decoding
Entropy
Jamming
Laboratories
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x 1 , ..., x n ) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits x i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each bit x i the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on x j for j ¿ i. This is in contrast to the ¿classical¿ adversarial jammer which may base its decisions on its complete knowledge of x. We present a non-trivial upper bound on the amount of information that can be communicated. We show that the achievable rate can be asymptotically no greater than min{1 - H(p), (1 - 4p) + }. Here H(.) is the binary entropy function, and (1 - 4p) + equals 1 - 4p for p ¿ 0.25, and 0 otherwise.
ISSN:2157-8095
2157-8117
DOI:10.1109/ISIT.2009.5205859