分布式存储系统中纠错码技术的研究

作     者：李萍萍 

作者单位：东莞理工学院 

学位级别：硕士

导师姓名：侯韩旭

授予年度：2024年

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

主      题：分布式存储系统 纠错码 RS码 范德蒙矩阵 多项式求值 

摘      要：随着新一轮科技革命的迅速发展,产生了规模更大的海量数据,对数据存储和流动效率都提出了更高要求。分布式存储系统因其能满足这种大存储与高并发需求,从而成为了海量数据存储的主要方式。但是,分布式存储系统中的数据常常面临因人为或意外造成丢失、删除、篡改等风险。因此,分布式存储系统常常需要引入保障系统数据安全的技术。纠错码是分布式存储与通信系统常用的数据安全保障技术,它可以及时发现和纠正分布式存储系统中数据的错误以保证数据的可靠性与完整性。BCH（Bose-Chaudhuri-Hocquenghem,BCH）码和RS（Reed-Solomon,RS）码是一类强有力的纠正随机错误的循环码,其中RS码是BCH码最重要的一个子类,它们都广泛应用于存储和通信系统。本文在总结现有这两种码译码流程中求解错误位置方案不足的基础上,针对求解错误位置复杂度高的问题,提出了一个基于不完全的Reed-Muller变换的范德蒙矩阵分解,基于此,提出了一种可以用于求解错误位置的算法。本文的具体贡献如下: 1.本文研究了基于Reed-Muller变换的范德蒙矩阵分解规律,分析了其在参数构造方面的限制,以及其应用于求解BCH码和RS码错误位置方面的不足之处,给出了一种不完全的Reed-Muller变换及其相关性质和证明,在此基础上给出了不受参数限制的范德蒙矩阵分解及其相关证明。 2.本文利用给出的范德蒙矩阵分解,提出了一种求解任意码长的BCH码和RS码错误位置的多项式求根算法,消除了其中不必要的加法操作,并给出了相关定理及其证明。最后,本文分析了提出的多项式求根算法的计算复杂度,并将提出的多项式求根算法与经典的钱式搜索算法以及当前计算复杂最低的基于快速傅里叶变换(FFT)的多项式求根算法进行比较,结果表明本文提出的多项式求根算法的加法复杂度和乘法复杂度均低于钱式搜索算法。此外,在加法复杂度近似的前提下,它的乘法复杂度显著低于目前最优的基于FFT的多项式求根算法。