首页 > BigData, Mathematics > Finite Field Arithmetic

Finite Field Arithmetic

[latexpage]
在分布式存储系统中,通常通过多副本的方式来保证数据的可靠性。Erasure编码,是分布式系统中用来在保证跟多副本同等可靠性的前提下,减少副本、节约成本的标准做法。有限域(Finite Field)上的四则运算是Erasure编码在分布式存储系统中应用的基础。今天这篇文章介绍一下有限域(Finite Field)及其上面的运算, 后续文章再介绍Erasure编码。

什么是有限域(Finite Field)

大小为$n$的集合,在其上的任何四则运算(加、减、乘、除)的结果仍在这个集合中,表示为$GF(n)$

有限域(Finite Field)有什么样的性质

对于有限域GF(n)中的元素A(0除外), 均存在:
1. $A+B=0$, $B$称之为$A$的加逆, $-A$(Addition inverse, 可以跟相反数据类比)
2. $A*B=1$, $B$称之为$B$的乘逆, $A^{-1}$(Multiplication inverse, 可以跟倒数类比)
由上面的性质可以推论,在有限域上的减法都可以转化为加法,除法都可以转化为乘法

$GF(n)$($n$为素数)有限域上的运算法则

对于$GF(n)$, 如果$n$是素数,可以这样来定义$GF(n)$,及其上的四则运算:
$GF(n) = {0, 1, 2, \dots, n-1}$
加: $A + B = (A + B) \mod n$
减: $A – B = (A + (-B)) \mod n$
乘: $A * B = (A * B) \mod n$
除: $A / B = (A * B^{-1}) \mod n$


下面举几个$GF(3)$的例子:
\[
\begin{center}
\begin{tabular}{|l|l|l|l||l|l|l|l|}
\hline
\multicolumn{4}{|c||}{Addition} & \multicolumn{4}{|c|}{Multiplication} \\
\hline
Add & 0 & 1 & 2 & Multiply & 0 & 1 & 2 \\
\hline
0 & 0 & 1 & 2 & 0 & 0 & 0 & 0 \\
\hline
1 & 1 & 2 & 0 & 1 & 0 & 1 & 2 \\
\hline
2 & 2 & 0 & 1 & 2 & 0 & 2 & 1 \\
\hline
\end{tabular}
\end{center}
\]
下面是减法和除法的例子:
减法: $1 – 2 = 1 + (-2) = 1 + 1 = 2$
除法: $1 / 2 = 1 * 2^{-1} = 1 * 2 = 2$

对于$GF(n)$, 如果$n$不是素数, 用上述取模的方式来定义四则运算就行不通了(比如在$GF(4)$上$3/2$无解)

$GF(2^w)$有限域上的四则运算法则

1. 对于$GF(2^w)$上的加减法,我们可以这么定义:
加法: $A + B = A \oplus B$
减法: $A – B = A + (-B) = A \oplus (-B) = A \oplus B$
从上面的定义,很容易看出,加、减的结果任在$GF(2^w)$中,满足之前的假设

2. 对于$GF(2^w)$的乘法和除法,为了使其结果任在$GF(2^w)$中,我们需要定义一种规则来生成$GF(2^w)$, 然后在其上做运算:

  • 以$GF(2) = {0, 1}$为初始集合
  • 拿集合中的最后一个元素,乘以$x$
  • 如果所得的结果的度大于等于$w$, 则把该结果模上本源多项式(Primitive Polynomial), 所得结果就是下一个元素
  • 重复(2)(3)两步,直到集合中有$2^w$个元素

下面来构建$GF(2^2)$, 即$GF(4)$, $GF(4)$的本源多项式为$q(x)=x^2+x+1$:

  • 初始状态: $GF(4) = {0, 1}$
  • 下一个元素: $1 * x = x$, 度为1, 小于$w$, $GF(4) = {0, 1, x}$
  • 下一个元素: $x * x = x^2$, 度为2, 大于等于$w$, $x^2 \mod q(x) = x + 1$, $GF(4) = {0, 1, x, x + 1} $
  • 此时,$GF(4)$中已经有4个元素了,结束构造

下面来看乘法: (度数大于等于2的需要mod $q(x)$)
\[
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Multiplication} \\
\hline
Multiply & 0 & 1 & x & x + 1 \\
\hline
0 & 0 & 0 & 0 & 0 \\
\hline
1 & 0 & 1 & x & x+1 \\
\hline
x & 0 & x & x+1 & 1 \\
\hline
x+1 & 0 & x+1 & 1 & x \\
\hline
\end{tabular}
\end{center}
\]
做如下映射: 0->0, 1->$x^0$, x->$x^1$
然后,依次取每个多项式的系数, 得到如下表:
\[
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Multiplication} \\
\hline
Multiply & 00 & 01 & 10 & 11 \\
\hline
00 & 00 & 00 & 00 & 00 \\
\hline
01 & 00 & 01 & 10 & 11 \\
\hline
10 & 00 & 10 & 11 & 01 \\
\hline
11 & 00 & 11 & 01 & 10 \\
\hline
\end{tabular}
\end{center}
\]
再将上述表,转化为十进制:
\[
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{5}{|c|}{Multiplication} \\
\hline
Multiply & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 0 & 0 & 0 \\
\hline
1 & 0 & 1 & 2 & 3 \\
\hline
2 & 0 & 2 & 3 & 1 \\
\hline
3 & 0 & 3 & 1 & 2 \\
\hline
\end{tabular}
\end{center}
\]
下面我们来看几个GF(4)上乘、除法的例子:
乘法: $2 * 3 = 1$
除法: $2 / 3 = 2 * 3^{-1} = 2 * 2 = 3 $

从上面的例子中,我们可以总结出$GF(2^w)$上的乘法法则(除法可以转化为乘法):

  • 将要乘的两个数先转化为$w$位的二进制
  • 将二进制分别都转化为对应的系数基于$GF(2)$的多项式
  • 将两个多项式相乘,相乘的结果如果度大于等于$w$, 将结果mod本源多项式$q(x)$
  • 将上面得到的多项式再转化为对应的二进制
  • 将上面得到的二进制再转化为对应的十进制,所得就是计算结果

下面我们来看一个$GF(16)$上的例子,$GF(16)$上的$q(x)=x^4+x+1$:
\[
\begin{split}
\begin{aligned}
5 * 6 &\\
& = 0101 * 0110 \\
& = (x^2 + 1)*(x^2 + x) \\
& = x^4 + x^3 + x^2 + x \\
& = (x^4 + x^3 + x^2 + x) \mod q(x) \\
& = (x^4 + x^3 + x^2 + x) \mod (x^4 + x + 1) \\
& = x^3 + x^2 + 1 \\
& = 1101 \\
& = 13 \\
\end{aligned}
\end{split}
\]
对于除法: $A / B = A * B^{-1}$,我们可以通过查表得到$B^{-1}$,然后按上面同样的方法来计算

在实际的应用为,用上面的方法来计算还是比较麻烦的,尤其对于计算机程序来说。我们知道对数可以将乘法转化为加法,将除法转法为减法:
乘: $log(A*B) = log(A) + log(B)$
除: $log(A/B) = log(A) – log(B)$
对于上面的式子,我们在两边同时取2的次幂运算:
乘: $2^{log(A*B)} = 2^{log(A) + log(B)}$ => $A*B = 2^{log(A) + log(B)}$
除: $2^{log(A/B)} = 2^{log(A) – log(B)}$ => $A/B = 2^{log^(A) – log^(B)}$
由上面可以推出,我们构造出$GF(2^w)$上的对数表$gflog[i]$的反对数表$gfilog[i]$, 就可以将乘法转化为加法,将除法转化为减法。这里如果$gflog[i] = b$, 那么$2^b = i$; 如果$gfilog[i] = b$, 那么$2^i = b$

如下表所示是GF(16)上的对数表和反对数表:
\[
\begin{left}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\
\hline
gflog[i] & – & 0 & 1 & 4 & 2 & 8 & 5 & 10 & 3 & 14 & 9 & 7 & 6 & 13 & 11 & 12 \\
\hline
gfilog[i] & 1 & 2 & 4 & 8 & 3 & 6 & 12 & 11 & 5 & 10 & 7 & 14 & 15 & 13 & 9 & – \\
\hline
\end{tabular}
\end{left}
\]
(注意: 本图中最后一列没显示出来,可以右键在新窗口中打开图片查看)
根据上表,我们来看几个乘除法的例子:
乘: $5 * 6 = gfilog[gflog[5] + gflog[6]] = gfilog[8 + 5] = gfilog[13] = 13$ (跟上面用多项式计算出来的结果一致)
除: $5 / 6 = gfilog[gflog[5] – gflog[6]] = gfilog[8 – 5] = gfilog[3] = 8$

关于对数和反对数表的生成,[3]中有给出具体的C代码,感兴趣的朋友可以查阅[3]。关于本源多项式,感兴趣的朋友可以查阅[2]。关于有限域上的运算中用到的多项式的乘除,感兴趣的朋友可以参考[4]。关于有限域具体是怎么应用到Erasure编码中的,然后又怎么具体应用到分布式存储系统中的,后续会写单独的文章来介绍。

参考资料

1. Finite Field
2. Primitive Polinomial
3. A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems
4. Finite Field Arithmetic

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.
您必须在 登录 后才能发布评论.