Research On Technology Of Fountain Codes

Digital fountain codes are a class of rateless erasure codes, the number of encoded symbols that can be generated from the original data is potentially limitless. Furthermore, encoded symbols can be generated on the fly, as few or as many as needed. Thus, no matter what the loss model is on the erasure channel, encoded symbols can be generated as needed and sent over the erasure channel until a sufficient number have arrived at the decoder in order to recover the data, with no need for retransmission. The application of digital fountain codes on reliable distribution, multi-source downloads and data storage has been paid much attention to currently. Besides, this technology can also be used in the network system like broadcasting and wireless network. As a kind of codes that are near optimal with respect to any erasure channel, the fountain codes have drawn increasing research efforts not only in theory, but also in engineering.This thesis is mainly on the two realizations of fountain codes: the LT(Luby Transform) codes and the Raptor codes and pays more effort on the LT codes. In the LT codes, the key factor that affects the decoding performance is degree distribution. A good degree distribution can make the decoder use as few encoded symbols as possible to recover the data. At the beginning of this thesis, the All-At-Once distribution, the Ideal Soliton distribution and the Robust Soliton distribution are firstly discussed. Then the whole process of encoding and decoding is simulated, using Message Passing(MP) as decoding algorithm. Due to the Raptor codes is just the extension of LT codes with linear time encoding and decoding,this thesis uses LDPC as pre-coding method and compares the decoding efficiency between Raptor codes and LT codes, proving that Raptor codes with pre-coding show better performance. To make it easy to compare, all decoding algorithm in this thesis is MP algorithm. Through simulation, the decoding performance of the LT codes using different degree distribution are compared with in this thesis respect to the mean value, the max value, the standard deviation and the CDF(Cumulative Distribution Function) and the conclusion that among the mentioned three degree distribution, the Robust Soliton distribution performs best has been proved. Later an improved encode method is given, making the decoder more likely to recover the data by receiving a little more one-degree encoded symbol. Tests in ideal channel without noise, in AWGN channel of different SNR and in Rayleigh channel all show that the LT codes with improved algorithm perform better than that with the Robust Soliton distribution.