RaptorQ喷泉码编译码算法分析及优化

doi:10.12305/j.issn.1001-506X.2024.04.33

摘要/Abstract

摘要：

RaptorQ喷泉码是喷泉码的最新研究成果, 理论分析和仿真验证表明, RaptorQ喷泉码是性能最好的喷泉码, 同时也是编译码复杂度最高的喷泉码。针对RaptorQ喷泉码编译码复杂度高这一问题, 以国际标准RFC6330所设计的RaptorQ码编译码流程为基础, 提出一种RaptorQ编译码算法的优化版本。新的编译码流程通过固定生成矩阵的方式提前计算好生成矩阵并存储, 方便随时调用; 通过提前列变换的方式规避多次寻找标准行和高斯消去操作, 以及通过去稀疏化的方式, 减少编译码过程中的矩阵乘法和异或运算。仿真比较优化前后的编译码算法, 结果表明, 优化后的RaptorQ码编译码流程能够在保证传输性能不变的同时, 减少RaptorQ喷泉码编译码基本运算次数、缩短RaptorQ喷泉码编译码的时间, 降低了编译码的计算复杂度, 并保持了传输性能。

关键词: 喷泉码, RaptorQ, RFC6330, 编译码算法

Abstract:

RaptorQ fountain code is the latest research achievement of fountain code. Theoretical analysis and simulation verification show that RaptorQ fountain code is the fountain code with the best performance, and it is also the fountain code with the highest encoding and decoding complexity. Aiming at the problem of high complexity of RaptorQ fountain code encoding and decoding, based on the RaptorQ code encoding and decoding process designed by the international standard RFC6330, an optimized version of RaptorQ encoding and decoding algorithm is proposed. The new encoding and decoding process calculates the generated matrix in advance by the way of fixing generation matrix and matrix storing, which is convenient to call at any time, avoiding multiple searches for standard rows and Gaussian elimination operations through advance column transformation, and reducing matrix multiplication and exclusive-OR operations in the process of encoding and decoding process by means of de-shinning. The simulation compares the encoding and decoding algorithms before and after the optimization. The results show that the optimized RaptorQ code encoding and decoding process can reduce the number of basic operations of RaptorQ fountain code encoding and decoding, shorten the time of RaptorQ fountain code encoding and decoding, reducing the complexity of encoding and decoding while ensuring the transmission performance unchanged.

Key words: fountain code, RaptorQ, RFC6330, encoding and decoding algorithm

中图分类号:

TN911.22

马梦宇, 罗长洲, 梁春瑞, 王杰. RaptorQ喷泉码编译码算法分析及优化[J]. 系统工程与电子技术, 2024, 46(4): 1440-1447.

Mengyu MA, Changzhou LUO, Chunrui LIANG, Jie WANG. Analysis and optimization of RaptorQ fountain code encoding and decoding algorithm[J]. Systems Engineering and Electronics, 2024, 46(4): 1440-1447.

图/表 14

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

参考文献 11

12	YUAN M, FU Y, QIAO Y, et al. Rateless codes for reliable and secure packet transmission in industrial control systems[C]//Proc. of the China Automation Congress, 2021: 6376-6381.
13	YING Y Z . Simulation of public art communication in colleges based on smart cloud platform and artificial intelligence algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40 (4): 7359- 7369.
14	RAZA A , BUKHARI S H R , AADIL F , et al. An UAV-assisted VANET architecture for intelligent transportation system in smart cities[J]. International Journal of Distributed Sensor Networks, 2021, 17 (7): 15501477211031750.
15	LAZARO F , LIVA G , BAUCH G , et al. Bounds on the error probability of Raptor codes under maximum likelihood decoding[J]. IEEE Trans.on Information Theory, 2021, 67 (3): 1537- 1558. doi: 10.1109/TIT.2020.3049061
16	CAO N, YU S C, YANG Z Y, et al. LT codes-based secure and reliable cloud storage service[C]//Proc. of the IEEE INFOCOM, 2012: 693-701.
17	ZHENG Z , YUAN L , FANG F . Performance analysis of fountain coded non-orthogonal multiple access with finite blocklength[J]. IEEE Wireless Communications Letters, 2021, 10 (8): 1752- 1756. doi: 10.1109/LWC.2021.3078811
18	CHANG S Y, CHIAO H T, SHEU R K, et al. Accelerating transmission of streaming files based on AL-FEC protection blocks[C]//Proc. of the IEEE 45th Annual Computers, Software, and Applications Conference, 2021: 1188-1193.
19	THEODOROPOULOS D , KRANITIS N , TSIGKANOS A , et al. Efficient hardware architectures and implementations of packet-level erasure coding schemes for high data rate reliable satellite communications[J]. IEEE Trans.on Aerospace and Electronic Systems, 2021, 58 (3): 2269- 2280.
20	TASDEMIR E, TÖMÖSKÖZI M, SALAH H, et al. Low-latency sliding-window recoding[C]//Proc. of the IEEE 93rd Vehicular Technology Conference, 2021.
21	郭晓, 张更新, 徐任晖, 等. 一种用于RaptorQ码的降维快速译码算法[J]. 电子与信息学报, 2015, 37 (6): 1310- 1316.
	GUO X , ZHANG G X , XU R H , et al. Fast decoding algorithm for RaptorQ code using matrix dimensionality reduction[J]. Journal of Electronics & InformationTechnology, 2015, 37 (6): 1310- 1316.
22	李越, 张立军, 李明齐, 等. 一种RaptorQ码的低复杂度编码算法[J]. 电视技术, 2017, 41 (3): 57- 60.
	LI Y , ZHANG L J , LI M Q , et al. Low complexity encoding method for RaptorQ code[J]. Video Engineering, 2017, 41 (3): 57- 60.
23	李越, 张立军, 李明齐, 等. 一种RaptorQ码的模式选择解码算法[J]. 电视技术, 2016, 40 (12): 120- 124.
	LI Y , ZHANG L J , LI M Q , et al. A mode selection algorithm for RaptorQ code decoding[J]. Videoengineering, 2016, 40 (12): 120- 124.
1	CEBECIOGLU B B . RaptorQ codes aided secure data delivery strategy for vehicular networks[J]. Automatisierungstechnik, 2022, 70 (2): 154- 163. doi: 10.1515/auto-2020-0146
2	郭瑞林. 基于喷泉码的物理层安全关键技术研究[D]. 成都: 电子科技大学, 2022.
	GUO R L. Research on key technologies of physical layer security based on fountain code[D]. Chengdu: University of Electronic Science and technology, 2022.
3	滕井赛. 数字喷泉码编译码设计优化和仿真分析[D]. 杭州: 杭州电子科技大学, 2020.
	TENG J S. Digital fountain code coding and decoding design optimization and simulation analysis[D]. Hangzhou: Hangzhou Dianzi University, 2020.
4	LEE C H, LI Y L. Preliminary study of cache exchange improvement based on RaptorQ and tsunami[C]//Proc. of the IET International Conference on Engineering Technologies and Applications, 2022.
5	刘亦伟. 铁路车地广播通信系统中喷泉码的应用研究[J]. 铁路通信信号工程技术, 2021, 18 (4): 35-38, 58. doi: 10.3969/j.issn.1673-4440.2021.04.007
	LIU Y W . Research on performance of RaptorQ code in railway broad-casting system[J]. Railway Signalling & Communication Engineering, 2021, 18 (4): 35-38, 58. doi: 10.3969/j.issn.1673-4440.2021.04.007
6	REN Y , ZHANG Y , LIU Y W , et al. DNA-based concatenated encoding system for high-reliability and high-density data storage[J]. Small Methods, 2022, 6 (4): 2101335. doi: 10.1002/smtd.202101335
7	BULUT B . Experimental analysis and evaluation of RaptorQ codes for video multicasting over wifi[J]. Wireless Personal Communications, 2020, 114 (2): 1431- 1448. doi: 10.1007/s11277-020-07428-6
8	高斐, 赵娜. 基于RaptorQ码的网络资源安全云存储结构设计[J]. 软件, 2021, 42 (10): 135- 137.
	GAO F , ZHAO N . Network resource security cloud storage architecture design based on RaptorQ code[J]. Software, 2021, 42 (10): 135- 137.
9	SHOKROLLAHI A . Raptor codes[J]. IEEE Trans.on Information Theory, 2006, 52 (6): 2551- 2567. doi: 10.1109/TIT.2006.874390
10	ALASMAR M , PARISIS G , CROWCROFT J . Scdp: systematic rateless coding for efficient data transport in data centers[J]. IEEE/ACM Trans.on Networking, 2021, 29 (6): 2723- 2736. doi: 10.1109/TNET.2021.3098386
11	TALHA G M , ALI A , SINGH D K , et al. Merge-and-forward: a cooperative multimedia transmissions protocol using RaptorQ codes[J]. IET Communications, 2016, 10 (15): 1884- 1895. doi: 10.1049/iet-com.2016.0146

[1]	周安安, 易本顺, 刘羽升, 罗来干. 分布式存储系统中新型可修复喷泉码构造[J]. 系统工程与电子技术, 2022, 44(1): 285-291.
[2]	戴新颖, 王建萍. 基于输出可译集的LT码联合度分布优化[J]. 系统工程与电子技术, 2020, 42(3): 727-732.
[3]	朱文杰1, 易本顺1,2, 甘良才1. 喷泉码差分跳频系统在AWGN中抗部分频带干扰性能研究[J]. 系统工程与电子技术, 2016, 38(3): 665-671.
[4]	赵旦峰, 司佳希, 梁明珅, 段晋珏. 基于算术编码的低冗余LT码及其在安全通信中的应用[J]. 系统工程与电子技术, 2016, 38(2): 409-414.
[5]	祝开艳1,2, 王洪玉1, 孙文珠3, 宋维波2. 基于规则变量节点度LT码的协作传输[J]. 系统工程与电子技术, 2015, 37(5): 1163-1169.
[6]	赵旦峰，梁明珅，段晋珏. 水声网络中喷泉码的应用研究现状与发展前景[J]. 系统工程与电子技术, 2014, 36(9): 1838-1843.
[7]	刘晓健，孙小钧. 级联码中的高码率短码长SLT码设计[J]. Journal of Systems Engineering and Electronics, 2013, 35(3): 634-637.
[8]	祝开艳１，２，王洪玉１，孙文珠１. 基于网络编码和中继选择的无码率协作传输[J]. 系统工程与电子技术, 2013, 35(11): 2439-.
[9]	顾术实, 焦健, 杨志华, 张钦宇. 面向深空通信的中继协作喷泉码设计[J]. Journal of Systems Engineering and Electronics, 2012, 34(8): 1696-1701.
[10]	孙蓉，刘景伟，孙岳，白宝明. 非规则RA码无码率特性分析[J]. Journal of Systems Engineering and Electronics, 2011, 33(3): 654-658.
[11]	赵旦峰,钱晋希,吴宇平. 一种改进的UEP喷泉码算法及其在FGS系统中的应用[J]. Journal of Systems Engineering and Electronics, 2011, 33(1): 170-0172.
[12]	姚文顶, 李晖, 陈立甲, 许洪光. 深空通信中喷泉码技术研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(1): 40-44.
[13]	姚文顶, 李晖, 陈立甲, 许洪光. 深空通信中喷泉码技术研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(01): 40-44.