Coding for Errors and Erasures in Random Network Coding

By Ralf Koetter, Frank R. Kschischang. IEEE Transactions on Information Theory, 2007

1,168 citations recorded by the source corpus.

The problem of error-control in random linear network coding is considered. A ldquononcoherentrdquo or ldquochannel obliviousrdquo model is assumed where neither transmitter nor receiver is assumed to have knowledge of the channel transfer characteristic. Motivated by the property that linear network coding is vector-space preserving, information transmission is modeled as the injection into the network of a basis for a vector space V and the collection by the receiver of a basis for a vector space U. A metric on the projective geometry associated with the packet space is introduced, and it is shown that a minimum-distance decoder for this metric achieves correct decoding if the dimension of the space V capU is sufficiently large. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or, equivalently, a subset of the vertices of the corresponding Grassmann graph. Sphere-packing and sphere-covering bounds as well as a generalization of the singleton bound are provided for such codes. Finally, a Reed-Solomon-like code construction, related to Gabidulin's construction of maximum rank-distance codes, is described and a Sudan-style ldquolist-1rdquo minimum-distance decoding algorithm is provided.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/641b89d00a4e4cabbf6908f2ca2bfd7fb7f5d49b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

MRD Codes: Constructions and Connections (2019, methodology): “Subspace codes have applications in random network coding, due to the inﬂuential work of Koetter-Kchishang [54], [97].”
Resilient Network Coding in the Presence of Byzantine Adversaries (2008, positive): “The work closest in spirit to our work is that of Koetter and Kschischang [19], who also studied the presence of Byzantine adversaries in the distributed network coding setting.”
EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS (2013, methodology): “Finally, as explained earlier, q-Steiner systems produce optimal codes for error correction in networks [17, 34].”
Symbol-level network coding for wireless mesh networks (2008, background): “MIXIT’s network code also builds on recent advances in extending network coding to scenarios with errors and adversaries [7, 12].”
A Rank-Metric Approach to Error Control in Random Network Coding (2007, methodology): “In the course of setting up the problem, we also prove a result that can be seen as complementary to [ 9 ]; namely, we relate the performance guarantees of a subspace code with more concrete network parameters such as the maximum number of corrupting packets that can be injected in the network.”
Rank metric codes (2016, methodology): “This construction is first proposed in 2003 for linear authentication codes in [66] and rediscovered by Kschischang and Kötter in 2008 in [37].”