Research On Theory And Key Technique Of Fountain Codes

Fountain codes are sparse-graph codes for channels with erasures, such as the Internet, where files are transmitted in multiple small packets, each of which is either received without error or not received. Standard file transfer protocols simply chop a file into K packet-size pieces, and repeatedly transmit each packet which needs retransmitting. In contrast, fountain codes make packets using random functions from the whole file. The transmitter sprays packets at the receiver without any knowledge of which packet is received. Once the receiver has received any k packets, where k is just slightly greater than the original file size K, the whole file can be recovered.By utilizing Chaos theory and Bionic algorithms such as Ant colony algorithm, Genetic algorithm and Particle Swarm algorithm, the dissertation discusses several methods and models to improve the performance of fountain codes. On the other hand, the dissertation explores and proposes a novel class fountain codes based on Chinese Remainder theorem and Dayan method. The main contents and contributions of this dissertation are as follows:1. An implementation method based on Chaos Theory is proposed to solve the problem of recovering the degree and neighbor relations of encoding packets of fountain codes. Exploiting composite Logistic maps and their phase space character and using the initial values of the chaotic formula as public keys, the proposed method can synchronize the degree and neighbor relations without extra header-cost. The simulation results verify that the method had a good performance in the application of fountain codes.2. A Luby Transform (LT) Encoding algorithm based on Parabolic map by using chaotic position scrambling method is proposed. Firstly, chaotic sequences are produced by using Parabolic map and then transformed into uniform-like sequences. The degree distribution and data set of neighbors of LT codes are generated by using position scrambling algorithm which is more sensitive than traditional importance sampling method keeping the construction of theoretical distribution. Experimental results show that the algorithm has simpler construction, smaller header costs of the packets, better encryption effect than traditional importance sampling method.3. Degree distribution is the key index to evaluate the performance of fountain codes. In order to obtain a better degree distribution structure, Ant colony algorithm, Genetic algorithm and Particle Swarm algorithm are introduced into the designing process together with Monte Carlo simulation method and get a better solution of the degree distribution structure compared with traditional method by Robust Soliton Distribution formula. Simulation results verify that degree distribution designs of LT codes using Bionic algorithms are effective.4. A novel class of fountain codes implementation with encoding and decoding algorithms named Chinese Transform (CT) codes is proposed. Encoding process of CT codes can transform finite original symbols into theoretically infinite encoding symbols which are generated by integers uniformly selected from the set of primes, then they are enveloped into packets by chaotic position scrambling algorithm which are different from the former fountain codes based on Tanner graph and XOR operations. When enough packets are received from the packets, the original symbols can be recovered according to CT decoding algorithm with 100%probability. Simulations verify that the novel fountain codes implementation and construction are effective.