Reed-Solomon 编码算法-白红宇

Reed-Solomon 编码算法

阅读量：2398 次

发布时间：2019-05-10

本文共 1769 字，大约阅读时间需要 5 分钟。

Reed-Solomon (RS) 是一种纠错码算法, 纠错码是说对原始数据通过计算得到检验数据, 根据这些冗余的校验数据, 可以保证原始数据的可恢复性.

极大距离可分法(Maximun Distance Seperable codes, MDS) 是一种很常见的纠错码: 将原始数据分成等长的 n 份, 并根据这 n 份数据生成 m 个冗余的校验数据, 这样, 这 m+n 块数据中任意 m 块数据损失, 也可以通过剩下的 n 块数据计算得到. RS 是经典的 MDS 算法.

理论基础一: 有限域算法

有限域: 包含有限个元素的域, 又称为伽罗华域. 有限域的一个特征是一般包含 2^n 个元素, 且定义域内的加乘运算是封闭的, 即运算结果还在域内.

可以将有限域中的元素映射为 [0, 2^n - 1], 然后通过满足封闭性的典型算法来快速计算:

一个典型的有限域加减定义是异或运算:

11 + 7 = 1011 ^ 0111 = 1100 = 12

12 - 7 = 1100 ^ 0111 = 1011 = 11

一个典型的有限域乘除定义是对数和反对数运算:

以有限域[0, 2^4 - 1]为例的一个离散对数参照表:

function	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
log		0	1	4	2	8	5	10	3	14	9	7	6	13	11	12
ilog	1	0	4	8	3	6	12	11	5	10	7	14	15	13	9

3 * 7 = ilog(log(3) + log(7)) = ilog(4 + 10) = ilog(14) = 9

9 / 7 = ilog(log(9) - log(7)) = ilog(14 - 10) = ilog(4) = 3

理论基础二：Vandermonde 矩阵

法国数学家 Alexandre-Théophile Vandermonde 在十八世纪提出了行列式的概念, 用来解决线性方程组问题, 其中一个关键是 Vandermonde 矩阵, Vandermonde 矩阵具有如下的形式:

Vandermonde 矩阵有一个很重要的特性:

这个特性可以用数学归纳法证明出来, 此处省略.

在差值(interpolation)问题中, 假设在二维空间有 n 个点 (x1,y1), (x2,y2) .. (xn,yn), 希望得到一个多项式解:

这个多项式可以满足我们的当前条件:

实际上, 可以推演如下:

因为 A 的行列式不为 0, 所以 A 可逆, 所以上述多项式必然存在唯一解.

数据冗余与恢复

我们需要解决的问题: 假设有 n 份原始数据 D = (d1, d2 ... dn), 我们希望通过根据原始数据计算 m 份冗余 C = (c1, c2 ... cm), 并能容忍最大 m 份数据的丢失.

首先, 从 n 份数据计算 m 份冗余:

我们可以将 F 定义为 m x n 的 Vandermonde 矩阵, 令 (x1 = 1, x2 = 2, ... xn = n), 那么可以得到:

于是, 我们可以构造出一个如下的等式:

其中 A' 由一个 n 阶单位矩阵和 m x n 的 Vandermonder 矩阵组成, 所以 A' 的任意 n 行都线性无关, 组成的非奇异矩阵必然存在逆矩阵。

基于这一点, 我们删掉任意 m 行 (丢失 m 块数据), 都可以对剩下的 n 行数据求逆, 从而计算恢复出原始数据 D.

Reed-Solomon 算法示例

第一步, 计算方法和数据:

有限域: [0, 15], 乘除法参照前文离散对数参照表, 加减法参照前文异或操作

原始数据 D, Vandermonde 矩阵 F, 冗余数据 C

第二步, 构造等式:

第三步, 假设数据 D2 D3 C3 丢失, 那么可以通过下面的方式恢复出 D:

RS 算法理解与应用

RS 算法的本质是相比常用的多副本方式, 利用 CPU 换空间, 以获得数据的可用性.

RS 算法多个数据系统中都应用, 一个典型是 , facebook 在开源的 HDFS 上引入 (10, 4)RS 编码.

延伸阅读