Linear Network Coding: Theory and Algorithms

Abstract

Network coding is a new paradigm in data transport that combines coding with data propagation over a network. Theory of linear network coding (LNC) adopts a linear coding scheme at every node of the network and promises the optimal data transmission rate from the source to all receivers. Linearity enhances the theoretic elegance and engineering simplicity, which leads to wide applicability. This paper reviews the basic theory of LNC and construction algorithms for optimal linear network codes. Exemplifying applications are presented, including random LNC. The fundamental theorem of LNC applies to only acyclic networks, but practical applications actually ignore the acyclic restriction. The theoretic justification for this involves convolutional network coding (CNC), which, however, incurs the difficulty of precise synchronization. The problem can be alleviated when CNC is generalized by selecting an appropriate structure in commutative algebra for data units. This paper tries to present the necessary algebraic concepts as much as possible in engineering language.