On Network Coding and NetworkError Correction
Abstract
The paradigm of network coding was introduced as a means to conserve bandwidth (or equivalently increase throughput) in information ﬂow 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 ﬂow networks compared to network coding. Networkerror 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 networkerrors. 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 networkerror correcting codes, as they can be viewed as a special class of network codes (a) Existence of a network code that satisﬁes the demands (b) Eﬃcient 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 networkerror correc tion. Depending upon the number of networkerrors 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 networkerror correction which require large ﬁeld sizes, using convolutional codes enables the ﬁeld 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 networkerror correcting codes require a rather large ﬁeld 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 networkerror correcting code, can obtain an other network code using a small ﬁeld, with the same error correcting capability as the original code. The major step in our algorithm is to ﬁnd a least degree irreducible poly nomial which is coprime to another large degree polynomial. We utilize the algebraic properties of ﬁnite ﬁelds to implement this step so that it becomes much faster than the bruteforce method. A recently proposed algorithm for network coding using small ﬁelds can be seen as a special case of our algorithm for the case of no networkerrors.
(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 important results of network coding has been obtained using these connections from matroid theory. In our work, we establish that matroids with certain special properties correspond to networks with error detecting and correcting properties. We call such networks as matroidal error detecting (or equivalently, correcting) networks. We show that networks have scalar linear networkerror detecting (or correcting) codes if and only if there are associated with representable matroids with some special properties. We also use these ideas to construct matroidal error correcting networks along with their associated matroids. In the case of representable matroids, these algorithms give rise to scalar linear network error correcting codes on such networks. Finally we also show that linear network coding is not suﬃcient for the general networkerror detection (correction) problem with arbitrary demands.
(4)Problems related to network coding for acyclic, instantaneous networks have been extensively dealt with in the past. In contrast, not much attention has been paid to networks with delays. In our work, we elaborate on the existence, construction and minimum ﬁeld size issues of network codes for networks with integer delays. We show that the delays associated with the edges of the network cannot be ignored, and in fact turn out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the network coding problem considered. In the process, we also show multicast network codes which involve only delaying the symbols arriving at the nodes of the networks and coding the delayed symbols over a binary ﬁeld, thereby making coding operations at the nodes less complex.
(5) In the usual network coding framework, for a given set of network demands over an arbitrary acyclic network with integer delays assumed for the links, the out put symbols at the sink nodes, at any given time instant, is a Fqlinear combination of the input symbols generated at diﬀerent time instants where Fq denotes the ﬁeld over which the network operates. Therefore the sinks have to use suﬃcient memory elements in order to decode simultaneously for the entire stream of demanded infor mation symbols. We propose a scheme using an νpoint ﬁniteﬁeld discrete fourier transform (DFT) which converts the output symbols at the sink nodes at any given time instant, into a Fqlinear combination of the input symbols generated during the same time instant without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into νinstantaneous networks (ν is suﬃciently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach.
Collections
Related items
Showing items related by title, author, creator and subject.

Functional Index Coding, Network Function Computation, and SumProduct Algorithm for Decoding Network Codes
Gupta, Anindya (20180110)Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes ... 
Coding Schemes For Distributed Subspace Computation, Distributed Storage And Local Correctability
Vadlamani, Lalitha (20170724)In this thesis, three problems have been considered and new coding schemes have been devised for each of them. The first is related to distributed function computation, the second to coding for distributed storage and the ... 
Classical Binary Codes And Subspace Codes in a Lattice Framework
Pai, Srikanth B (20171010)The classical binary error correcting codes, and subspace codes for error correction in random network coding are two different forms of error control coding. We identify common features between these two forms and study ...