Random Network Coding And Network Error Correction Coding

Network coding has been developed as a new approach for communication in net-works, allowing packets to be algebraically combined at internal nodes, rather thansimply routed or replicated. It has been shown that network coding provides gains interms of the achievable information rate region in modern communication networksand takes better advantage of the redundant resources in the network. Due to its gener-ality and its vast application potential, network coding has generated much interest ininformation theory, coding theory, networking, wireless communications, complexitytheory, cryptography, operations research, distributed storage and matroid theory.The main portion of this work is devoted to random linear network coding andlinear network error correction coding. In network coding, random linear network cod-ing has been proposed as an acceptable coding technique for the case that the networktopology cannot be utilized completely. Motivated by the fact that different networktopological information can be obtained for different practical applications, we studythe performance analysis of random linear network coding by analyzing some failureprobabilities depending on these different topological information of networks. We ob-tain some tight or asymptotically tight upper bounds on these failure probabilities andindicate the worst cases for these bounds, i.e., the networks meeting the upper boundswith equality. In addition, if the more topological information of the network is uti-lized, the better upper bounds are obtained. On the other hand, we also discuss thelower bounds on the failure probabilities. Moreover, in order to characterize the per-formance of random linear network coding more comprehensively and completely, wedefine the concept of average failure probability of random linear network coding andthen analyze this failure probability in detail. We also obtain several upper bounds onthe failure probabilities depending on different network topological information, whichare tight or asymptotically tight, too. Similarly, if the more topological information ofthe network is utilized, the better upper bounds are acquired.The second part of this work investigates linear network error correction coding. Following the research line using the extended global encoding kernels proposed byZhang [22], the refined Singleton bound of NEC can be proved more explicitly. More-over, we give a constructive proof of the attainability of this bound which indicates thatthe required field size for the existence of network maximum distance separable (MDS)codes can become smaller further. By this proof, an algorithm is proposed to constructgeneral linear network error correction codes including the linear network error cor-rection MDS codes. In addition, we study the error correction capability of randomlinear network error correction coding. Motivated partly by the performance analysisof random linear network coding, we evaluate the different failure probabilities definedin this research in order to analyze the performance of random linear network errorcorrection coding. Several upper bounds on these probabilities are obtained and theyshow that these probabilities will approach to zero as the size of the base field goes toinfinity. Using these upper bounds, we slightly improve on the probability mass func-tion of the minimum distance of random linear network error correction codes, as wellas the upper bound on the field size required for the existence of linear network errorcorrection codes with degradation at most d.In practical network communication, the source often transmits messages at sev-eral different information rates within a session. In view of both information transmis-sion and network error correction, linear network error correction MDS codes are ex-pected to be used for these different rates. For this purpose, a theoretical but practically-oriented solution is provided. We introduce the concept of a family of universal linearnetwork error correction MDS codes, that is, these linear network error correction MDScodes have the same local encoding kernels at all internal nodes, which solves this prob-lem efficiently and saves the storage space for each internal node, and resources andtime for the transmission on networks. We further specialize this theory and propose ascheme for efficient implementation.When both information transmission and error correction are under considera-tion simultaneously, four well-known classes of linear network codes in network cod-ing: linear multicast, linear broadcast, linear dispersion, and generic network codesare generalized to network error correction coding, i.e., linear network error correctionmulticast/broadcast/dispersion/generic codes. Furthermore, we propose the (weakly, strongly) extended Singleton bounds for these new classes of linear network error cor-rection codes, and define linear network error correction multicast/broadcast/dispersion/generic MDS codes satisfying the corresponding (weakly, strongly) extended Single-ton bounds with equality, respectively. We finally prove the existence of such codes indetail by algebraic methods and design the algorithms for constructing them.