IEEE Transactions on Information Theory · 2010 · 66 citations · 27 references
EngineeringCommunicationComputer ScienceComputer NetworksDigital CommunicationInformation TheoryChannel CodingCoding TheoryError Control CodingError-correcting CodesNetwork Information TheoryWireless Channel ModelingCoding-theoretic CommunicationError Control
This paper is motivated by the problem of error control in network coding when errors are introduced in a random fashion (rather than chosen by an adversary). An additive-multiplicative matrix channel is considered as a model for random network coding. The model assumes that <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> packets of length <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> are transmitted over the network, and up to <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</i> erroneous packets are randomly chosen and injected into the network. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of large field or matrix size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has decoding complexity <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> ) and a probability of error that decreases exponentially both in the packet length and in the field size in bits. Extensions of these results for coherent network coding are also presented.
27
Rudolf Ahlswede, Ning Cai, Shuo Li et al. · IEEE Transactions on Information Theory · 2000 · 7.9K citations
Sphere Packings, Lattices and Groups.
H. S. M. Coxeter, J. H. Conway, N. J. A. Sloane · American Mathematical Monthly · 1989 · 3.5K citations
Shuo Li, Raymond W. Yeung, Ning Cai · IEEE Transactions on Information Theory · 2003 · 3.5K citations
A Random Linear Network Coding Approach to Multicast
T. Ho, Muriel Médard, R. Koetter et al. · IEEE Transactions on Information Theory · 2006 · 2.6K citations
An algebraic approach to network coding
R. Koetter, Muriel Médard · IEEE/ACM Transactions on Networking · 2003 · 2.4K citations