（转）存储系统中的纠删码（Erasure Codes）—有限域（三）

白丁

（转）存储系统中的纠删码（Erasure Codes）—有限域（三） [复制链接]

原文地址

有限域是纠删码中运算的基础域，所有的编解码和重建运算都是基于某个有限域的。在讲讲为什么纠删码不能基于一般常见的域（自然数域，实数域）之前，需要讲讲域的概念和有限域与其他域的区别。文章将以尽量简单的语言使得更多的读者能够看懂。

一、有限域的基本概念

1. 什么是域？

首先回顾下我们学习数学的历史：从刚开始接触数学时，我们首先学会一些符号（比如从1开始数到100，初中开始学习未知数x, y, z 等），接着开始学习基于这些符号的运算（加减乘除等），这些符号和运算就可以构成一个“域”。比如我们最早接触的是整数域，接着有理数域，然后在高中和大学还接触了虚数域，只不过当时老师没有告诉你这些是域而已。还有一些常见的数不构成域，比如自然数、素数、整数。

2. 域具有哪些性质？

在抽象代数中，域是一个非零的可交换环。 在域上可以进行我们常见的加减乘除算法，一个域具有以下性质：

• 加法和乘法的封闭性，加法和乘法结果还在域内
• 加法和乘法的交换律； a + b = b + a   和  a · b = b · a .
• 加法和乘法的分配律： a + ( b + c ) = ( a + b ) + c   和  a · ( b · c ) = ( a · b ) · c.
• 加法和乘法的分配律： a · ( b + c ) = ( a · b ) + ( a · c ).
• 存在加法和乘法的单位元素：a+0 = a 和 a·1 = 1（这里的0,1 不是自然数的0,1，代表着域上的加法单位元素和乘法单位元素）
• 每个域上的元素都存在其负元和逆元： a+(-a) = 0, a·(a -1 ) = 1
  

这些性质和我们平时遇到的许多运算性质相同，这是因为我们很多运算就是在域上进行的。

3. 什么是有限域（finite field）和无限域（infinite field）？

域中的元素时有限个，则该域是有限域；如果域中的元素是无限多的，则是无限域；我们通常学习和接触到的域都是无限域，因为它们更接近于我们的生活，比如有理数域，复数域。有限域的大小是素数（记作p）或者素数的指数幂（p q ）。有限域由数学家伽罗瓦最早提出的，一种有限域的构造方法即使由他提出的，也称作Galois Field，这样的域记作GF(p) 和GF(p q )。

4. 一个有限域的例子？

最小的有限域GF(2)，只包含加法单位元素（零元素）为0，乘法单位元素为1。它们运算规则如下，容易看出它们满足域的性质（+表示加法运算，·表示乘法运算，右下是运算结果）。

5. 纠删码为什么要选择有限域？

不止是纠删码，一般的编码方法都在有限域上进行，比如常见的AES加密中也有有限域运算。使用有限域的一个重要原因是计算机是进行数值计算，不能够精确处理无限域上的计算，比如有理数域和虚数域。计算机能够精确处理整数上的加法和乘法，整数却不能构成一个域。

在有限域上运算另一个重要的好处是运算后的结果大小在一定范围内，这是因为有限域的封闭性决定的。作为程序员，我们可以想象在一个无限域上的运算，分配两块空间保存两个运算数，却要分配多大的空间给结果呢？因为结果大小可能非常大，甚至超过运算器的缓存空间。

6. 如何构造一个有限域？

作为程序员，真的不用太过于关心一个有限域是如何构造的，这问题总体来说是数学家的问题，但是要实现一个有限域上的运算还是要知道某些域的构造（比如GF(2 w )）。

二、GF(2 w )

GF(2 w ) 是存储系统中纠删码所使用的域大小，GF(2 w ) 中有2 w 个元素。为什么选取的是GF(2 w )  而不是其他大小的域是由现代计算机存储、计算结构相关的。底数是2是因为现代计算机是二进制的。当w=8 时，域的大小是2 8 = 256，对应着一个字节的大小。这样域大小有利于数据的存储和计算。

常见的w 的大小有1/2/4/8/16/32。XOR 码对应的就是GF(2) （w=1），运算速度最快，其域上的加法等同于计算机中的异或运算，其域上的乘法运算等同于计算机中与运算。在w>1 时，有限域上的加法运算还是可以用异或运算代替，但乘法运算则不同于普通的乘法运算，下图给出了一个有限域GF(2 3 ) 中的乘法表（a×b = mult[a]）。

关于有限域上如何进行乘法可以参考这里： http://www.dullgull.com/2013/01/伽罗瓦域上的乘法/

有了加法和乘法就比较容易进行其他运算，比如除法和求逆元素。

三、GF(2 w ) 乘法表/对数表的构造方法

上节直接给出了乘法表，在这节中将介绍如何在给定的域GF(2 w )，使用本原多项式和生成元构造出该域的乘法表/对数表（对数表是一维表，保存的是一个数在域GF(2 w )上的对数和反对数）。

域中不可约多项式是不能够进行因子分解的多项式， 本原多项式 （primitive polynomial）是一种特殊的不可约多项式。当一个域上的本原多项式确定了，这个域上的运算也就确定了。本原多项式一般通过查表可得，同一个域往往有多个本原多项式。通过将域中的元素化为多项式的形式，可以将域上的乘法运算转化为普通的多项式乘法模以本原多项式的计算。比如g(x) = x 3 +x+1 是GF(2 3 )上的本原多项式，那么GF(2 3 ) 域上的元素3*7 可以转化为多项式乘法：

3*7(in GF(2 3 )) → (x+1)*(x 2 +x+1) mod g(x) = x 3 +1 mod x 3 +x+1 = x → 3*7 = 2 (in GF(2 3 ))

需要注意的是，系数为2 的整数倍会被约去。这样 有限域上任意两个数的乘法都可以通过本元多项式求得 ，且不用额外保存任何表，但这样多项式的运算对计算机十分不友好，实际系统中采用的较少。

生成元 是域上的一类特殊元素，生成元的幂次可以遍历域上的所有元素（域上的元素并不都满足）。假设c 是域GF(2 w )上生成元，那么集合{ c 0 ，c 1 ，……，c 2^w-1 } 包含了域GF(2 w )上所有非零元素。在域GF(2 w )中2 总是生成元。利用生成元遍历域上元素的过程可以创建域上的对数表.

下面的代码是Jim Plank 教授Jerasure 中生成域GF(2 w )上对数表的函数（作者做了一些简化易于理解），其中log_table[ww][ele] 和ilog_table[ww][ele] 是ele 在域GF(2 ww )上对数值和反对数值，b 初始化生成元的0次幂 c 0 ，一直运算到c 2^w-1 为止。

gfele_t galois_create_log_tables(int ww) {

int nw = 1 << ww;

int nwm = nw - 1;

int b;

int j;

log_table[ww] = (gfele_t *) malloc (sizeof(gfele_t) * nw));

ilog_table[ww] = (gfele_t *) malloc (sizeof(gfele_t) * nw))

for(j = 0; j < nw; ++j) {

log_table[ww][j] = nwm;

ilog_table[ww][j] = 0;

}

b = 1;

for(j = 0; j < nwm; ++j) {

log_table[ww] = j;

ilog_table[ww][j] = b;

b = b << 1;

if(b & nw) {

b = (b ^ prim_poly[ww]) & nwm;

}

}

ilog_table[ww] += nwm;

return 1;

}

其中

b = b << 1;
if(b & nw) {
    b = (b ^ prim_poly[ww]) & nwm;
}

计算的是b←b×2