RS纠删码算法实现需要伽罗瓦域和矩阵的一些知识。

1 伽罗瓦域的四则运算

提到伽罗瓦域（也称有限域），不得不提一嘴伽罗瓦Évariste Galois，非常传奇的一位法国天才数学家，现代数学群论的创立者，人们称之为伽罗瓦理论，21岁时死于一次决斗，关于伽罗域的基本概念和理论，可以参考《古典数学难题与伽罗瓦理论》。

我们都知道5除以2等于2.5，但在伽罗瓦域5除以2可以等于7也可以等于4，并且这是一套定义良好且封闭的体系，我们在生活中使用的基本是实数域内的运算，但对于编码和计算机来说，每个比特取到的值是不连续且有限的，伽罗瓦域/有限域正好可以适用这个场景。

有限域GF(2^w)上的四则运算，加减法比较简单就是异或运算; 乘除法，可以通过生成元+本原多项式生成，生成元是域上的特殊元素，生成元的幂次可以遍历域上的所有元素。假设g是域GF(2^w)上的生成元，那么集合{g0, g^1, g(2^w-1)}包含了域GF(2^w)上的所有元素,在生成过程中当元素值超过2^w-1，需要mod P(x)，P(x)是本原多项式，不同的本原多项式会产生不同的有限域

GF(2^3)有限域的加法表：

  +   1   2   3   4   5   6   7
  1   0   3   2   5   4   7   6
  2   3   0   1   6   7   4   5
  3   2   1   0   7   6   5   4
  4   5   6   7   0   1   2   3
  5   4   7   6   1   0   3   2
  6   7   4   5   2   3   0   1
  7   6   5   4   3   2   1   0

GF(2^3)有限域乘除法表 5 / 2 = 7, 选取本原多项式： x^3 + x^1 + 1

......
 2 * 7 = 5, 5 / 2 = 7, 5 / 7 = 2
 3 * 1 = 3, 3 / 3 = 1, 3 / 1 = 3
 3 * 2 = 6, 6 / 3 = 2, 6 / 2 = 3
 3 * 3 = 5, 5 / 3 = 3, 5 / 3 = 3
 3 * 4 = 7, 7 / 3 = 4, 7 / 4 = 3
........
 7 * 6 = 4, 4 / 7 = 6, 4 / 6 = 7
 7 * 7 = 3, 3 / 7 = 7, 3 / 7 = 7

G(2^3)有限域乘法表，选取本原多项式： x^3 + x^2 + 1

....
 2 * 4 = 5, 5 / 2 = 4, 5 / 4 = 2
 2 * 5 = 7, 7 / 2 = 5, 7 / 5 = 2
 2 * 6 = 1, 1 / 2 = 6, 1 / 6 = 2
 2 * 7 = 3, 3 / 2 = 7, 3 / 7 = 2
 3 * 1 = 3, 3 / 3 = 1, 3 / 1 = 3
 3 * 2 = 6, 6 / 3 = 2, 6 / 2 = 3
....
 7 * 6 = 5, 5 / 7 = 6, 5 / 6 = 7
 7 * 7 = 2, 2 / 7 = 7, 2 / 7 = 7

2 使用范德蒙德生成矩阵计算纠删码，8个数据块，2个校验块

  • 编码

  • 解码

假如D1，D5数据块丢失，需要通过D2,D3,D4,D6,D7,D8,P1,P2恢复

3 RS纠删码算法的特点

3.1 编码算法的关键在于构建生成矩阵

  • 柯西矩阵： 在理论上保证产生最优码
  • 范德蒙德矩阵：生成矩阵构造更为简单、快速

3.2 解码算法的关键在于求生成矩阵的逆矩阵

  • 伽罗瓦域运算：解决求逆矩阵时除法运算时在实数域无法整除的情况。

4 RS算法效率分析

4.1 编码算法

  • 柯西矩阵：O(n^2) , n为数据分片
  • 范德蒙德矩阵：O(n^2)

4.2 解码算法

  • 柯西矩阵：O(n^2) , n为数据分片
  • 范德蒙德矩阵：O(n^2)

4.3 求逆矩阵算法

  • 高斯-若当消元法：O(n^3)
  • 伴随矩阵法：(n!^2)