Binary causal-adversary channels
Binary causal-adversary channels
复制标题
二元因果-对手渠道
DOI：
10.1109/isit.2009.5205859
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
B. Dey
中科院分区：
文献类型：
--
作者：
M. Langberg;S. Jaggi;B. Dey
在这项工作中，我们考虑了在因果对抗干扰器存在的情况下的信息通信。在所研究的设置中，发送者希望通过发送码字x=(x1，…)将消息传送给接收者，xn)在通信信道上逐位传输。对抗性干扰器可以一次一个地查看发送的比特xi，并且可以改变它们中的p个分数。然而，干扰器的决定必须以在线或随机性的方式做出。也就是说，对于每个比特xi，干扰器关于是否破坏它(以及如何改变它)的决定必须仅取决于j≤i的xj。这与可能基于其对x的完全了解来做出决定的“经典”对抗干扰器形成对比。我们根据可传递的信息量给出了一个非平凡的上界。我们证明了可达速率可以渐近不大于min{1-H(P)，(1-4p)+}。这里H(.)是二进制熵函数，对于p≤为0.25时，(1-4p)+等于1-4p，否则为0。
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 = (x1, …, xn) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits xi 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 xi the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on xj 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.