ガロア体の取り扱い

この例では、ガロア体の取り扱い方法を示します。誤り制御符号化にハミング符号とガロア体理論を使用した際の効果も示します。

ガロア体は、有限個の要素をもつ代数体です。 $2^{m}$ の要素をもつガロア体は、 $GF (2^{m})$ で示されます。ここで、m は [1, 16] の範囲の整数です。

ガロア体配列の作成

ガロア体配列は関数gfを使用して作成します。たとえば、ガロア体 $GF (2^{2})$ に要素 3 を作成します。

A = gf(3,2)

 
A = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)
 
Array elements = 
 
   3

ガロア体配列の使用

組み込み MATLAB® データ型のように A を使用できます。たとえば、ガロア体に 2 つの異なる要素を追加します。

A = gf(3,2);
B = gf(1,2);
C = A+B

 
C = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)
 
Array elements = 
 
   2

ガロア体の演算の例

ガロア体要素に対する算術演算の規則は整数の場合とは異なります。たとえば、 $GF (2^{2})$ では、3 + 1 = 2 となります。この表は、整数 0 ～ 3 のガロア体の演算と整数演算の違いを示しています。

+__0__1__2__3

0| 0 1 2 3

1| 1 2 3 4

2| 2 3 4 5

3| 3 4 5 6

MATLAB® でこのような表を定義します。

A = ones(4,1)*(0:3);
B = (0:3)'*ones(1,4);
A+B

ans = 4×4

     0     1     2     3
     1     2     3     4
     2     3     4     5
     3     4     5     6

同様に、ガロア体 $GF (2^{2})$ の加算表を作成します。

A = gf(ones(4,1)*(0:3),2);
B = gf((0:3)'*ones(1,4),2);
A+B

 
ans = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)
 
Array elements = 
 
   0   1   2   3
   1   0   3   2
   2   3   0   1
   3   2   1   0

ガロア配列での MATLAB 関数の使用

ガロア配列とともに使用できる MATLAB® 関数の一覧については、gf関数リファレンスページのガロアの計算を参照してください。たとえば、2 つの異なるガロア配列を作成し、関数 conv を使用して 2 つの多項式を乗算します。

A = gf([1 33],8);
B = gf([1 55],8);

C = conv(A,B)

 
C = GF(2^8) array. Primitive polynomial = D^8+D^4+D^3+D^2+1 (285 decimal)
 
Array elements = 
 
     1    22   153

関数 roots を使用すると、多項式の根を求めることができます。たとえば、多項式 C の根を求めます。結果には、根は多項式 A および B の元の値と一致することが示されます。

roots(C)

 
ans = GF(2^8) array. Primitive polynomial = D^8+D^4+D^3+D^2+1 (285 decimal)
 
Array elements = 
 
   33
   55

ハミング符号とガロア理論の使用

この節では、誤り制御符号化にシンプルなハミング符号とガロア体理論を使用する方法を示します。誤り制御符号は、情報ビットに冗長性を加えます。たとえば、(7,4) のハミング符号は、4 情報ビットにガロア体 $GF (2)$ の 4 行 7 列の生成行列を乗算することで、4 ビットの情報を 7 ビットのコードワードに割り当てます。関数hammgenを使用してこの行列を求めます。

[paritymat,genmat] = hammgen(3)

paritymat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat = 4×7

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

出力 paritymat はパリティチェック行列で、出力 genmat は生成行列です。情報ビット [0 1 0 0] を符号化するには、情報ビットにガロア体 $GF (2)$ の生成行列 genmat を乗算します。

A = gf([0 1 0 0],1)

 
A = GF(2) array. 
 
Array elements = 
 
   0   1   0   0

code = A*genmat

 
code = GF(2) array. 
 
Array elements = 
 
   0   1   1   0   1   0   0

この例では、送信の過程でこのコードワードに誤りが発生したとします。この例で使用されているハミング符号は、最大 1 ビットの誤りを訂正できます。1 番目のビットを 0 から 1 に変更して、送信に誤りを挿入します。

code(1) = 1

 
code = GF(2) array. 
 
Array elements = 
 
   1   1   1   0   1   0   0

パリティチェック行列を使用して、誤りのあるコードワードにパリティチェック行列を乗算することによって誤りの発生場所を特定します。

paritymat*code'

 
ans = GF(2) array. 
 
Array elements = 
 
   1
   0
   0

パリティチェック行列 paritymat を調べて、誤りを特定します。[1 0 0]' と一致する paritymat 内の列が誤りの位置です。この例では、1 番目の列が [1 0 0]' のため、ベクトル code の最初の要素に誤りが含まれていることになります。

paritymat

paritymat = 3×7

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

参考

関数

gf | hammgen