The capacity of online (causal) q-ary error-erasure channels
The capacity of online (causal) q-ary error-erasure channels
复制标题
在线（因果）q 进制错误擦除通道的容量
DOI：
10.1109/isit.2016.7541432
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Langberg
中科院分区：
文献类型：
--
作者：
Zitan Chen;S. Jaggi;M. Langberg
在 q 元在线（因果）信道编码模型中，发送者希望通过发送码字 x = (x1,...,xn) ∈ {0, 1,... 来向接收者传达消息。 。 。 , q - 1}n 逐个符号通过通道限制至多 p*n 错误（符号更改）和 p*n 擦除。通道是“在线”（即“因果”）的，因为在通信的第 i 个步骤中，通道仅根据其对符号（x1，...，xi）的看法来决定是否破坏第 i 个符号。这与经典的对抗性通道形成对比，在经典的对抗性通道中，在完全了解发送的码字 x 的情况下选择损坏。在这项工作中，我们扩展了[1]-[4]中获得的结果（其中表征了二进制在线仅位翻转通道和单独的二进制在线仅擦除通道的容量）。我们在这里以两种重要的方式扩展了这些先前的结果。首先，我们获得一般 q（而不仅仅是 q = 2）的 q 进制在线通道的容量。其次，我们分析组合的错误擦除损坏模型（而不是单独研究它们）。对这一类更广泛的对称在线渠道的表征可以让我们更全面地了解因果关系对干扰对手的影响。本文中的扩展需要用于最佳代码设计和匹配信息论逆论证的新颖方法。
In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}n symbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1, . . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.