A bit of delay is sufficient and stochastic encoding is necessary to overcome online adversarial erasures
A bit of delay is sufficient and stochastic encoding is necessary to overcome online adversarial erasures
复制标题
一点延迟就足够了，并且需要随机编码来克服在线对抗性擦除
DOI：
10.1109/isit.2016.7541425
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Sarwate
中科院分区：
文献类型：
--
作者：
B. Dey;S. Jaggi;M. Langberg;A. Sarwate
我们考虑在恶意干扰对手（Calvin）存在下传达消息M的问题，后者可以删除任意设置的最多pn位，从n个传输位x =（x1，...，...，xn）中。当加尔文完全是因果关系时，这种通道的能力是，加尔文的决定是否删除XI是否取决于他的观察结果（x1，...，xi）[1]，[2]为1-- 2p。 （也许）令人惊讶的现象。 （并且独立于“当前位” XI）然后，当允许编码器随机时，容量会增加到1-p。设置，如果编码是确定性的（即，传输的代码字是消息m的确定性函数），那么由于错误的可能性消失的可能性，没有速率不对称大于1-2p，因此随机编码（在编码器上使用私有随机性）对于实现了实现1-p的容量对一位删除的加尔文。
We consider the problem of communicating a message m in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to pn bits, out of n transmitted bits X = (x1, ..., xn). The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit xi depends on his observations (x1, ..., xi) was recently characterized [1], [2] to be 1 - 2p. 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 xi depends only on (x1, ..., xi-1) (and is independent of the “current bit” xi) then the capacity increases to 1 - p 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 X is a deterministic function of the message m) then no rate asymptotically larger than 1 - 2p is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of 1- p against a one-bit-delayed Calvin.