Communications in Information and Systems

Volume 6 (2006)

Number 1

Network Error Correction, I: Basic Concepts and Upper Bounds

Pages: 19 – 35



Ning Cai

Ning Cai

Raymond W. Yeung

Raymond W. Yeung


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.


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

2010 Mathematics Subject Classification

Primary 94B60. Secondary 94A05.

Published 1 January 2006