Random network error correction codes

Network Communications has been established on the principle of routing, in which received packets at intermediate nodes are replicated and forwarded to the outgoing channels. This scheme has been well accepted primarily for its simplicity in implementation on the networks. However, the vast development and availability of advanced microprocessors has given the ability to process and re-encode the received information at the intermediate nodes of the network. In that respect Network Coding studies the design and analysis of codes for networks. The primary benefits of network coding over the routing are it's increased throughput and the error correction capability. However, the design of network codes that achieves the network capacity and also the error correction capability relies on the knowledge of the network topology. While these predesigned network codes posses all of these desired properties, the centralized nature of these codes makes them highly intolerant to network changes. And hence, arbitrary network topology and highly dynamic traffics makes it impossible to use these predesigned codes. Under these circumstances decentralized codes presents a more viable option. The main decentralized network coding approach, which is the topic of this thesis is random coding. While random coding provides a decentralized coding operation of network, it may not necessarily achieve the best possible performance of a code. This makes the analysis of random coding vital both theoretically and also for its applications. This thesis mainly provides a theoretical basis for random coding and its error correction capabilities through the analysis of the failure probability of random linear network codes. First we provide a general upper bound on the failure probability of random linear network codes that applies to all single source multi-cast transmissions over acyclic networks as long as the transmission is feasible (i.e. source rate is at most the minimum cut capacity). Then we study the limiting behavior of Random Linear Network Codes as the finite field size F goes to infinity. The study of limiting behavior of Random network codes has lead us to a new tight bound for the failure probability of random network codes with redundancy. Finally the error correction capability of random linear network codes has been analyzed, the primary tool in facilitating the study of error correction capability is the bounds we have derived on the failure probability of random linear network codes. We give a definition of minimum distance of a network error correction code which plays exactly the same role as it does in classical coding theory. As expected the minimum distance of the random network code is a random variable which takes non negative integer values that satisfies the Singleton bound. The error correction capability of random network error correction codes has been presented by giving a bound on the probability mass function on it's minimum distance. Moreover we defined the code degradation as the difference between the singleton bound and the actual minimum distance of the code. We have derived bounds on the required field size for the existence of network error corrections codes with a given maximum degradation which showed that the required field size for a network error correction code decays exponentially as a function of code degradation. This suggests that even a minor sacrifice in terms of a code degradation causes a significant reduction in the required field size for the existence of a network error correction code.