Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.

In this paper, we study the error correction capability of random linear network error correction codes (Z. Zhang, 2006). We derive bounds on the probability mass function of the minimum distance of a random network error correction code and the field size required for the existence of a network error correction code with a given degradation, which is the difference between the highest possible minimum distance in the Singleton bound and the minimum distance of the code. The main tool that we use to study these problems is an improved bound on the failure probability of random linear network codes that at one or more sinks, the source messages are not decodable. This problem was originally studied in T. Ho et al. (2006).

This paper summarizes our recent works on network error correction codes. We study basic properties of linear network error correction codes in the single source multicast case. We define the minimum distance of a network error correction code which plays the same role as it does in classical coding theory. We construct MDS codes and give sufficient conditions for its existence. We propose basic decoding algorithms and analyze their performance. We propose an improved upper bound for the failure probability of random network code and use it to analyze the performance of randomized network error correction codes [9], [10]. We study the possibility of decoding beyond error correction capability. We propose a hybrid network error correction coding systems. An extensive performance analysis of this coding system is reported in a separate paper.