Research and development of degree distribution in the rateless code

Yue QIAO; Yusun FU; Muyun YUAN; Jinhui TANG

doi:10.11959/j.issn.1000-0801.2022268

您当前的位置：

首页 >

文章列表页 >

Research and development of degree distribution in the rateless code

Review | 更新时间：2024-06-05

- Research and development of degree distribution in the rateless code
- Telecommunications Science Vol. 38, Issue 10, Pages: 1-19(2022)
- 作者机构：
  
  1. 上海交通大学宁波人工智能研究院，浙江宁波 315000
  2. 上海交通大学电子信息与电气工程学院，上海 200240
  3. 系统控制与信息处理教育部重点实验室，上海 200240
  4. 上海工业智能管控工程技术研究中心，上海 200240
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2022268
  CLC： TN911
- Published Online：2022-10，
  
  Published：20 October 2022
- 稿件说明：
移动端阅览
Yue QIAO, Yusun FU, Muyun YUAN, et al. Research and development of degree distribution in the rateless code[J]. Telecommunications science, 2022, 38(10): 1-19.
DOI：

Yue QIAO, Yusun FU, Muyun YUAN, et al. Research and development of degree distribution in the rateless code[J]. Telecommunications science, 2022, 38(10): 1-19. DOI： 10.11959/j.issn.1000-0801.2022268.

摘要

无速率编码作为一种纠删码，在减少反馈重传的同时也具有码率灵活、编译码简单的特性，在许多领域都有广阔的应用前景。度分布作为无速率编码设计的基础，对无速率编码的性能有至关重要的影响。随着无速率编码的广泛应用，度分布的设计也需要随着场景和需求的变化进行优化。首先论述了无速率编码的发展与应用，从几种经典的无速率编码和度分布开始，详细地从应用场景、优化目标以及现有优化方法 3 个角度，对目前无速率编码中度分布的研究和发展进行了总结与分析。最后，对无速率编码和度分布的发展应用趋势进行了分析与展望。

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.

关键词

Keywords

references

LUBY M G , . LT codes [C ] // Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science . Piscataway:IEEE Press , 2002 : 271 - 280 .

SHOKROLLAHI A . Raptor codes [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 6 ): 2551 - 2567 .

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 .

YANG S H , YEUNG R W . Batched sparse codes [J ] . IEEE Transactions on Information Theory , 2014 , 60 ( 9 ): 5322 - 5346 .

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 .

徐大专 , 许生凯 , 华洁 , 等 . 数字喷泉码度分布优化设计的最新研究进展 [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 .

MACKAY D J C . Fountain codes [J ] . IEE Proceedings - Communications , 2005 , 152 ( 6 ): 1062 .

黄靖轩 , 费泽松 , 李欢 . 无速率编码及其应用综述 [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 .

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 .

ETESAMI O , SHOKROLLAHI A . Raptor codes on binary memoryless symmetric channels [J ] . IEEE Transactions on Information Theory , 2006 , 52 ( 5 ): 2033 - 2051 .

TANNER R . A recursive approach to low complexity codes [J ] . IEEE Transactions on Information Theory , 1981 , 27 ( 5 ): 533 - 547 .

3GPP . Multimedia broadcast/multicast service(MBMS); protocols and codecs:TS 26.346 V7.2.0 [S ] . 2006 .

ETSI T S . IP datacast over DVB-H:content delivery protocols:102 472 v1.2.1 [S ] . 2006 .

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 .

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 .

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 .

ABDULLAH N F , DOUFEXI A , PIECHOCKI R J . Raptor codes-aided relaying for vehicular infotainment applications [J ] . IET Communications , 2013 , 7 ( 18 ): 2064 - 2073 .

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 .

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 .

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 .

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 .

段文雪 , 胡铭 , 周琼 , 等 . 云计算系统可靠性研究综述 [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 .

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 .

HUSSAIN I , XIAO M , RASMUSSEN L K . Buffer-based distributed LT codes [J ] . IEEE Transactions on Communications , 2014 , 62 ( 11 ): 3725 - 3739 .

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 .

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 .

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 .

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 .

SANDELL M , RAZA U . Application layer coding for IoT:benefits,limitations,and implementation aspects [J ] . IEEE Systems Journal , 2019 , 13 ( 1 ): 554 - 561 .

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 .

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 .

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 .

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 .

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 .

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 .

WIBERG N . Codes and decoding on general graphs [D ] . Linkoping:Linkoping University , 1996 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

戴新颖 , 王建萍 . 基于输出可译集的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 .

郑志国 , 侯登峰 . 基于可译集大小的 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 .

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 .

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 .

雷维嘉 , 张梦 , 谢显中 . 基于度分布合并和可译集优化的 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 .

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 .

任鹏 , 相征 . 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 .

姚渭箐 , 胡凡 . 基于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 .

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 .

龚赟 , 王俊义 . 一种用于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 .

敖珺 , 卢亚军 , 马春波 . 基于短码长的喷泉码度分布设计 [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 .

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 .

李杰 . 无线传输中短码长喷泉码的度分布优化算法 [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 .

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 .

BEIMEL A , DOLEV S , SINGER N . RT oblivious erasure correcting [J ] . IEEE/ACM Transactions on Networking , 2007 , 15 ( 6 ): 1321 - 1332 .

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 .

HAGEDORN A , AGARWAL S , STAROBINSKI D , et al . Rateless coding with feedback [C ] // Proceedings of IEEE INFOCOM 2009 . Piscataway:IEEE Press , 2009 : 1791 - 1799 .

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 .

牛芳琳 , 李宝明 , 陈付亮 , 等 . 一种改进的基于部分信息喷泉码度分布设计 [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 .

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 .

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 .

宋鑫 , 倪淑燕 , 张喆 , 等 . 面向不等差错保护的低误码平台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 .

Views

394

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A hash-neighborhood-search-network-coding based opportunistic relay retransmission approach

An Improved Retransmission Approacb Based on Opportunistic Network Coding in Multicast Networks

Flow Allocation Algorithm Based on Potential Game in Multi-Source Multi-Hop Wireless Sensor Network

Related Author

Pengfei SHAO

Yanwei ZHAO

Zhaoxi FANG

Pengfei Shao

Yanwei Zhao

Yaohui Wu

Xinwei Yao

Wei Zhang

Related Institution

College of Computer Science ＆ Technology，Zhejiang University of Technology

School of Electronic and Information Engineering，Zhejiang Wanli University

College of Mechanical Engineering，Zhejiang University of Technology

College of Computer Science ＆ Technology,Zhejiang University of Technology

College of Mechanical Engineering,Zhejiang University of Technology

⁰