Reed-Solomon纠删码简析

Reed-Solomon编码（又叫RS编码、里德-所罗门编码）作为一种前向纠错编码，是一种很常见的数据冗余技术，也就是通过对数据增加冗余部分来保证当数据丢失时能够在一定程度上进行恢复。最典型的应用就是在现在最流行的QR二维码的编码设计中。

实现功能

他所解决的问题是：给定n个数据块(d_1,d_2,d_3,...,d_n)，对于一个确定的正整数m， RS编码能够根据这n个数据块生成m个校验块， (c_1, c_2,..., c_m)。  我们能够做到，从这m+n个数据(或校验)块中任取n块就能解码出原始数据。 即对于n个数据块进行RS编码后生成的n+m个数据块，我们能够容忍丢失至多m个数据块。

编码原理

实现的功能听上去很强大，其实原理却十分简单，只是他很巧妙的运用了矩阵运算的特点，说起来也十分简单。

一、对于需要进行冗余处理的n个数据块，我们把他写成列向量的形式，其中每个数据块都可以看做是一个数。

二、生成一个变换矩阵，这个矩阵由n+m行和n列组成，其中上面的n\times n的部分是一个单元矩阵，下面的m\times n的部分是一个范德蒙矩阵。

三、用这个变换矩阵左乘数据列向量得到n+m位冗余码列向量。

算式如下：

上面使用单位矩阵显然是为了保证原数据块在编码后不发生变化，从而看上去只是增加了冗余码。

下面使用范德蒙矩阵其实是为了保证这个矩阵任取n*n的部分可逆。

解码原理

根据上面的编码方式，我们可以很容易理解他的解码方法。对于编码后的数据块(b1,b2,...,bn,c1,c2,...,cm)，只需要任取其中的n个数据块，假设为(ba1,ba2,...,bax,cb1,cb2,...,cby)其中x+y=n，再用fi表示编码过程中那个矩阵的第i行。显然，下面的等式一定成立：

这样一来，我们就可以把中间的数据矩阵解出来了。

计算域

上面的方法理论上是能够做到数据冗余处理的，不过由于作为一种编码技术，RS编码需要处理的是特定长度的二进制数据，然而求矩阵逆的过程是在实数域内进行的。显然特定长度的二进制位是无法准确描述实数的。因此RS编码的计算域采用的是能够用二进制位精确编码的伽罗华域GF(2^n)。这个域的特性就是非常适合处理[0-2^n)范围内数据的四则运算，而且这里的四则运算大都通过位运算处理，效率比较高。实际生产中由于数据的量会比较大，为了加快整个计算的过程，通常会采用离散傅里叶变换(DFT)及其逆变换来进行编码实现。

重要特征

由于RS编码采用的是伽罗华域GF(2^n)，那他就有一个很有趣的特点，那就是对于数据b_1,b_2以及其分别对应的冗余码c_1,c_2，我们可以迅速的知道对于数据b_1\otimes b_2，他的冗余码就是c_1\otimes c_2(\otimes 表示异或)。

这一点其实很好理解，根据之前的编码过程，我们很容易知道对于实数域，如果数据b_1,b_2分别对应的冗余码是c_1,c_2，那么数据b_1+ b_2的冗余码就是c_1+ c_2。而现在的运算域是伽罗华域，在伽罗华域中加法做的就是异或操作。

参考资料

Reed Solomon纠删码 里德-所罗门码(RS 码) 简介 Finite Field Arithmetic and Reed-Solomon Coding