The Interplay of Causality and Myopia in Adversarial Channel Models
The Interplay of Causality and Myopia in Adversarial Channel Models
复制标题
对抗性渠道模型中因果关系和近视的相互作用
DOI：
10.1109/isit.2019.8849568
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Carol Wang
中科院分区：
文献类型：
--
作者：
B. Dey;S. Jaggi;M. Langberg;A. Sarwate;Carol Wang
自该领域早期以来，最坏情况和平均情况信道噪声模型之间容量公式的差异一直是信息论的一部分。本文继续研究中间模型，其中信道行为可以部分依赖于传输的码字。特别是，我们考虑一种模型，其中二进制擦除通道（擦除的最大分数为 p）由对手控制，对手可以通过独立且无记忆的擦除通道（擦除概率为 q）观察传输的码字。容量的上限和下限针对两种模型给出：一种是非因果模型，其中对手可以根据整个（部分观察到的）码字来选择其擦除；另一种是因果模型，其中对手每次都必须根据当前和先前观察到的码字位来选择其擦除。非因果情况的可实现率大于 Gilbert-Varshamov 界限，并且某些参数范围超过线性规划 (LP) 界限；我们还提供了一个重要的容量外部界限。对于因果情况，我们显示，当 p ≥ q 时，容量为 1−2p+q（之前的工作表明，当 p<q 时，容量等于 1−p）。我们在这两种情况下的代码构造都是新颖的，要求编码器仔细地在其传输中添加“低权重相关噪声”。
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<q). Our code construction in both scenarios are novel, requiring the encoder to carefully add “low-weight correlated noise” to its transmission.