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

Analysis and optimization of RaptorQ fountain code encoding and decoding algorithm

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

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.