Galois 域上的运算(规则)

OO~ posted @ 2013年10月28日 19:22 in 存储编码 , 7443 阅读

    考虑到存储编码中,矩阵等之间的运算都是在伽罗华域(Galois Field,GF,有限域)上进行的,所以要实现底层的运算库,必须了解 GF 上的运算规则。开始前,我们将字长设为 $w$ bit。

    GF 上的加法和减法运算比较简单,都是两个数值直接异或( XOR )。对乘法和除法运算,很多人可能会想到,首先按照十进制进行乘除运算,然后再将结果模上 $2^w$ 即可。这样做我们容易得到,GF 上的数值都是成对出现的,但是当 GF($n$) 中的 $n$ 不是质数时,不能构成 pairs,另外对类似于 $(3/2) \% 4$ 的运算时没有定义的,综合上面所论述的,所以 GF($2^w$) 上的乘除法运算不能简单做如上定义。

    GF($2^w$) 的乘除法运算规则使用到了线性代数中用最小多项式简化高次矩阵运算的理论,简单说来就是“除法原理”。我们定义 GF($2^w$) 上关于 $x$ 的多项式,即若 $r(x) = x + 1, s(x) = x$,则有 $$r(x) + s(x) = x + x + 1 = (1 + 1)x + 1 = 1$$

根据“除法原理”,有 $r(x) = q(x)t(x) + s(x)$,即 $r(x) \% q(x) = s(x)$ ($q(x)$ 除 $r(x)$ 的商是$t(x)$,余数是$s(x)$),同时,易知 $s(x)$ 的度($x$ 的最高次)要小于 $q(x)$ 的。

     我们设 $q(x)$ 是在 GF($2$) 上对应度为 $w$ 的本原多项式(最小多项式),则任意的 GF($2^w$) 均可以由 GF($2$) 下的多项式 $x$ 产生出。基本步骤是:

1. 给定一个初始集合 $\{0, 1, x\}$;

2. 将这个集合中的上一个元素,例如 $x$ ,乘以 $x$ ,如果得到的结果的度大于等于 $w$,则再将结果 mod $q(x)$;

3. 直到集合有 $2^w$ 个元素,此时最后一个元素乘以 $x$ 再 mod $q(x)$ 的值为 $1$。

    下面给出一个例子来说明,当 $w = 2$ 时,$q(x) = x^2 + x + 1$,对 GF($4$),最开始的集合是 $\{0, 1, x\}$,这个集合的上一个元素是 $x$,乘以 $x$ 得到 $x^2$,此时其度等于 $w$,所以 $x^2 \% q(x) = x + 1$;此时集合更新为 $\{0, 1, x, x + 1\}$;再将 上一个元素 $x + 1$ 乘以 $x$,得到 $x^2 + x$,其度数也等于 $2$,所以 $(x^2 + x) \% q(x) = 1$,此时可以结束这个过程,即 GF($4$)  为 $\{0, 1, x, x +1\}$。

    通过上面说明,只需要找到对应 GF($2^w$) 上的本源多项式 $q(x)$ (运算遵循 GF($2$)),则其即可通过 $x$ 代换得到,可以对应表示成:$$GF(2^w) = GF(2)[x] / q(x)$$

根据已有理论,根据不同 $w$ ,对应本源多项式为:

    在实际计算机中,都是使用二进制来运算,所以我们需要将 RS 码中的 GF($2^w$) 中的元素都映射到二进制上来:$s(x)$ 的元素 $x^i$ 对应到二进制位的 $i$ -th,例如上面的 GF($4$) 中,依次对应的是 $\{00, 01, 10, 11\}$。如下图给出 GF($16$) 的例子:

    通过上面系列对 GF($2^w$) 的分析,对应其上的乘法可以转换成多项式相乘后再 mod $q(x)$,问题得到了简化(多项式相乘时,各元素次数做的是加法)。因此,我们定义 RS 码上的元算时,先将二进制映射成多项式,再求模运算,再转换成二进制,这样一来,我们有两个映射表格 gflog(将二进制映射成多项式) 和 gfilog(对多项式进行运算,然后将结果转换成二进制),不同的 $w$ 对应不同的表格,表格中的元素是 $2^w - 1$ ($0$ 单独存在,没有哪个的次方等于 $0$)。如下图给出了$w = 4$ 情况下的两个表格:

    对应给出几个乘法和除法运算的例子:

7 * 9 = gfilog[gflog[7] + gflog[9]] = gfilog[10 + 14] = gfilog[9] = 10

13 / 11 = gfilog[gflog[13] - gflog[11]] =  gfilog[13 - 7] = gfilog[6] = 12

    

Avatar_small
OO~ 说:
2013年10月28日 21:01

这个生成的过程,要强调在 GF($2$) 的多项式运算,文中多次给出。这样最后进行简化的时候可以保持统一,无论 $w$ 怎么变化,$0 = (1 + 1) * y$,其中 $y$ 是任意的关于 $x$ 的多项式。

Avatar_small
OO~ 说:
2013年10月28日 21:02

囧,评论里居然没有 tex 的插件!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter