安全存储系统中纠删码技术研究

发布时间：2024-04-19 00:30

　　冗余备份机制是安全存储系统提高系统可靠性和容灾容错能力的一个重要方法。纠错码及纠删码技术是冗余备份机制的一个重要方法。与其他技术相比,纠删码技术在节省存储空间,提高容错容灾能力,提高数据的可靠性方面有着明显的优势。本文在学习和掌握已有的纠删码技术的基础上,本文的主要贡献在两个方面: 本文构建了求解最优柯西矩阵的数学模型,并且提出了求解该问题的近似算法。通过分析柯西RS码的编码方式,柯西RS码在编码过程中柯西矩阵对编码效率有着极大的影响。本文提出来的局部贪婪算法在复杂度均好于Plant提出的求解最优柯西矩阵的算法,并且得到的最优矩阵的近似解与Plant提出的算法得到的结果相同。 本文提出了LDPC码校验矩阵构造算法Progressive Weight-Growth(PWG),该算法通过迭代增加校验矩阵的行重和列重,构造高码率的LDPC码。和现有构造算法(MacKay构造算法,比特填充算法)相比,LDPC码能够比它们构造更高码率的码,同时PWG算法构造的LDPC码能够提高码中各个节点的围长分布,并且与一些已知好码有着相同的性能。

【文章页数】：57 页

【学位级别】：硕士

【部分图文】：

图3-7：LGA算法Fig.3-7:LGAalgorithm根据该算法，在域3GF(2)构造一个G×的柯西矩阵，如图3-8所示：

由于在每个步骤中，该算法总是选取重量最小的元素，所以该算法称为局部贪婪算法(LocalizeGreedyAlgorithm,LGA)，该算法在每一个步骤中保证得到是最小重量的元素，但是不能保证最终得到是最优解。图3-7是该算法的具体描

图3-10：4GF(2)上LGA与RC算法比较

方面对三种方法进行了比较。RC和LGA生成的柯西矩阵性能比较在这个比较过程中，参数分别为n=3,L=4,而m从3到13变化.在图3-10中，m∈[3,13]时，点线表示LGA生成的矩阵的平均重量，实线表示RC生成的矩阵的平均重量(是一个定值)。

图3-11：8GF(2)上LGA与RC算法比较

8GF(2)图3-11中的平面是RC矩阵的平均重量，曲面则是LGA的平均重量。在这9×245=2205个矩阵中，矩阵平均重量的增益达到:210,224618.6%2205RCLGARCGGnmGWWW≤≤≤≤∑=LGA与PX的比较在PX和LGA的比较....

图3-12：LGA与PX比较

×，两种算法构造出来的柯西矩阵的平均重量如图3-12所示,从图3-12中可以看出，LGA和PX得到的柯西矩阵的平均重量相差无几。直线为L变化时的RC方法得到的柯西矩阵的平均重量。

本文编号：3957954