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.
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.
@cite_12
2130539706
For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k] sup q , a simple counting argument shows that for any integer 0 0. We show that the discrete logarithm problem over F sub qh can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g - h] sub q with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over finite fields. The main tools to obtain these results are an interesting connection between the problem of list-decoding of Reed-Solomon code and the problem of discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors.