Communications in Information and Systems
Volume 6 (2006)
Network Error Correction, II: Lower Bounds
Pages: 37 – 54
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.
Network coding; multicast; error correction; algebraic coding; Gilbert bound; Varshamov bound; Singleton bound
2010 Mathematics Subject Classification
Primary 94B60. Secondary 94A05.