Network Error Correction, I: Basic Concepts and Upper Bounds

Error correction in existing point-to-point communication networks is done on a link-by-link basis, which is referred to in this paper as classical error correction. Inspired by network coding, we introduce in this two-part paper a new paradigm called network error correction. The theory thus developed subsumes classical algebraic coding theory as a special case. In Part I, we discuss the basic concepts and prove the network generalizations of the Hamming bound and the Singleton bound in classical algebraic coding theory. By studying a few elementary examples, the relation between network error correction and classical error correction is investigated.

Keywords

Network coding, multicast, error correction, algebraic coding, Hamming bound, Singleton bound

2010 Mathematics Subject Classification

Primary 94B60. Secondary 94A05.

Full Text (PDF format)

Published 1 January 2006