Research On Algorithms And Protocols Of Network Coding

Network coding is one of the most important breakthroughs in communication fields recently. The main idea of network coding is that in communication networks, intermediate nodes are allowed to not only store-forward but also process the incoming independent information flows. Network coding has been proved as an elegant and novel technique to improve network performance. Network coding is first proposed to enable multicast transmission to abtain the theoretical maximum transmission capacity, so as to achieve better network throughput than conventional routing. With further developing, network coding has been expanded to wireless network, P2P content distribution, distributed storage, network security, and other applications. There has been much investigation into various properties of network coding with a fixed rate. Network coding with variable-rate technology has important research significance since information flows are dynamic in the real network.Quantum communication provides a new way for transmitting message securely, and is one of the important parts in quantum information. Quantum communication has made a great deal of achievements both in theory and experiments and has broad prospects for development and application. Currently, quantum communication network is one of hot research topics in the international community. Therefore, improving the overall performance is essential when a quantum communication network becomes relized. However, the research of quantum network coding has just begun. Although the butterfly network is only a specific example of network coding, it represents the properties of networks with bottlenecks, so that its solution gives a trigger for a more general solution. In addition, quantum cloning, as an important element of quantum network coding technology, plays a great role in promoting the research on quantum network coding.The dissertation mainly focuses on the algorithms and protocols of netwok coding. The content of this dissertation relates to classical and quantum network coding, specifically including three aspects:algorithms for variable-rate linear network coding, protocols of quantum network coding over the butterfly network, and protocols for cloning an unknown quantum state with assistance.The principal contributions of the work presented in the paper are:1. Over a single-source acyclic classical communication network, four types of variable-rate linear network codes are investigated. On the one hand, by simple and clear proofs, it is found that variable-rate generic, dispersion and broadcast can be implemented without changing the local encoding kernels of the non-source nodes if the field is large enough. At the same time, it supplies efficient algorithms for variable-rate generic, dispersion and broadcast on the same network. These schemes have the advantage that each non-source node is required to store only one copy of the local encoding kernel within a session. On the other hand, it is shown by an example that variable-rate multicast may not always be implemented under the above condition. Moreover, applying this approach to a network with link failure, one can obtain similar results for variable-rate static network coding.Over a single-source cyclic classical communication network, four types of variable-rate convolutional network codes are investigated. It is found that variable-rate convolutional generic, dispersion and broadcast can be implemented without changing the local encoding kernels of the non-source nodes. However, it is also shown that variable-rate convolutional multicast may not always be implemented under the above condition.2. Classical network coding can save bandwidth. For a quantum communication network with bottleneck channels, efficient use of quantum network resources is also essential. One protocol is proposed to tranmit two 2-level quantum states crossly over the butterfly network with two non-maximally entangled qubit pairs shared only between two senders. It is shown that both of the receivers can reestablish the initial states with unit fidelity and a probability less than one. And one classical bit communication can be saved at the bottleneck channel. It means that the proposed protocol is more efficient than its without network coding. Moreover, this protocol is generalized to the case of transmitting two multipartite entangled states.3. Assisted-clone schemes are investigated to produce the perfect copy of an unknown state with a high probability without increasing the quantum non-local resources. A novel procotol is proposed to clone an unknown two-particle entangled state. The first stage of the protocol requires usual teleportation. In the second stage of the protocol, a novel set of mutually orthogonal basis vectors is constructed. With the assistance of the preparer through a projective measurement under this basis, the perfect copy of an original state can be produced. Comparing with the previous protocols which produce the unknown state and its orthogonal complement at the site of the sender, the proposed protocol generates the unknown state deterministically. On the other hand, another protocol is also put forword via non-maximal entanglement as the quantum channel. The faithful copy of an unknown state can be obtained with a certain probability.Using the similar method, we propose an deterministic assisted-clone protocol for an N-particle entangled state and an assisted-clone protocol for a three-particle GHZ class state with the successful probability 1/2, respectively.