Coding for Errors and Erasures in Random Network Coding
| dc.creator | Koetter, Ralf | |
| dc.creator | Kschischang, Frank | |
| dc.date | 2007-03-13 | |
| dc.date | 2008-03-25 | |
| dc.date.accessioned | 2026-07-07T09:28:09Z | |
| dc.date.available | 2026-07-07T09:28:09Z | |
| dc.description | 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 \cap 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. | |
| dc.description | This revised paper contains some minor changes and clarifications | |
| dc.identifier | https://arxiv.org/abs/cs/0703061 | |
| dc.identifier | http://arxiv.org/abs/cs/0703061 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/157350 | |
| dc.subject | Information Theory | |
| dc.subject | Networking and Internet Architecture | |
| dc.title | Coding for Errors and Erasures in Random Network Coding | |
| dc.type | text |