UC San Diego

As connected devices play an ever-growing role in our society, there is a subsequent need for advances in multi-user communication systems. In a network, senders and receivers are connected via a series of intermediate users who share information represented as sequences of bits or elements of some other finite alphabet. By allowing users to transmit functions of their inputs, as opposed to simply relaying received data, the information throughput of a network can be increased. Network codes in which these functions are linear are sub-optimal in general but are of practical interest due to their mathematical tractability and low implementation complexity. The study of linear network coding has primarily been limited to finite field alphabets. In this work, we consider linear network codes over more general algebraically-structured alphabets, namely finite rings. We contrast linear network codes over finite fields, commutative rings, and non-commutative rings, and we discuss cases where non-linear codes attain higher information rates than even very general linear codes. Our results show that finite fields are, in some sense, the best ring alphabets for linear network coding, but in certain instances, it may be advantageous to use linear coding over some other ring alphabet of the same size. Specifically, we prove results related to:

(i) network solvability: whether or not a network’s receivers can obtain their desired information using codes over a given alphabet. We characterize the commutative rings for which there exists a network that is linearly solvable over the ring but not over any other commutative ring of the same size. We show that these rings are, in some sense, the best commutative rings of a given size for linear network coding. We then present an infinite class of networks that are linearly solvable over certain non-commutative rings but not over any commutative rings. We also prove that vector linear codes over finite fields minimize the alphabet size needed for linear solvability, which is desirable from an implementation complexity standpoint.

(ii) network capacity: how much information per channel use can be sent to the network’s receivers in the limit of large block sizes for transmission. We show that the linear coding capacity of a given network cannot be increased by looking beyond finite fields to more general rings.