Network coding theory via commutative algebra

摘要

The fundamental result of linear network coding asserts the existence of optimal 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. Adopting data units that belong to a discrete valuation ring (DVR), that is, a PID with a unique maximal ideal, much of the network coding theory extends to cyclic networks. Being a PID with the maximal ideal 0, a field can be regarded as a degenerated DVR. Thus the field-based theory becomes a degenerated version of the DVR-based theory. Meanwhile, convolutional network coding becomes the instance when the DVR consists of rational power series over a field. Besides the treatise in commutative algebra, the present paper also delves into the efficiency issue of code construction. Given a cyclic network, a quadratically large acyclic network is constructed so that every optimal code on the acyclic network subject to some straightforward restriction induces an optimal code on the given network. In this way, existing construction algorithms over acyclic networks can be adapted for cyclic networks as well.