Coding for Errors and Erasures in Random Network Coding
<|reference_start|>Coding for Errors and Erasures in Random Network Coding: 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.<|reference_end|>
@article{koetter2007coding,
    title={Coding for Errors and Erasures in Random Network Coding},
    author={Ralf Koetter and Frank Kschischang},
    journal={arXiv preprint arXiv:cs/0703061},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0703061},
    primaryClass={cs.IT cs.NI math.IT}
}