On Network Coding and Network-Error Correction
Prasad Krishnan · 2018
The paradigm of network coding was introduced as a means to conserve bandwidth (or equivalently increase throughput) in information flow networks. Network coding makes use of the fact that unlike physical commodities, information can be replicated and coded together at the nodes of the network. As a result, routing can be strictly suboptimal in many classes of information flow networks compared to network coding. Network-error correction is the art of designing network codes such that the sinks of the network will be able to decode the required information in the presence of errors in the edges of the network, known as network-errors. The network coding problem on a network with given sink demands can be considered to have the following three major subproblems, which naturally also extend to the study of network-error correcting codes, as they can be viewed as a special class of network codes (a) Existence of a network code that satisfies the demands (b) Efficient construction of such a network code (c) Minimum alphabet size for the existence of such a network code. This thesis primarily considers linear network coding and error correction and in- vestigates solutions to these issues for certain classes of network coding and error correction problems in acyclic networks. Our contributions are broadly summarised as follows. (1) We propose the use of convolutional codes for multicast network-error correc- tion. Depending upon the number of network-errors required to be corrected in the network, convolutional codes are designed at the source of the multicast network so that these errors can be corrected at the sinks of the networks as long as they are separated by certain number of time instants (for which we give a bound). In con- trast to block codes for network-error correction which require large field sizes, using convolutional codes enables the field size of the network code to be small. We discuss the performance of such networks under the BSC edge error model. (2)Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. In our work, we give an algorithm which, starting from a given network-error correcting code, can obtain an- other network code using a small field, with the same error correcting capability as the original code. The major step in our algorithm is to find a least degree irreducible poly- nomial which is coprime to another large degree polynomial. We utilize the algebraic properties of finite fields to implement this step so that it becomes much faster than the brute-force method. A recently proposed algorithm for network coding using small fields can be seen as a special case of our algorithm for the case of no network-errors. (3)Matroids are discrete mathematical objects which generalize the notion of linear independence of sets of vectors. It has been observed recently that matroids and network coding share a deep connection, and several…