Adversarial error correction for network coding: Models and metrics

Abstract — The problem of error correction in both coherent and noncoherent network coding is considered under an adver-sarial model. For coherent network coding, where knowledge of the network topology and network code is assumed at the source and destination nodes, the error correction capability of an (outer) code is succinctly described by the rank metric; as a consequence, it is shown that universal network error correcting codes achieving the Singleton bound can be easily constructed and efficiently decoded. For noncoherent network coding, where knowledge of the network topology and network code is not assumed, the error correction capability of a (subspace) code is given exactly by a modified subspace metric, which is closely related to, but different than, the subspace metric of Kötter and Kschischang. In particular, in the case of a non-constant-dimension code, the decoder associated with the modified metric is shown to correct more errors then a minimum subspace distance decoder. I