予備知識としてのGF(2n)

[] [] []


ガロア体(Galois Field)とは、加減乗除ができるもの(体とよぶ)のうち要素数が有限のものである。例えば、有理数,実数,複素数はふつうの加減乗除ができるので「体」をなすが要素数は無限である。要素数を有限におさめようとすると意外と難しく、学校で習うのは「加減乗除した結果がpを超えたらpで割った余りを取る(mod p)」という方法である。要素数がp個になるからGF(p)と表す。ここでpは素数でなければならない(∵pが素数でないと乗算でab=pとなるa,bがあり、ab=0(mod p)だから除算1/a,1/bができず不都合)。逆にpが素数であれば「体」をなすらしい。

デジタル回路でよく出てくるのはGF(2n)というものである

 

GF(2n)

GF(p)

要素

nビットのベクタ a[n-1:0]

整数 0,1, ... ,p

加算

ビット毎にXOR

(減算は加算と同じになる1+1=0)

mod pの加算

(普通に加算してpで割った余りを取る)

乗算

mod g[n:0]の乗算

(加算をXORとして普通に2進数の乗算をしてnビットを超えたらg[n:0]で割った余りを取る)

mod pの乗算

(普通に乗算して pで割った余りを取る)

条件

g[n:0]は規約でなければならない

pは素数でなければならない

要素は0,1を係数とする(n-1)次多項式で表すのが一般的だが、本稿では係数のベクタ表記(2,16)も使うことにする。

多項式表記

ベクタ表記

a(x)= a[n-1] xn-1 + ... + a[0] x0

) x3 + x + 1

a[n-1:0]

) 1011 (2)

_____b  (16)

要素数を有限に抑えるため

・加算は桁上がりがないXOR(1+1=0)にする

・乗算はビット数が増えてしまうのでg[n:0]で割った余りを取る

Verilogで書くと、乗算 p[m+n:0]=a[m:0]*b[n:0]

for(i=0; i<=n; i++)

   if(b[i]==1) p = p ^ (a[m:0] << i)

余り r[n-1:0]=c[m:0] mod g[n:0]

r[m:0] = c[m:0]

for(i=m; i>=n; i--)

   if(r[i]==1) r = r ^ (g[n:0] << (i-n))

例)3 * 3 = 5;  5 mod 7 = 2;

   11

*) 11

  ---

   11

  11

  ---

  101

 

     ----

111 ) 101

      111

     ----

       10

◇◇

GF(p)pが素数でなければならなかったのと同様に、GF(2n)g[n:0]は既約でなければならない。

試しにn=3ビットで既約なg[3:0]をさがすと2つある(LSB=0(10)で割り切れるので除いた)

  (1001)=(111)*(11)

  (1011)  既約

  (1101)  既約

  (1111)=(101)*(11)=(11)*(11)*(11)

乗算してみると、g[3:0]が既約のときは結果がダブること(a*b=a*c)はなく大丈夫。

g[3:0]が既約でないと結果がダブること(a*b=a*c)があるので不都合。

 

◇◇◇

補足 − 「体」のもう少しちゃんとした定義

加算(可換)と乗算が定義されていて

(1)加算,乗算ともに結合則が成り立つ

(2)加算,乗算ともに単位元がある

(3)全要素に対して加算の逆元がある (減算ができる)

(4)ゼロ以外の要素に対して乗算の逆元がある (除算ができる)

(5)分配則が成り立つ (これが加算と乗算を関係づけている)

要素が有限個という制約をもうけると

・要素数はp個かpn

・乗算は可換

でなければならないそうだが、デジタル回路ではビット(2n)AND-XOR(可換)しか使わないので気にしなくてよい。

「体」と似たものとして

「環」は除算ができなくてもよいもの、(4)がない

「群」は加算だけor乗算だけできるもの、(5)がない


[] [] []