Communications in Information and Systems

Volume 6 (2006)

Number 1

Network Error Correction, I: Basic Concepts and Upper Bounds

Pages: 19 – 35

DOI: http://dx.doi.org/10.4310/CIS.2006.v6.n1.a2

Authors

Ning Cai

Ning Cai

Raymond W. Yeung

Raymond W. Yeung

Abstract

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)