最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

ガロア体の取り扱い

この例では、ガロア体の取り扱い方法を説明します。

ガロア体は、誤り制御符号化で使用される、有限個の要素をもつ代数体です。2m の要素をもつガロア体は GF(2m) で示されます。この例では、m は 1 ~ 16 の整数です。

ガロア体配列の作成

ガロア体配列は関数 GF を使用して作成します。ガロア体 22 に要素 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

ガロア体の演算

このガロア体では 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 1 2 3];
B = [0 1 2 3]'*ones(1,4);
Table = A+B
Table = 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 1 2 3],2);
B = gf([0 1 2 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 関数をガロア配列で使用できます。これを確認するために、配列をいくつか作成します。

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

これで 2 つの多項式を乗算できます。

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

多項式の根を求めることもできます (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 ビットの情報を 7 ビットの符号語に割り当てます。これは 4 ビットの符号語に 4 x 7 の行列を乗算することで行います。この行列は関数 HAMMGEN を使用して取得できます。

[H,G] = hammgen(3)
H = 3×7

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

G = 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

H はパリティ チェック行列で G は生成行列です。情報ビット [0 1 0 0] を符号化するには、情報ビット [0 1 0 0] に生成行列 G を乗算します。

A = gf([0 1 0 0],1)
 
A = GF(2) array. 
 
Array elements = 
 
   0   1   0   0
Code = A*G
 
Code = GF(2) array. 
 
Array elements = 
 
   0   1   1   0   1   0   0

送信の過程でこの符号語に誤りが発生したとします (ハミング符号が訂正できる誤りは 1 つのみであることに注意してください)。

Code(1) = 1   % Place a 1 where there should be a 0.
 
Code = GF(2) array. 
 
Array elements = 
 
   1   1   1   0   1   0   0

パリティ チェック行列 H を使用して誤りの発生場所を特定できます。符号語に H を乗算します。

H*Code'
 
ans = GF(2) array. 
 
Array elements = 
 
   1
   0
   0

誤りを見つけるには、パリティ チェック行列 H に注目します。[1 0 0 ]' と一致する H 内の列が誤りの場所です。H を見ると、最初の列が [1 0 0]' であることがわかります。つまり、ベクトル Code の最初の要素に誤りが含まれていることになります。

H
H = 3×7

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