Causal Erasure Channels
Causal Erasure Channels
复制标题
因果删除通道
DOI：
10.1137/1.9781611973402.133
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Adam D. Smith
中科院分区：
文献类型：
--
作者：
Raef Bassily;Adam D. Smith
我们考虑了二元因果对抗擦除信道的通信问题。这样的信道将n个输入比特映射到{0，1，n}中的n个输出符号，其中n表示擦除。如果对于每个i，通道基于输入1，...，i，然后观察比特i+1到n。这样的通道是p-有界的，如果它可以擦除在整个传输持续时间的输入位的最多一个p分数。因果通道为遵循基本物理限制但不可预测或高度可变的通道提供了一个自然模型。
对于给定的擦除率p，我们的目标是了解最佳速率（“容量”），在该速率下，随机化编码器/解码器可以可靠地跨所有因果p有界擦除信道进行传输。
在本文中，我们介绍了因果擦除模型，并提供了新的上限（不可能的结果）和下限（分析代码）的可达率。我们的边界分离的因果擦除设置可实现的速率从两个相关的模型：随机擦除通道（严格较弱）和完全对抗擦除通道（严格较强）。具体而言，我们显示：
·对于所有恒定擦除率p e（0，1），随机擦除和因果擦除之间的严格分离。特别地，我们证明了因果擦除信道的容量对于p ≥ 1/2为0（而对于随机擦除信道为非零）。
·对于p e（0，φ），因果擦除和完全对抗擦除之间的严格分离，其中φ a 0.348。
·对于p e [φ，1/2），我们展示了因果擦除的代码，其速率高于完全对抗信道的最佳已知构造。
我们的结果与纠正因果位翻转错误（与擦除相反）的现有结果形成鲜明对比[10，9，7，4，11]。对于我们提供的分离，位翻转模型的类似分离要么根本不知道，要么弱得多。
We consider the communication problem over binary causal adversarial erasure channels. Such a channel maps n input bits to n output symbols in {0, 1, ∧}, where ∧ denotes erasure. The channel is causal if, for every i, the channel adversarially decides whether to erase the ith bit of its input based on inputs 1, ..., i, before it observes bits i+1 to n. Such a channel is p-bounded if it can erase at most a p fraction of the input bits over the whole transmission duration. Causal channels provide a natural model for channels that obey basic physical restrictions but are otherwise unpredictable or highly variable.
For a given erasure rate p, our goal is to understand the optimal rate (the "capacity") at which a randomized encoder/decoder can transmit reliably across all causal p-bounded erasure channels.
In this paper, we introduce the causal erasure model and provide new upper bounds (impossibility results) and lower bounds (analyses of codes) on the achievable rate. Our bounds separate the achievable rate in the causal erasures setting from the rates achievable in two related models: random erasure channels (strictly weaker) and fully adversarial erasure channels (strictly stronger). Specifically, we show:
• A strict separation between random and causal erasures for all constant erasure rates p e (0, 1). In particular, we show that the capacity of causal erasure channels is 0 for p ≥ 1/2 (while it is nonzero for random erasures).
• A strict separation between causal and fully adversarial erasures for p e (0, φ) where φ a 0.348.
• For p e [φ, 1/2), we show codes for causal erasures that have higher rate than the best known constructions for fully adversarial channels.
Our results contrast with existing results on correcting causal bit-flip errors (as opposed to erasures) [10, 9, 7, 4, 11]. For the separations we provide, the analogous separations for bit-flip models are either not known at all or much weaker.