Network Coding Theory Based on Commutative Algebra and Matroids.

摘要

The fundamental result of linear network coding asserts the existence of optimal linear network codes over acyclic networks when the symbol field is sufficiently large. The restriction to just acyclic networks turns out to stem from the customary algebraic structure of data symbols as a finite field.;The first part of this thesis algebraically structures the ensemble of data units as a principal ideal domain (PID) instead of a finite field. Fundamental theory of linear algebra deals with vectors over a PID and leads to a theoretic generalization of the basic concepts of linear network coding from acyclic to cyclic networks. As a prerequisite for causal data propagation around a cycle via a PID-based network code, the code must be normal such that the data unit carried on every channel can be unambiguously identified. Moreover, in order to break the deadlock in cyclic transmission, the PID of data units is further restricted to be a discrete valuation ring (DVR), which possesses a unique maximal ideal.;The second part connects PID-based network coding with matroid theory, an abstract theory of dependence. Over a network, a network matroid is defined on the edge set via the independence structure of edge-disjoint paths. Meanwhile, the linear independence among coding vectors of a normal code naturally induces a matroid on the edge set. Every independent set in the matroid so induced is also independent in the network matroid. Moreover, the two matroids coincide with each other if and only if the normal code is a generic one. This shows the optimality of generic codes in terms of linear independence. On the other hand, when the network is acyclic, every representation for the network matroid forms a generic code.;The third part delves into the efficiency issue of code construction. Given a cyclic network, a quadratically large acyclic network is established by de-cycling such that every optimal code on the de-cycled network subject to some straightforward restriction directly induces an optimal code on the cyclic one. In this way, existing construction algorithms for optimal codes on acyclic networks can be adapted to cyclic networks as well.