New results on network error correction: Capacities and upper bounds
Sukwon Kim, Tracey Ho, Michelle Effros, Salman Avestimehr · 2010
In this paper, we present new results on network error correction with unequal link capacities. We consider network error correction codes that can correct arbitrary errors occurring on up to z links. We find the capacity of a two-node network with multiple feedback links and show how feedback links can be used to increase the error correction capacity. We propose a new cut-set upper bound for general acyclic networks, and show its tightness for a family of four-node acyclic networks when each backward link has enough capacity. For a more general family of zig-zag networks, we present conditions under which our upper bound is tight. Finally, we propose an approach for high-probability network error correction with a causal adversary.