RS柯西码编码算法改进研究

发布时间：2020-12-23 16:32

　　针对RS（Reed-Solomon）算法编码过程涉及有限域运算,复杂度高,效率低,运算代价难以被大规模分布式存储系统所接受等问题,提出了一种RS柯西码编码改进算法。该算法用贪心算法选取局部最优柯西矩阵,减少柯西码的计算量。同时,引入二进制矩阵替换柯西矩阵中的有限域元素进行阵列化,将有限域运算转换为异或运算,并对阵列进行运算优化,进一步减少计算量,增加柯西码的编码效率。根据仿真实验表明,改进后RS柯西码与通过遍历得到的最优柯西矩阵的柯西码相比,计算量更小,与编码效率著称的阵列码中的EVENODD码和STAR码相比,编码效率更高。并且具有类似阵列码性质,能够选择更简单高效的译码方法,在一定程度上提高解码效率。 

【文章来源】：计算机工程与应用. 2020年11期 北大核心

【文章页数】：7 页

【部分图文】：

第一次连线图

在有了二进制矩阵替换有限域元素的方法，将复杂的有限域运算转换为简单的异或运算，RS柯西码的计算复杂度得到了一定程度的降低。但集合X、Y的不同，对RS柯西码的编码效率影响非常大。目前，并没有一个好的方法去得到最优集合X和Y，只能通过遍历得到，随着规模加大，得到最优集合的代价也会随之增加。也有采取随机的方式来选取集合X和Y，但得到的柯西矩阵的1的数量无法得到保证。图2展示了优化后的RS柯西码与遍历最优RS柯西码、随机RS柯西码的编码所需异或数对比情况，并且以两种不同条件进行更全面的展示。图2(a）展示的是在保持校验块数为4，有限域为GF(24)的条件下，数据块数从4到9编码所需的异或数变化情况。图2(b）展示的是在保持数据块数为4，有限域为GF(24)的条件下，校验块数从4到8编码所需的异或数变化情况。从图中可以看出经过优化后的RS柯西码编码所需的异或数远小于文献[14]的遍历最优RS柯西码，并且选取集合X、Y的代价也相对较小。编码效率不仅能够通过编码所需的异或数来体现。通过编码时间也能更直观地反应编码的效率。图3与图4分别展示了优化后的RS柯西码与EVENODD码、STAR码分别对1～10 MB的文件进行编码的编码时间对比情况，并分为数据块数为5和7分别进行对比。从图中可以看出经过优化的RS柯西码的编码时间与以编码效率著称的阵列码中的代表EVENODD码和STAR码相差不大，甚至有一些优势。并且对于EVENODD码和STAR码，容错超过3便失效了。可见优化后的RS柯西码编码效率有了很大幅度的提升。

编码效率不仅能够通过编码所需的异或数来体现。通过编码时间也能更直观地反应编码的效率。图3与图4分别展示了优化后的RS柯西码与EVENODD码、STAR码分别对1～10 MB的文件进行编码的编码时间对比情况，并分为数据块数为5和7分别进行对比。从图中可以看出经过优化的RS柯西码的编码时间与以编码效率著称的阵列码中的代表EVENODD码和STAR码相差不大，甚至有一些优势。并且对于EVENODD码和STAR码，容错超过3便失效了。可见优化后的RS柯西码编码效率有了很大幅度的提升。图4 优化后的RS柯西码与STAR码的编码时间对比


本文编号：2934005