An optimized framework for degree distribution in LT codes based on power law

Abstract

LT codes are practical realization of digital fountain codes, which provides the concept of rateless coding. In this scheme, encoded symbols are generated infinitely from k information symbols. Decoder uses only (1+α)k number of encoded symbols to recover the original information. The degree distribution function in the LT codes helps to generate a random graph also referred as tanner graph. The artifact of tanner graph is responsible for computational complexity and overhead in the LT codes. Intuitively, a well designed degree distribution can be used for an efficient implementation of LT codes. The degree distribution function is studied as a function of power law, and LT codes are classified into two different categories: SFLT and RLT codes. Also, two different degree distributions are proposed and analyzed for SFLT codes which guarantee optimal performance in terms of computational complexity and overhead.

Keywords

fountain codes / degree distribution / overhead / computational complexity / power law

References

[1] ByersJ, LubyM, MitzenmacherM, RegeA. A digital fountain approach to reliable distribution of bulk data [C]. Proceeding of ACM SIGCOMM, 199855-67

[2] LubyM. LT Codes [C]. Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science. Vancouver, Canada, 2002271-280

[3] TarusH, BushJ, IrvineJ, DunlopJ. Exploiting redundancies to improve performance of LT decoding [C]. Proceeding of the 6th Annual Conference on Communication Networks and Services Research (CNSR 2008), 2008568-573

[4] HyytiäE, TirronenT, VirtamoJ. Optimizing the degree distribution of LT codes with an importance sampling approach [C]. 6th International Workshop on Rare Event Simulation, 200664-73

[5] ZhuH, ZhangG, LiG. A novel degree distribution algorithm of LT codes [C]. the 11th IEEE International Conference on Communication Technology, 2008

[6] SørensenJ H, PopovskiP, ØstergaardJ. Design and analysis of LT codes with decreasing ripple size [J]. IEEE Transactions on Communication, 2012, 60(11): 3191-3197

[7] ChenC M, ChenY P, ShenT C, ZaoJ K. Optimizing the degree distributions in LT codes by using the multi-objective evolutionary algorithm based on decomposition [C]. Proceeding of the IEEE Congress on Evolutionary Computation. Barcelona, 20103635-3642

[8] ChenC M, ChenY P, ShenT C, ZaoJ KA practical optimization frame for the degree distribution in LT codes [R], 2011

[9] BarabasiA L, DezsoZ, RavaszE, YookS H, OltvaiZ. Scale free and hierarchical structures in complex networks [C]. American Institute of Physics (AIP) Conference Proceedings. Granada, 20021-16

[10] NewmanM E J. Power laws pareto distributions and Zipf’s law [J]. Contemporary Physics, 2005, 46(5): 323-351

[11] LeiM, ZhaoO-g, HouZ-ting. Three vertex degree correlations of fixed act-size collaboration networks [J]. Journal of Central South University, 2011, 18(3): 830-833

[12] StockhammerT, JenkacH, MayerT, XuW. Soft decoding of LT codes for wireless broadcast [C]. Proceeding of IST Mobile. Dresden, Germany, 2005262-264

[13] UyedaF, XiaH, ChenA AEvaluation of a high performance erasure code implementation [R], 2004San DiegoUniversity of California