2011
DocumentsDate added
A Practical Optimization Framework for the Degree Distribution in LT Codes
Abstract: Digital fountain is a new class of the forward error correction technology. One of the most important features is the characteristic called rateless, which allows encoders to generate codewords unlimitedly. As the first practical implementation of digital fountain, LT codes have been widely utilized in many areas, including multimedia streaming, long-distance communication, broadcasting systems, and distributed data storage. LT codes determine the coding structure according to a degree distribution and adopt belief propagation in decoding. Consequently, certain degree distributions are required to cooperate with belief propagation for good performance. With the proposal of LT codes, a degree distribution named robust soliton was presented. The capability of robust soliton distribution has been proved by theoretical analysis and asymptotically approaches optimal when the number of input symbols increases. However, most applications making use of LT codes have finite data lengths, and even some have a data length less than one thousand. Robust soliton distribution cannot guarantee satisfactory performance for relatively short data lengths. Hence, it is quite important to refine degree distributions for such cases. In this work, a practical framework which employs evolutionary algorithms is proposed to search for better degree distributions. Our experiments empirically prove that the proposed framework is robust and can customize degree distributions for different application requirements. Distributions found in the experiments are compared with a control group composed of robust soliton distributions. The performance measurements on different evaluation models are also presented to demonstrate the significant improvement of LT codes with the optimized degree distributions.
Abstract: Digital fountain is a new class of the forward error correction technology. One of the most important features is the characteristic called rateless, which allows encoders to generate codewords unlimitedly. As the first practical implementation of digital fountain, LT codes have been widely utilized in many areas, including multimedia streaming, long-distance communication, broadcasting systems, and distributed data storage. LT codes determine the coding structure according to a degree distribution and adopt belief propagation in decoding. Consequently, certain degree distributions are required to cooperate with belief propagation for good performance. With the proposal of LT codes, a degree distribution named robust soliton was presented. The capability of robust soliton distribution has been proved by theoretical analysis and asymptotically approaches optimal when the number of input symbols increases. However, most applications making use of LT codes have finite data lengths, and even some have a data length less than one thousand. Robust soliton distribution cannot guarantee satisfactory performance for relatively short data lengths. Hence, it is quite important to refine degree distributions for such cases. In this work, a practical framework which employs evolutionary algorithms is proposed to search for better degree distributions. Our experiments empirically prove that the proposed framework is robust and can customize degree distributions for different application requirements. Distributions found in the experiments are compared with a control group composed of robust soliton distributions. The performance measurements on different evaluation models are also presented to demonstrate the significant improvement of LT codes with the optimized degree distributions.
