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.
Define the distance of two codewords @math and @math as @math and the minimum distance @math of the code @math as the minimum of the distances between all distinct pairs of codewords. The normalized minimum distance is @math . It is shown in @cite_12 that @math is a true distance metric; in particular it fulfills the triangle inequality. Therefore, given a code @math of minimum distance @math a simple bounded distance decoder can correct all errors of weight @math or less. A bounded distance decoder is an algorithm that, given a received word @math , decodes @math to the unique word within distance @math if such a word exists and declares an error otherwise. Bounded distance decoders are popular since a suitable algebraic structure on the code often ensures that bounded distance decoding can be accomplished with low complexity.