基于二进制矩阵的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@