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

reed-solomon简介

计 算 机 工 程 第 37 卷 第23期

Computer Engineering V ol.37 No.23 文章编号：文章编号：1000—3428(2011)23—0057—03 ·软件技术与数据库·软件技术与数据库· 2011年12月 December 2011 文献标识码：文献标识码：A 中图分类号：中图分类号：TP301.6

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

朱卫卫，朱卫卫，杨金民

(湖南大学软件学院，长沙 410082)

摘 要：现有RAID系统的编码算法不能同时具备较高的执行效率和较强的容错能力。为此，提出一种基于二进制矩阵的RS编码优化算法。使用RS编码中有限域内乘法运算得到转换后的二进制矩阵，采用多分法对其进行优化，从而减少编码时的异或运算次数，以此设计优化算法。实验结果表明，该算法的执行效率较高，容错能力较大。

关键词：关键词：范德蒙矩阵；容错；数据冗余；二进制矩阵

Optimization Algorithm for RS Coding Based on Binary Matrix

ZHU Wei-wei, YANG Jin-min

(College of Software, Hunan University, Changsha 410082, China)

【Abstract】Aiming at the problem of the existing coding algorithms can not meet the needs of high performance and large fault tolerance at the same time in RAID(Redundant Array of Inexpensive Disc) system, this paper proposes a algorithm for RS coding based on binary matrix. The method uses binary matrix to optimize the multiplication operation in finite fields. Meanwhile, the theory of multisection is used in the algorithm to reduce the XOR operation. Experimental result show that the proposed algorithm has high efficiency and good performance, and can be used in large fault-tolerant systems.

【Key words】Vandermonde matrix; fault-tolerant; data redundancy; binary matrix

DOI: 10.3969/j.issn.1000-3428.2011.23.019

1 概述

RAID[1]是一种基于数据冗余的磁盘容错技术，文献[2-3]

提出EVENODD和STAR算法是基于该技术的编码算法，虽

然这些算法的编码过程简单、效率高，但只能容2个、3个

磁盘错误，显然很难满足现在的需求。文献[4]里德所罗门

(Reed-solomon, RS)编码可以实现对任意多磁盘失效的容错，

但这种编码算法的运算过程涉及到有限域内的乘法操作实现

起来比较复杂。文献[4]使用查对数与反对数表的方法来解决

有限域内乘法运算的问题，但该方法进行一次乘法要经过多

次查表，运算效率较低。本文针对上述问题提出基于二进制

矩阵的RS编码优化算法。 校验盘损坏的话，可重新根据F计算校验盘中的数据。 由于RS编码的运算是在有限域内进行的，加法可以直接用二进制的异或(Exclusive-or, XOR)进行运算。而乘法一 般用多项式来构造，但这种方法不管用软件还是硬件实现起来都比较复杂，因此需要用一种简单、有效的方法来表示有限域内的乘法。 3 2种乘法运算的同构关系 根据文献[4]多项式构造有限域内乘法的方法，可得出GF(2w)上的任意一个元素都能用一个多项式f(x)表示，得到下式： i 1f(x)=∑iw=0fix (2) 2 基于范德蒙矩阵的基于范德蒙

矩阵的RS算法

RS算法是一种前向纠错算法，以实现基于数据块的错

误纠正。将数据块称为word，每个磁盘划分为若干个word，

每个word的大小是w bit。用矩阵D表示n个数据盘，矩阵

C表示m个校验盘，文献[5]给出整个编码过程为C=DF，其

中，F为n×m阶的范德蒙矩阵，展开得下式：

cn= d1d2L111L121L

MM

1n1L1m2m (1) Mnmc1c2Ldn

当磁盘阵列中有i≤m个磁盘崩溃时，根据下面的方法

进行数据恢复：构建一个n×(m+n)阶矩阵A，其前n列是一

个单位矩阵，后m列是范德蒙矩阵F，则删除掉任意m列后

的矩阵为一个可逆矩阵，这样当i块磁盘崩溃后，就在A和

C中删去对应的i行，得到矩阵A’，有C’=A’D，这样可以通

过高斯消元法得到D，也就恢复了数据盘中的内容。如果有其中，fi=0,1。 将向量(f0, f1,…, fw 1)称为多项式f(x)的系数向量。即对 域内的元素均可用相应的系数向量来表示。由上述分析给出如下定义：对于GF(2w)中的元素f，Γ(f)是一个w×w的二进制矩阵，其中，第i列为xi×f mod p(x)的系数向量。根据文 献[6]中矩阵与系数向量之间的关系可得出以下性质，其中，用“*”表示域内乘法或者二进制矩阵乘法： (1)Γ是GF(2w)到Γ(GF(2w))的同构； (2)对于GF(2w)内的元素g、f有Γ(g+f)=Γ(g)+Γ(f)； (3)对于GF(2w)内的元素g、f有Γ(g*f)=Γ(g)*Γ(f)。 根据Γ的性质，域内乘法就可以转换为Γ上的二进制矩基金项目：基金项目：湖南省科技计划基金资助重点项目(2009JT1018) 作者简介：作者简介：朱卫卫(1985－)，男，硕士研究生，主研方向：编码容错；杨金民，教授、博士 收稿日期：收稿日期：2011-06-28 E-mail：zwwheart008@

reed-solomon简介

58 计 算 机 工 程 2011年12月5日 阵乘法。例如对于GF(23)中的元素4、5域内乘法运算的转

化，如图1所示。

图1 二进制矩阵表示域内乘法

由图1可知，当域内的元素同构成二进制矩阵后，域内

乘法也就转换成二进制矩阵间的乘法。

由于RS编码在计算过程中涉及到域内元素的乘法运算，

因此将域内元素的乘法运算转换为二进制矩阵的乘法运算，

而矩阵中二进制元素的乘法运算即为与运算。如一个RS(4,2)

容错系统(w=3)，先将数据盘和校验盘中的数据在有限域内

用多项式表示：da=d1x2+d2x+d3，ca=c1x2+c2x+c3等。即d1、

d2、d3和c1、c2、c3就是da、ca在GF(23)内的系数，对其进

一步根据Γ的性质同构成二进制矩阵，则式(1)变换成下式：

c1c2c3c4c5c6=

d1d2d3d4d5d6d7 d8d9d10d11d12×

100100

010010

001001

100001

010101

001010

100101

010111

001011

100010

010011

001101

其中，c1,c2,…,c6和d1,d2,…,d12的取值为0或1，即1 bit。由于二进制的异或操作不管数据位数有多长都只是在对应位置上作异或运算，因此上述每个盘中每次对3个1 bit数据的

编码就可以推广到1 Byte，也可以是w bit的字。则RS(4,2)

容错系统的编码过程其实是每次对每个数据盘中3个w bit的二进制字进行编码，此过程如图2所示。

图2 容错系统编码过程举例

综上所述，对于任意的范德蒙RS(n,m)码，都可以把它

转换为纯异或的编码，其编码矩阵为(wn)×(wm)的二进制

矩阵。

4 多分法优化二进制矩阵

多分法的思想在矩阵论中，主要用来将所给矩阵计算问

题分解成多个小规模矩阵，从而更方便、更容易的解决该问

题。由此，根据第3节中二进制编码矩阵的特点，提出一种

多分法优化算法。

对于改进后的RS编码，发现影响每个校验盘编码性能

的是进行XOR的次数。而XOR的次数又直接由二进制矩阵

中对应列“1”的个数所决定。例如，把矩阵中某列“1”的

个数记为k，则通过前面的二进制矩阵可以得出该列XOR的

次数为k 1。同时如果把矩阵中“0”的个数记为t，则XOR的次数可以通过wn t 1来表示，其中，n为校验盘个数；w为word长度。 从式(1)的变化式可以发现，转换成二进制矩阵后该矩阵的前w列是由n个w×w的单位矩阵所构成，在这n个单位 矩阵中的“1”，以间隔w个位置均匀分布在二进制矩阵的前w列，同时这w列编码时正好都不重复的只取每个数据盘中的一个word。例如前面的RS(4,2)系统，在转换成二进制矩阵后总共要进行25次XOR操作。将第3节式(1)的变化式表示成下式： c1=d1+d4+d7+d10 c2=d2+d5+d8+d11 c3=d3+d6+d9+d12 c=d+d+d+d+d (3) 4157812 c5=d2+d6+d8+d9+d10+d11 c6=d3+d4+d5+d7+d8+d9+d11+d12结合图2可以发现式(3)中，c1、c2、c3是所有数据盘中相同水平位置的数据进行XOR操作，而且c1、c2、c3正好用到了每次进行编码的所有数据。因此在矩阵中我们也可以看成是c1、c2、c3把数据d1, d1,…,d12均匀的间隔成w=3份(间隔距离为w 1)，这里把c1、c2、c3称为发生器。那么式(3)中的某些列编码可看成是由发生器去除“0”位置数据后的总和，同时由于XOR运算中加法和减法是一样的，这样式(3)可变换成下式： c1=d1+d4+d7+d10 c2=d2+d5+d8+d11 c3=d3+d6+d9+d12 c=d (4) 41+d5+d 7+d8+d12 c5=c2+d6+d9+d10+d5 c6=c2+c3+d4+d7+d2+d6发现通过变换后得到的式(4)只进行了22次XOR操作，其中，c5、c6用到了发生器c2、c3。可以看出，用发生器生成某些校验盘中的数据比直接运算效率要高。 在编码过程中，如果把二进制矩阵(wn)×(wm)间隔分成 多个n×m的小矩阵，就可以用发生器来计算某些校验盘。这里需要考虑什么时候使用发生器。首先，通过前面分析可以知道发生器中的数据就是第1块校验盘中的数据，从第2块校验盘开始，校验盘数据产生的方法描述如下： (1)从第w+1列开始把二进制矩阵按发生器的形式间隔分成w个n×m的小矩阵(间隔距离w 1)。 (2)统计小矩阵每一列中数据“1”的个数。 (3)当“1”的个数大于n/2时，说明“0”的个数要比“1”的个数多，这时用相应的发生器去除“0”位置对应的数据要比直接对“1”位置上的数据进行运算来的快。 (4)当“1”的个数小于等于n+1/2时说明“1”的个数要比“0”的个数多，则直接对“1”位置上的数据进行运算。 (5)将所有用(3)中发生器产生的数据与(4)中直接产生的数据相加就是校验盘的数据。 按照上述方法，可以减少二进制矩阵在编码时某些校验盘XOR操作的次数。得出当系统规模n+m增大时，相应的二进制矩阵(wn)×(wm)的规模也变大，而该矩阵中“1”的个数变多。这样用发生器产生对应列数据的可能性也会变多，使得编码时运算次数降低。此外，用发生器的优点是发生器中的数据是，第1块校验盘中的数据所以不会占用额外的存

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. 编辑 张正兴

reed-solomon简介

reed-solomon简介

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

本文来源：https://www.bwwdw.com/article/0u1j.html