Network Error Correcting Code On Zig-zag Network

Network coding gets lots of attention once it was raised, since the nature of it: encode considered on the dimension of time and space, it improves the throughput of network extremely and provides high capability of anti adversary nodes and malicious edges.Therefore, network coding, capability of error correction of which, is an interested and important work, also it is challenged.We explored the ability of network error correcting code, show its capability of anti adversary edges in a family of network called zig-zag network. The zig-zag network we concerned includes four nodes, representing source node, sink node and intermediate nodes respectively. Zig-zag network model could be treated as the smallest unit of general network. Particularly, our research focus on how feedback link influences the capability of error correction and provide a serials of results.Our contribution includes the following points:1. In a family of zig-zag network with limited feedback link, when there is in presence of z at most malicious edges, we found the achieved reliable rate of network is different from the previous results. And the new rate is better than the result from the Singleton bound, but is tighter than the previous result.2. Based on the new theorem on tighter bound, we proved its achieveavility of theorem. We designed an achieve strategy, including encode structure and decoding strategy. The challenge is, to achieve new upper bound, it cannot work with simple linear coding structure, and the decoding strategy requires involving the detection of intermediate nodes. It has shown since the complex of topology of network, an efficient of achieve strategy is much complicated and challenged. But the previous work on zig-zag network didn’t provide any results about those, the part is the most contribution of our work.3. The reason of new upper bound is better than the Singleton bound is that we discussed it by considering the character of the topology of network, exploring the potential of ability to increase the throughput of network. Therefore, it leads to another interesting problem: whether there exists a family of network which has the same character of the topology of network we concerned, but its upper bound is no more than Singleton bound. The further research we did confirms the conjecture.The intuition is that Singleton bound is a bound for general network without considering topology of network, for the whole kinds of network, even if there is network with some specific topology is better than Singleton bound, it should exist network with similar character topology is no more than it.4. At last, we consider the achievable strategy on general network. On this research director, there are four possible upper bounds depending on the properties of typology, however there was no concrete encoding structure and decoding strategy. Thus we analysis thoroughly the condition of topology of each possible upper bound,generalized our encoding structure and decoding strategy on them, which can reach any given bound. Therefore, it generalizes the results of our work, providing more universality.