ガロア体(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)がない