Applications Of Matroid In Network Coding

The foundation of network coding theory is a significant breakthrough in thefield of communication and information theory in the early21st century. The key ideaof network coding technique is to allow an intermediate node to do linear or nonlinearencoding of the incoming information and then forward them. By integrating routingwith coding, network coding establishes a new mode of information processing andtransmission in the communication network. It has been proved that network codingtechniques have incomparable advantages in throughput, data security, robustness,universality, load equalization and low computational complexity and so on. Atpresent, network coding has become one of the hot research topics in the field ofnetwork and telecommunication. Many mathematical tools have been applied toresearch of the network coding theory, mainly including algebra, graph theory,matroid theory, combinatorial optimization etc.One fundamental problem in network coding is to understand the capacity regionand the classes of codes that achieve the capacity. Therefore, using the mathematicaltool—matroid to construct a valid network coding schemes and to study the networkcoding apacity region of multi-source multi-sink network, become an importantresearch topic in the field of network coding. This paper focuses on the research ofdetermining the boundary of the capacity region, revealing the relations betweenmatroid and linear network error correction code (LNEC). The main contributions arelisted as follows.1. According to the method of constructing matroidal network systematically,which is proposed by Dougherty et al., a matroidal network associated with matroidR8is constructed. An upper bound on coding capacity of this matroidal network is deducedfrom Ingleton inequality and Zhang-Yeung non-Shannon-type information inequalityrespectively.2. Connections between LNEC and representable matroids are presented withconcepts of the extended network and the extended global encoding kernel. Accordingto the essential characteristics of LNEC over a network, a different definition ofmatroidal error correction network is proposed. A more general case when the givenLNEC has different error correcting capacity at different sinks is considered.Afterwards, the conditions on the existence of linear network error correctionmulticast/broadcast/dispersion MDS codes on a matroidal error correction network are studied.3. A two-level group network coding method over the subgroup H Of theprojective general linear group PGL (2, p) is proposed. It is proved that the two-levelgroup network codes over H can be constructed by using linear codes over theadditive groupsZpandZp1as component. Finally, the effectiveness of our two-levelgroup network coding method is verified by a specific network coding scheme.