Coding for Errors and Erasures in Random Network Coding

DOI10.1109/TIT.2008.926449MaRDI QIDQ3604797zbMATH OpenOpenAlexDBLPWikidataFDO

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0703061

Decoding (94B35) Other types of codes (94B60) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: The problem of error-control in random linear network coding is considered. A ``noncoherent or ``channel oblivious 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 modelled 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 c a p U

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 ``list-1 minimum distance decoding algorithm is provided.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Coding for Errors and Erasures in Random Network Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604797)