Principle And Error Correction Analysis Of Network Coding

Network coding is first introduced by Rudolf Ahlswede et al. One important advantage of network coding based multicast is that the upper bound of a multicast, i.e. multicast capacity can be achieved. But using present multicast methods, multicast can not, often, achieve this upper bound. In addition, network coding bring other benefits, including resources consumption, load balancing, network manage and so on. So far, main researches are taken on multicast networks and main work of this paper is concentrated on multicast.Given an arbitrary multicast, there are two methods for network coding presently. The first one based on algebraic structure is brought forward by Ralf Koetter et al and it is an exponential time algorithm. The second one is introduced by Peter Sanders et al. and it is a polynomial time algorithm. This method compared to the first one not only has low complexity, but has another big advantage. Before transmitting information from source node to all receiver nodes, the paths from source to each receiver have been determined. So resources consumption is lower and network coding is easier to perform.For special kind of multicast network there may be more effective method. In this paper, for two kinds of multicast networks, effective methods of network coding are given respectively.In addition network coding based multicast can possess the ability of error correction. If there are several links, symbols out of which are different from input symbols, and the number is not exceed the ability of error correction, then all receivers can recover source information correctly.The main results of this paper are showed as follows:1. The principle of network coding is introduced; two kinds of network coding methods which are applicable to any multicasts are introduced in detail; network coding methods for non-multicast networks are depicted briefly.2. Two kinds of special multicast networks are analyzed and given quick network coding methods.3. Based on classical error-correcting codes, what is error-correcting codes based on network coding is introduced; upper bound and lower bound on the size of source alphabet are given after error-correcting codes based on network coding is further analyzed; the complexity of constructing parity-check matrix is analyzed and some technologies used to decrease computational Complexity are given.