A Study Of Low Complexity Network Coding And Non-Shannon-Type Information Inequality

Network coding can increase multicast throughput on communication network. But the encoding and decoding complexity is high. This prevents its application on terminal devices with limited processing power.LT code is a sparse random linear fountain code with a low complexity decoding algorithm. This work emphasizes on reducing decoding complexity of receivers in multicast transmission while maintaining high throughput as in network coding, using characteristics and decoding algorithm of LT code.This work first generalizes the deduction process of distributed LT code used for multiple-access relay channel, and then extends the application of distributed LT code to relay channel with multiple sources and to simple networks. The performance and limitation of the generalized code is analyzed.For the complexity of designing encoding scheme for distributed LT code in multicast application, we introduce the condition of invariance of robust Soliton distribution for localized encoding scheme design, and then develop practical middle-node encoding scheme to implement this condition. With this encoding scheme and the decoding algorithm for LT code, this work applies LT code to multicast scenario, resulting in network LT code with low decoding complexity suited for multicast. The advantage and limitation of network LT code is surveyed by analysis and emulation. And then the code is applied to multicast transmission on wireless ad-hoc network.This work also presents the deduction process and the algorithm for systematically deriving non-Shannon-type information inequalities. New 4-variable non-Shannon-type information inequalities derived using this method are presented.