We consider communication over a noisy network under randomized linear network coding. Possible error mechanism include node- or link- failures, Byzantine behavior of nodes, or an over-estimate of the network min-cut. Building on the work of Kotter and Kschischang, we introduce a probabilistic model for errors. We compute the capacity of this channel and we define an error-correction scheme based on random sparse graphs and a low-complexity decoding algorithm. By optimizing over the code degree profile, we show that this construction achieves the channel capacity in complexity which is jointly quadratic in the number of coded information bits and sublogarithmic in the error probability.
@cite_12: The problem of error-control in a "noncoherent" random network coding channel is considered. 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 suitable coding metric on subspaces is defined, under which a minimum distance decoder achieves correct decoding if the dimension of the space V U is large enough. When the dimension of each codeword is restricted to a fixed integer, the code forms a subset of the vertices of the Grassmann graph. Sphere-packing, sphere-covering bounds and a Singleton bound are provided for such codes. A Reed-Solomon-like code construction is provided and decoding algorithm given.
Upon transmission of @math , a corrupted'' version @math of the codeword is received. Without loss of generality, we assume that @math is brought back into normal form @math by Gaussian elimination. In principle it might be that the received matrix cannot be brought in this form because its first @math columns have rank smaller than @math . However, within the probabilistic model which we discuss in the following, the rank deficiency is small with high probability and can be eliminated by a small perturbation. Following K "o tter and Kschischang @cite_12 , we model the net effect of the transmission- and the processing- noise'' as a low-rank perturbation of @math . More precisely, we assume that where @math is an @math matrix over @math of @math , @math . We call @math the weight of the error, and @math the normalized weight.