Network coding: Is zero error always possible?

Abstract

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.

Additional details