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

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块校验盘中的数据所以不会占用额外的存