Network coding: Is zero error always possible?
Network coding: Is zero error always possible?
复制标题
网络编码：零错误总是可能的吗？
DOI：
10.1109/allerton.2011.6120342
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Effros
中科院分区：
文献类型：
--
作者：
M. Langberg;M. Effros
本文研究了网络编码实例中的零和ε误差容量。对于组播网络编码，众所周知，所有可以以任意小的错误概率发送的速率也可以以零错误概率发送；即ε误差组播容量区域和零误差组播容量区域是相同的。对于所有源都来自同一源节点的一般网络编码实例，Chan和Grant最近表明[ISIT 2010]， ε错误通信与零错误通信相比没有速率优势。我们首先重新审视同地来源的设置，在那里我们提出了Chan和Grant给出的另一种证明。虽然新的证明基于类似的核心思想，但我们的建设性策略是对先前论点的补充。然后，我们将我们的结果扩展到索引编码的设置，索引编码是一种特殊的、有代表性的网络编码形式，它封装了“带副信息的源编码”问题。最后，我们考虑“边缘去除”问题（最近由Jalali， Effros和Ho在[Allerton 2010]和[ITA 2011]中研究），旨在量化从给定网络中去除单个边缘相关的容量损失。利用我们对共定位源的证明，我们将一般网络编码实例中的“零与ε误差”问题与“边缘去除”问题联系起来。粗略地说，我们证明这两个问题是等价的。
In this work we study zero vs. ε-error capacity in network coding instances. For multicast network coding it is well known that all rates that can be delivered with arbitrarily small error probability can also be delivered with zero error probability; that is, the ε-error multicast capacity region and zero-error multicast capacity region are identical. For general network coding instances in which all sources originate at the same source node, Chan and Grant recently showed [ISIT 2010] that, again, ε-error communication has no rate advantage over zero-error communication. We start by revisiting the setting of co-located sources, where we present an alternative proof to that given by Chan and Grant. While the new proof is based on similar core ideas, our constructive strategy complements the previous argument. We then extend our results to the setting of index coding, which is a special and representative form of network coding that encapsulates the “source coding with side information” problem. Finally, we consider the “edge removal” problem (recently studied by Jalali, Effros, and Ho in [Allerton 2010] and [ITA 2011]) that aims to quantify the loss in capacity associated with removing a single edge from a given network. Using our proof for co-located sources, we tie the “zero vs. ε-error” problem in general network coding instances with the “edge removal” problem. Loosely speaking, we show that the two problem are equivalent.