无速率编码中度分布的研究和发展

doi:10.11959/j.issn.1000-0801.2022268

Abstract

Abstract:

As a kind of deletion coding technology, the rateless code reduces feedback retransmission and has the characteristics of flexible bit rate and simple compilation code, which has broad application prospects in many fields.As the basis of rateless code design, degree distribution has a crucial impact on the performance of the rateless code With the wide application of the rateless code, the design of degree distribution also needs to change with changes in scenarios and needs.Firstly, the development and application of the rateless code were discussed.Starting with several classical rateless codes and degree distributions, the current research and development of the degree distribution were summarized and analyzed from three perspectives of application scenarios, optimization targets and existing optimization methods.Finally, the development and application trend of rateless codes and degree distribution were discussed.

Key words: rateless code, fountain code, degree distribution, network coding, multipath

CLC Number:

TN911

Yue QIAO, Yusun FU, Muyun YUAN, Jinhui TANG. Research and development of degree distribution in the rateless code[J]. Telecommunications Science, 2022, 38(10): 1-19.

Figures/Tables 4

References 69

[1]	LUBY M G , . LT codes[C]// Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2002: 271-280.
[2]	SHOKROLLAHI A . Raptor codes[J]. IEEE Transactions on Information Theory, 2006,52(6): 2551-2567.
[3]	SHIRVANIMOGHADDAM M , LI Y H , VUCETIC B . Adaptive analog fountain for wireless channels[C]// Proceedings of 2013 IEEE Wireless Communications and Networking Conference. Piscataway:IEEE Press, 2013: 2783-2788.
[4]	YANG S H , YEUNG R W . Batched sparse codes[J]. IEEE Transactions on Information Theory, 2014,60(9): 5322-5346.
[5]	LáZARO F , LIVA G , BAUCH G . Inactivation decoding of LT and raptor codes:analysis and code design[J]. IEEE Transactions on Communications, 2017,65(10): 4114-4127.
[6]	徐大专, 许生凯, 华洁 ,等. 数字喷泉码度分布优化设计的最新研究进展[J]. 数据采集与处理, 2015,30(4): 733-746.
	XU D Z , XU S K , HUA J ,et al. Recent progress on optimization design of degree distributions in digital fountain codes[J]. Journal of Data Acquisition and Processing, 2015,30(4): 733-746.
[7]	MACKAY D J C . Fountain codes[J]. IEE Proceedings - Communications, 2005,152(6): 1062.
[8]	黄靖轩, 费泽松, 李欢 . 无速率编码及其应用综述[J]. 无线电通信技术, 2020,46(1): 44-54.
	HUANG J X , FEI Z S , LI H . Overview of rateless codes and their applications[J]. Radio Communications Technology, 2020,46(1): 44-54.
[9]	LUBY M G , MITZENMACHER M , SHOKROLLAHI M A . Analysis of random processes via AND-OR tree evaluation[C]// Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms.[S.l.:s.n.], 1998.
[10]	ETESAMI O , SHOKROLLAHI A . Raptor codes on binary memoryless symmetric channels[J]. IEEE Transactions on Information Theory, 2006,52(5): 2033-2051.
[11]	TANNER R . A recursive approach to low complexity codes[J]. IEEE Transactions on Information Theory, 1981,27(5): 533-547.
[12]	3GPP. Multimedia broadcast/multicast service(MBMS); protocols and codecs:TS 26.346 V7.2.0[S]. 2006.
[13]	ETSI T S . IP datacast over DVB-H:content delivery protocols:102 472 v1.2.1[S]. 2006.
[14]	JEON S Y , AHN J H , LEE T J . Reliable broadcast using limited LT coding in wireless networks[J]. IEEE Communications Letters, 2016,20(6): 1187-1190.
[15]	BORKOTOKY S S , PURSLEY M B . Fountain-coded broadcast distribution in multiple-hop packet radio networks[J]. IEEE/ACM Transactions on Networking, 2019,27(1): 29-41.
[16]	PALMA V , MAMMI E , VEGNI A M ,et al. A fountain codes-based data dissemination technique in vehicular Ad-hoc networks[C]// Proceedings of 2011 11th International Conference on ITS Telecommunications. Piscataway:IEEE Press, 2011: 750-755.
[17]	ABDULLAH N F , DOUFEXI A , PIECHOCKI R J . Raptor codes-aided relaying for vehicular infotainment applications[J]. IET Communications, 2013,7(18): 2064-2073.
[18]	GAO Y M , XU X L , GUAN Y L ,et al. V2X content distribution based on batched network coding with distributed scheduling[J]. IEEE Access, 2017(6): 59449-59461.
[19]	ANGLANO C , GAETA R , GRANGETTO M . Exploiting rateless codes in cloud storage systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(5): 1313-1322.
[20]	LU H F , FOH C H , WEN Y G ,et al. Delay-optimized file retrieval under LT-based cloud storage[J]. IEEE Transactions on Cloud Computing, 2017,5(4): 656-666.
[21]	OKPOTSE T , YOUSEFI S . Systematic fountain codes for massive storage using the truncated Poisson distribution[J]. IEEE Transactions on Communications, 2019,67(2): 943-954.
[22]	段文雪, 胡铭, 周琼 ,等. 云计算系统可靠性研究综述[J]. 计算机研究与发展, 2020,57(1): 102-123.
	DUAN W X , HU M , ZHOU Q ,et al. Reliability in cloud computing system:a review[J]. Journal of Computer Research and Development, 2020,57(1): 102-123.
[23]	PUDUCHERI S , KLIEWER J , FUJA T E . The design and performance of distributed LT codes[J]. IEEE Transactions on Information Theory, 2007,53(10): 3740-3754.
[24]	HUSSAIN I , XIAO M , RASMUSSEN L K . Buffer-based distributed LT codes[J]. IEEE Transactions on Communications, 2014,62(11): 3725-3739.
[25]	SUN L , REN P Y , DU Q H ,et al. Fountain-coding aided strategy for secure cooperative transmission in industrial wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2016,12(1): 291-300.
[26]	YI B S , XIANG M , HUANG T Q ,et al. Data gathering with distributed rateless coding based on enhanced online fountain codes over wireless sensor networks[J]. AEU - International Journal of Electronics and Communications, 2018,92: 86-92.
[27]	YUE J , XIAO M , PANG Z B . Distributed fog computing based on batched sparse codes for industrial control[J]. IEEE Transactions on Industrial Informatics, 2018,14(10): 4683-4691.
[28]	SEVERINSON A , AMAT A G I , ROSNES E . Block-diagonal and LT codes for distributed computing with straggling servers[J]. IEEE Transactions on Communications, 2019,67(3): 1739-1753.
[29]	SANDELL M , RAZA U . Application layer coding for IoT:benefits,limitations,and implementation aspects[J]. IEEE Systems Journal, 2019,13(1): 554-561.
[30]	YUAN M Y , FU Y S , QIAO Y ,et al. Rateless codes for reliable and secure packet transmission in industrial control systems[C]// Proceedings of 2021 China Automation Congress (CAC). Piscataway:IEEE Press, 2021: 6376-6381.
[31]	AGHA K A , KADI N , STOJMENOVIC I . Fountain codes with XOR of encoded packets for broadcasting and source independent backbone in multi-hop networks using network coding[C]// Proceedings of IEEE 69th Vehicular Technology Conference. Piscataway:IEEE Press, 2009: 1-5.
[32]	SEJDINOVIC D , PIECHOCKI R J , DOUFEXI A . AND-OR tree analysis of distributed LT codes[C]// Proceedings of 2009 IEEE Information Theory Workshop on Networking and Information Theory. Piscataway:IEEE Press, 2009: 261-265.
[33]	ZENG M , CALDERBANK R , CUI S G . On design of rateless codes over dying binary erasure channel[J]. IEEE Transactions on Communications, 2012,60(4): 889-894.
[34]	TSAI P C , CHEN C M , CHEN Y P . A novel evaluation function for LT codes degree distribution optimization[C]// Proceedings of 2014 IEEE Congress on Evolutionary Computation. Piscataway:IEEE Press, 2014: 3030-3035.
[35]	NGUYEN T D , YANG L L , HANZO L . Systematic Luby transform codes and their soft decoding[C]// Proceedings of 2007 IEEE Workshop on Signal Processing Systems. Piscataway:IEEE Press, 2007: 67-72.
[36]	WIBERG N . Codes and decoding on general graphs[D]. Linkoping:Linkoping University, 1996.
[37]	PAUL I J L , RADHA S , RAJA J . Studies on the suitability of LT codes with modified degree distribution (MDD) for fading channels[C]// Proceedings of 2014 International Conference on Advances in Computing,Communications and Informatics (ICACCI). Piscataway:IEEE Press, 2014: 1764-1769.
[38]	LIAU A , YOUSEFI S , KIM I M . Binary soliton-like rateless coding for the Y-network[J]. IEEE Transactions on Communications, 2011,59(12): 3217-3222.
[39]	LIAU A , KIM I M , YOUSEFI S . Improved low-complexity soliton-like network coding for a resource-limited relay[J]. IEEE Transactions on Communications, 2013,61(8): 3327-3335.
[40]	SHAO H Q , XU D Z , ZHANG X F . Asymptotic analysis and optimization for generalized distributed fountain codes[J]. IEEE Communications Letters, 2013,17(5): 988-991.
[41]	CUI Y , WANG L , WANG X ,et al. FMTCP:a fountain code-based multipath transmission control protocol[J]. IEEE/ACM Transactions on Networking, 2015,23(2): 465-478.
[42]	LIMMANEE A , HENKEL W . A cooperative scheme for shaping degree distribution of LT-coded symbols in network coding multicast[C]// Proceedings of 2010 International ITG Conference on Source and Channel Coding (SCC). Piscataway:IEEE Press, 2010: 1-6.
[43]	THOMOS N , FROSSARD P . Degree distribution optimization in Raptor network coding[C]// Proceedings of 2011 IEEE International Symposium on Information Theory Proceedings. Piscataway:IEEE Press, 2011: 2736-2740.
[44]	NESSA A , KADOCH M . Joint network channel fountain schemes for machine-type communications over LTE-advanced[J]. IEEE Internet of Things Journal, 2016,3(3): 418-427.
[45]	HYYTIA E , TIRRONEN T , VIRTAMO J . Optimal degree distribution for LT codes with small message length[C]// Proceedings of IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2007: 2576-2580.
[46]	MAATOUK G , SHOKROLLAHI A . Analysis of the second moment of the LT decoder[C]// Proceedings of 2009 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2009: 2326-2330.
[47]	YEN K K , LIAO Y C , CHEN C L ,et al. Modified robust soliton distribution (MRSD) with improved ripple size for LT codes[J]. IEEE Communications Letters, 2013,17(5): 976-979.
[48]	戴新颖, 王建萍 . 基于输出可译集的LT码联合度分布优化[J]. 系统工程与电子技术, 2020,42(3): 727-732.
	DAI X Y , WANG J P . Optimization of combined degree distribution of LT codes based on output ripple size[J]. Systems Engineering and Electronics, 2020,42(3): 727-732.
[49]	郑志国, 侯登峰 . 基于可译集大小的 LT 码编码算法的改进[J]. 电视技术, 2011,35(5): 13-16.
	ZHENG Z G , HOU D F . Improvement of LT encoding algorithm based on ripple size[J]. Video Engineering, 2011,35(5): 13-16.
[50]	RENSEN J H S , POPOVSKI P , OSTERGAARD J . Design and analysis of LT codes with decreasing ripple size[J]. IEEE Transactions on Communications, 2012,60(11): 3191-3197.
[51]	YEN K K , LIAO Y C , CHANG H C . Design of LT code degree distribution with profiled output ripple size[C]// Proceedings of 2015 IEEE Workshop on Signal Processing Systems (SiPS). Piscataway:IEEE Press, 2015: 1-6.
[52]	雷维嘉, 张梦, 谢显中 . 基于度分布合并和可译集优化的 LT码度分布设计方案[J]. 电子学报, 2015,43(4): 800-805.
	LEI W J , ZHANG M , XIE X Z . A design scheme for LT codes degree distribution by combining degree distributions and optimizing ripple size[J]. Acta Electronica Sinica, 2015,43(4): 800-805.
[53]	ZHANG M , LEI W J , XIE X Z . Combined degree distribution:a simple method to design the degree distribution of fountain codes[C]// Proceedings of 2013 IEEE Third International Conference on Information Science and Technology. Piscataway:IEEE Press, 2013: 1089-1092.
[54]	任鹏, 相征 . LT 码中一种新的开关度分布[J]. 西安电子科技大学学报, 2015,42(5): 43-47.
	REN P , XIANG Z . New switch degree distribution for the LT code[J]. Journal of Xidian University, 2015,42(5): 43-47.
[55]	姚渭箐, 胡凡 . 基于IBED和仿生算法的LT码度分布设计[J]. 电子学报, 2019,47(2): 428-433.
	YAO W Q , HU F . The design of degree distribution for LT codes based on IBED and bionic algorithm[J]. Acta Electronica Sinica, 2019,47(2): 428-433.
[56]	YAO W Q , YI B S , HUANG T Q ,et al. Poisson robust soliton distribution for LT codes[J]. IEEE Communications Letters, 2016,20(8): 1499-1502.
[57]	龚赟, 王俊义 . 一种用于LT码的新型联合度分布设计方法[J]. 桂林电子科技大学学报, 2017,37(5): 355-360.
	GONG Y , WANG J Y . A design method of novel combined degree distribution for LT code[J]. Journal of Guilin University of Electronic Technology, 2017,37(5): 355-360.
[58]	敖珺, 卢亚军, 马春波 . 基于短码长的喷泉码度分布设计[J]. 计算机与数字工程, 2015,43(12): 2101-2105.
	AO J , LU Y J , MA C B . Fountain codes degree distribution design based on short code length[J]. Computer ＆ Digital Engineering, 2015,43(12): 2101-2105.
[59]	ZAO J K , HORNANSKY M , DIAO P L . Design of optimal short-length LT codes using evolution strategies[C]// Proceedings of 2012 IEEE Congress on Evolutionary Computation. Piscataway:IEEE Press, 2012: 1-9.
[60]	李杰 . 无线传输中短码长喷泉码的度分布优化算法[J]. 电讯技术, 2016,56(8): 900-905.
	LI J . A degree distribution optimization algorithm for small size fountain codes in wireless transmission[J]. Telecommunication Engineering, 2016,56(8): 900-905.
[61]	YUAN L , DENG K Y , LI H A . Design of finite-length precoded EWF codes for scalable video streaming[J]. Wireless Personal Communications, 2017,97(3): 4111-4128.
[62]	BEIMEL A , DOLEV S , SINGER N . RT oblivious erasure correcting[J]. IEEE/ACM Transactions on Networking, 2007,15(6): 1321-1332.
[63]	JIA D , FEI Z S , SHANGGUAN C L ,et al. LT codes with limited feedback[C]// Proceedings of 2014 IEEE International Conference on Computer and Information Technology. Piscataway:IEEE Press, 2014: 669-673.
[64]	HAGEDORN A , AGARWAL S , STAROBINSKI D ,et al. Rateless coding with feedback[C]// Proceedings of IEEE INFOCOM 2009. Piscataway:IEEE Press, 2009: 1791-1799.
[65]	AGARWAL S , HAGEDORN A , TRACHTENBERG A . Adaptive rateless coding under partial information[C]// Proceedings of 2008 Information Theory and Applications Workshop. Piscataway:IEEE Press, 2008: 5-11.
[66]	牛芳琳, 李宝明, 陈付亮 ,等. 一种改进的基于部分信息喷泉码度分布设计[J]. 电子学报, 2016,44(2): 295-300.
	NIU F L , LI B M , CHEN F L ,et al. The improved degree distribution for rateless code under partial information[J]. Acta Electronica Sinica, 2016,44(2): 295-300.
[67]	SAVCHENKO Y , LIU Y . Optimizing degree distributions of LT-based codes with deep reinforcement learning[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops. Piscataway:IEEE Press, 2019: 228-233.
[68]	HUANG L C , ZHANG H Z , LI R ,et al. AI coding:learning to construct error correction codes[J]. IEEE Transactions on Communications, 2020,68(1): 26-39.
[69]	宋鑫, 倪淑燕, 张喆 ,等. 面向不等差错保护的低误码平台LT编码算法[J]. 通信学报, 2022,43(6): 85-97.
	SONG X , NI S Y , ZHANG Z ,et al. Low error floor LT coding algorithm for unequal error protection[J]. Journal on Communications, 2022,43(6): 85-97.

Metrics

Recommended 0

No Suggested Reading articles found!

应用场景	具体应用	文献
广播通信	Raptor码及其改进方案在蜂窝移动通信中的多媒体广播与多播	[12]
	Raptor码及其改进方案在DVB-H中的应用	[13]
	有反馈的二次广播下LT码度分布设计	[14]
	无速率编码在多跳无线网络数据分发中的应用	[15]
汽车通信	LT码在车载自组织网络中的应用	[16]
	Raptor码在汽车通信场景中的应用	[17]
	BATS码在汽车通信数据分发中的应用	[18]
存储	LT码在云存储系统中的应用	[19]
	在基于LT码的存储系统中如何优化检索方式以降低时延	[20]
	LT码在分布式存储系统中的应用	[21]
	纠删码在存储系统容错中的应用	[22]
无线传感器	分布式LT码在无线传感器网络中的应用	[23]
	利用缓存存储部分接收符号参与编码，降低最大度值的限制	[24]
	无线传感器网络中基于无速率编码的安全协作传输	[25]
	OFC在无线传感器网络中用于数据收集	[26]
分布式计算	BATS码在分布式计算系统中的应用	[27]
	使用失活译码器的LT码在分布式计算系统中的应用	[28]
物联网	将喷泉码作为物联网中的应用层编码	[29]
	工业环境下有限码长对喷泉码的影响	[30]

Research and development of degree distribution in the rateless code

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 69

Related Articles 15

Metrics

Recommended 0

[1]	Shiheng WANG, Heng LIU, Lin TANG, Jinling SU, Ruiqi ZHANG. Analysis for rank distribution of BATS codes under time-variant channels [J]. Telecommunications Science, 2022, 38(5): 64-74.
[2]	Shufeng SHI, Youyang YU. Multi-access, wireless and wired convergence architecture evolution and traffic scheduling mechanism [J]. Telecommunications Science, 2022, 38(4): 146-155.
[3]	Yang LU,Donglei ZHANG,Tingting WANG. Anti-fading technology of near space communication based on quasi-constant envelope OFDM [J]. Telecommunications Science, 2019, 35(1): 113-120.
[4]	Xiaobin FU,Baohui ZHENG. Transmission characteristics of air-ground channel in aerial communication platform [J]. Telecommunications Science, 2018, 34(1): 27-33.
[5]	Pengfei SHAO,Yanwei ZHAO,Zhaoxi FANG. A hash-neighborhood-search-network-coding based opportunistic relay retransmission approach [J]. Telecommunications Science, 2016, 32(4): 9-16.
[6]	Pengfei Shao,Yanwei Zhao,Yaohui Wu,Xinwei Yao. An Improved Retransmission Approacb Based on Opportunistic Network Coding in Multicast Networks [J]. Telecommunications Science, 2015, 31(4): 98-105.
[7]	Dan Deng,Ming Zhao,Guizhou Jian. Secure Transmission Based on Antenna Selection for Network Coding System [J]. Telecommunications Science, 2015, 31(2): 69-74.
[8]	Wei Zhang,Linghua Zhang. Flow Allocation Algorithm Based on Potential Game in Multi-Source Multi-Hop Wireless Sensor Network [J]. Telecommunications Science, 2015, 31(2): 75-79.
[9]	Shaohua Zhao,Wei Chen,Bo Bai,Zhisheng Niu,Zhigang Cao. A Rateless Code Transmission Strategy Based on Real Time Service [J]. Telecommunications Science, 2013, 29(10): 58-64.
[10]	Wang Zhenchao,Liang Junjun,Wang Zhuyi and Li Huiya. Study on Echo Cancellation Technology of Multipath Channel [J]. Telecommunications Science, 2012, 28(5): 60-64.
[11]	Cheong Siotai,Pingyi Fan. A Novel Hybrid Asymmetric Mapping Scheme to Improve the Spectrum Efficiency for Fountain Codes [J]. Telecommunications Science, 2012, 28(3): 57-61.
[12]	Fatang Chen,Wang Teng. Study of Timing Synchronization Algorithms in TD-LTE System Under Multipath Channel [J]. Telecommunications Science, 2012, 28(2): 74-78.
[13]	Yang Ge,Minghai Xu,Huan Chi. Research on the Packet Reordering in Transport Virtualization [J]. Telecommunications Science, 2012, 28(10): 80-87.
[14]	Tao Yuan,Jiange Xie,Yuan Bao,Liang Yang. Improvement of Maximum Likelihood Decoding Algorithm in Complex Field Network Coding [J]. Telecommunications Science, 2011, 27(12): 44-47.
[15]	Li'an Guan,Binqiang Wang,Xuanyong Zhu. Path Selection Algorithm Based on Residual Bandwidth and Link Utilization Rate of Next Hop [J]. Telecommunications Science, 2010, 26(8): 30-34.