基于二进制矩阵的RS编码优化算法(3)

reed-solomon简介

第37卷 第23期 朱卫卫，杨金民：基于二进制矩阵的 RS 编码优化算法 59 储空间。

容错系统主要通过编码与解码能力分析其解码的情况。

解码矩阵同编码矩阵都可以转换为二进制矩阵，但由于一个

RS(n,m)系统，可以容一个到m个任意磁盘出错，其发生出错

的情况有C1n+m+C2n+m+…+Cmn+m种，这使其解码矩阵变的

不确定，矩阵前w列也不一定是由一个个w×w的单位矩阵

所构成，因此上述优化方法不适合解码的情况。 的方法[3]使其运算过程也只有异或操作，且编码和解码性能都要比RS(二进制)的效率高。但RS(二进制)用发生器优化 为RS(发生器)后，由于进一步减少了编码时校验盘数据在实际运算过程中的次数，使得该算法在编码性能上面要比 STAR算法来的高。但是，由于发生器的优化方法不能应用在解码过程中，RS(发生器)的解码退化为RS(二进制)的解 码，其性能比STAR算法来的低。

然而在实际情况中，由于编码和解码并不对称。编码在

每次存储数据时都会用到，而解码只有在磁盘发生故障时才

用到，所以在实际容错系统中，编码效率才是影响系统性能

的首要判定因素。这样如果只考虑编码的情况，RS(发生器)

的效率比STAR算法来的高，且当磁盘阵列组容错能力>3

时，STAR算法已经失效，而RS(发生器)却可以容任意磁盘

数的出错。所以从整体性能上考虑，RS(发生器)不失为一种

通用，有效的算法。 5 算法性能分析 为了对本文算法进行性能测试，设计一个编码和解码的模拟实验。在该实验中，通过测试磁盘生成、恢复数据的平均XOR数对本文算法与传统RS算法以及STAR算法进行比较。对于传统RS算法，把每次查表看作一次异或运算(因为异或和查表的主要时间都用于访问内存)。经过二进制矩阵 改进后的算法称为RS(二进制)，发生器优化过的算法称RS

(发生器)。图3、图4给出对不同矩阵规模(阵列模式)(n,m)的

RAID系统的编码和解码测试结果。

6 结束语

本文提出基于二进制矩阵的RS编码优化算法。利用同

构的概念，将原编解码过程中涉及到的伽罗华域内乘除法运

算转换为二进制矩阵间运算，利用转换得到的二进制编码矩

阵前w列是由一个个单位矩阵组成的特点，给出一种多分

法的优化方法。实验结果表明，该优化算法具有较好的容错

能力和时间性能。然而，在转换为二进制矩阵后，数据冗余

度会随着w的取值增加而增加，下一步将研究如何取合适的

w值，使其在保证高时间性能的同时降低冗余度。

参考文献

[1] Gibon A. Redundant Disk Arrays: Reiable, Parallel Secondary

Storage[M]. Cambridge, England: The MIT Press, 1992.

图3 4种算法编码效率算法编码效率比较编码效率比较

[2] Blaum M, Brady J, Bruck J, et al. EVENODD: An Ef cient

Scheme for Tolerating Double Disk Failures in RAID Arch-

itectures[J]. IEEE Transactions on Computers, 1995, 44(2):

192-202.

[3] Huang Cheng, Xu Lihao. STAR: An Ef cient Coding Scheme for

Correcting Triple Storage Node Failures[C]//Proc. of the 4th

USENIX Conference on File and Storage Technologies. San

Francisco, USA: [s. n.], 2005.

[4] Plank J S. A Tutorial on Reed-solomon Coding for Fault-tolerance

in Raid-like Systems[J]. Software——Practice & Experience,

1997, 27(9): 995-1012.

[5] 刘昀昊, 张敏情, 杨晓元. 基于RS码的错误容忍存储方案[J].

计算机工程, 2010, 36(14): 65-67.

[6] Rizzo L. On the Feasibility of Software FEC[EB/OL]. (2010- 图4 4种算法解码效率算法解码效率比较解码效率比较

11-21). http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.49. 从图3、图4可以看出，RS(二进制)由于运算过程只有

2563. 异或操作，所以性能要比传统的RS码的编码和解码都要高。 编辑 刘 冰而STAR算法由于只针对m=3的情况，采用对角线奇偶编码 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(上接第53页)

[2] 杨鹤标, 侯仁刚, 田青华. 支持界面自动生成的模型研究[J].计

算机工程, 2010, 36(3): 79-82.

[3] 李 琦, 李建成, 张科峰. 基于GUI4J的界面自动生成技 术[J].

西安工程大学学报, 2010, 24(3): 334-337.

[4] Mori G, Paterno F, Santoro C. Design and Development of Multi-

device User Interfaces Through Multiple Logical Descriptions[J]. IEEE Trans. on Software Engineering, 2004, 30(8): 1-14. [5] Batsukh N, Book M, Kmann T B. Automatic Generation of Ruler-based User Interfaces of Web Applications[C]//Proc. of the 3rd International Conference on Internet and Web Applications and Services. Athens, Greece: [s. n.], 2008. 编辑 张正兴