A Characterization of the Capacity of Online (causal) Binary Channels
A Characterization of the Capacity of Online (causal) Binary Channels
复制标题
在线（因果）二元通道容量的表征
DOI：
10.1145/2746539.2746591
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Langberg
中科院分区：
文献类型：
--
作者：
Zitan Chen;S. Jaggi;M. Langberg
在二进制在线(或“因果”)信道编码模型中，发送方希望通过将码字x=(x1，...，xn)∈{0，1}n经由限制为至多Pn个破坏的信道逐位发送来将消息传送给接收方。在通信的第i个步骤，该信道基于到目前为止它的观点来决定是否破坏第i比特，即，它的决定仅取决于所传输的比特(x1，…，xi)，因此该信道是在线的。在这项工作中，我们研究了两种破坏模型的二进制在线信道的容量：比特翻转模型，其中信道可以翻转所传输码字的至多Pn比特，以及擦除模型，其中信道可以擦除所传输码字的至多Pn比特。具体地说，对于这两个误差模型，我们给出了作为p的函数的容量的完整表征。在线信道(在比特翻转和擦除情况下)已经看到最近的一些研究，它们给出了其容量的上界和下界。在这项工作中，我们提出并分析了一种编码方案，它改进了先前提出的下界，并与先前建议的上界相匹配，从而意味着紧特征。
In the binary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1,...,xn) ∈ {0,1}n bit by bit via a channel limited to at most pn corruptions. The channel is "online" in the sense that at the ith step of communication the channel decides whether to corrupt the ith bit or not based on its view so far, i.e., its decision depends only on the transmitted bits (x1,...,xi). This is in contrast to the classical adversarial channel in which the error is chosen by a channel that has full knowledge of the transmitted codeword x. In this work we study the capacity of binary online channels for two corruption models: the bit-flip model in which the channel may flip at most pn of the bits of the transmitted codeword, and the erasure model in which the channel may erase at most pn bits of the transmitted codeword. Specifically, for both error models we give a full characterization of the capacity as a function of p. The online channel (in both the bit-flip and erasure case) has seen a number of recent studies which present both upper and lower bounds on its capacity. In this work, we present and analyze a coding scheme that improves on the previously suggested lower bounds and matches the previously suggested upper bounds thus implying a tight characterization.