Network Error Correction, II: Lower Bounds

In Part I of this paper, we introduced the paradigm of network error correction as a generalization of classical link-by-link error correction. We also obtained the network generalizations of the Hamming bound and the Singleton bound in classical algebraic coding theory. In Part II, we prove the network generalization of the Gilbert-Varshamov bound and its enhancement. With the latter, we show that the tightness of the Singleton bound is preserved in the network setting. We also discuss the implication of the results in this paper.

Keywords

Network coding, multicast, error correction, algebraic coding, Gilbert bound, Varshamov bound, Singleton bound

2010 Mathematics Subject Classification

Primary 94B60. Secondary 94A05.

Full Text (PDF format)

Published 1 January 2006