RS类纠删码的译码方法

作     者：唐聃 蔡红亮 耿微 Tang Dan;Cai Hongliang;Geng Wei

作者机构：成都信息工程大学软件工程学院成都610225 四川省信息化应用支撑软件工程技术研究中心成都610225 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2022年第59卷第3期

页      面：582-596页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：四川省重点研发计划项目(2020YFG0150) 

主　　题：RS码 纠删码 译码 数据重构 修复成本 

摘      要：RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR,XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明:在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.