A construction of matroidal error correcting networks

Abstract

Matroidal error correcting networks were recently introduced in [1] as a generalisation of the notion of matroidal networks introduced by Dougherty et al. to network-error correction. An acyclic network (with arbitrary sink demands) was shown to possess a scalar linear error correcting network code if and only if it is a matroidal error correcting network associated with a representable matroid. Therefore, networks with such scalar linear network-error correcting codes imply the existence of certain representable matroids that satisfy some special conditions, and vice versa. In this paper, we use this relationship between matroids and network-error correcting codes to present an algorithm which enables the construction of scalar linearly solvable multicast networks with a specified capability of network-error correction. Using this construction algorithm, a large class of hitherto unknown scalar linearly solvable networks with multicast network-error correcting codes is made available for theoretical use and practical implementation, with parameters such as number of information symbols, number of sinks, number of network coding nodes, error correcting capability, etc. being arbitrary but for computing power (for the execution of the algorithm).