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

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

Abstract

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

CLC Number:

TN911.22

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.

Figures/Tables 14

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

References 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]	Anan ZHOU, Benshun YI, Yusheng LIU, Laigan LUO. Novel construction of repairable fountain code in distributed storage systems [J]. Systems Engineering and Electronics, 2022, 44(1): 285-291.
[2]	Xinying DAI, Jianping WANG. Optimization of combined degree distribution of LT codes based on output ripple size [J]. Systems Engineering and Electronics, 2020, 42(3): 727-732.
[3]	ZHU Wenjie1, YI Benshun1,2, GAN Liangcai1. Performance research of FountainDFH concatenated coding systems over AWGN with partialband noise jamming [J]. Systems Engineering and Electronics, 2016, 38(3): 665-671.
[4]	ZHAO Dan-feng, SI Jia-xi, LIANG Ming-shen, DUAN Jin-jue. Low redundancy LT code based on arithmetic coding and its application in secure communication [J]. Systems Engineering and Electronics, 2016, 38(2): 409-414.
[5]	ZHU Kaiyan1,2, WANG Hongyu1, SUN Wenzhu3, SONG Weibo2. Cooperative transmission with regular variablenode degree LT codes [J]. Systems Engineering and Electronics, 2015, 37(5): 1163-1169.
[6]	ZHAO Dan-feng， LIANG Ming-shen， DUAN Jin-jue. Survey of fountain codes in underwater acoustic sensor networks [J]. Systems Engineering and Electronics, 2014, 36(9): 1838-1843.
[7]	LIU Xiao-jian， SUN Xiao-jun. Design of short length system Luby transform code of high rate in concatenated scheme [J]. Journal of Systems Engineering and Electronics, 2013, 35(3): 634-637.
[8]	GU Shu-shi, JIAO Jian, YANG Zhi-hua, ZHANG Qin-yu. Relay cooperation fountain codes for deep space communications [J]. Journal of Systems Engineering and Electronics, 2012, 34(8): 1696-1701.
[9]	SUN Rong, LIU Jing-wei, SUN Yue, BAI Bao-ming. On the rateless character of irregular RA codes [J]. Journal of Systems Engineering and Electronics, 2011, 33(3): 654-658.
[10]	ZHAO Dan-feng,QIAN Jin-xi,WU Yu-ping. Application of improved unequal error protected fountain codes algorithm in scalable video [J]. Journal of Systems Engineering and Electronics, 2011, 33(1): 170-0172.
[11]	YAO Wen-ding, LI Hui, CHEN Li-jia, XU Hong-guang. Study on the fountain codes technology in deep space communications [J]. Journal of Systems Engineering and Electronics, 2009, 31(1): 40-44.
[12]	YAO Wen-ding, LI Hui, CHEN Li-jia, XU Hong-guang. Study on the fountain codes technology in deep space communications [J]. Journal of Systems Engineering and Electronics, 2009, 31(01): 40-44.

Analysis and optimization of RaptorQ fountain code encoding and decoding algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 11

Related Articles 12

Recommended Articles

Metrics

Comments