Codint Theory document 03
符号理論特論第3回補足資料

1.2 基本的な定義，続き

$GF(q)$ とは，要素数が $q$ 個のガロア体のことである． ガロア体とは簡単にいうと四則演算が定義されている有限体のことで あるが，この授業ではその中で $GF(2)$ を扱う．$GF(2)$ を理解するのは 簡単で，使える数字は 0 か 1，演算はまず加算と乗算を それぞれ普通の加算，乗算の計算を 2 を法として（2で割った余りを 結果とする）行う．

加算については， \[ 0+0=0,\\ 0+1=1,\\ 1+0=1,\\ 1+1=0 \] である．3 個以上の和も $1+1+1=3(\mod2)=1$ のように 2を法として加算すればよい．

乗算については， \[ 0\times0=0,\\ 0\times1=0,\\ 1\times0=0,\\ 1\times1=1 \] である．

減算は加法の逆元を加えることで行う．ある数の加法の逆元とは その数に加算すると加法単位元0になる数のことで， $0+0=0$ より $0$ の逆元 $-0$ は $0$, $1+1=0$ より $1$ の逆元 $-1$ は $1$である．これにより \[ 0-0=0+0=0,\\ 0-1=0+1=1,\\ 1-0=1+0=1,\\ 1-1=1+1=0 \] となる．$GF(2)$ では加算と減算が同じ演算になる．

加算，減算，乗算は結果的に普通の整数の演算を行なった後に 2で割った余りを求めればいいのだが，除算だけは注意が必要である． 除算は乗法の逆元を乗じることで行う．0以外のある数の乗法の逆元とは その数に乗算すると乗法単位元1になる数のことで， $1\times1=1$ より $1$ の乗法逆元 $1^{-1}$ は $1$ である．0の乗法逆元は 定義されず，0による除算も定義されない．これにより \[ 0/1=0\times1=0,\\ 1/1=1\times1=1 \] となる．

2元符号は$GF(2)$上の符号である．$[n,k]$ 2元線形符号は数学的には $GF(2)$，つまり 0 か 1 の $n$ 項組の全空間（長さ$n$ のすべてのビットパターン） である $F^n$ の $k$ 次元線形部分空間である．

$[n,k]$2元符号は $2^k$ 個のベクトルを符号語としてもつ． 全ての符号語からなる集合が符号である． 符号は全空間 $F^n$ の部分集合で，$[n,k]$線形符号の場合は $k$次元線形部分空間であるから $k$ 個の基底といわれる ベクトルの集合が存在し，基底の和で全ての符号語を作り出す ことができる．

例
[3,2]2元線形符号
$C=\{000, 011, 101, 110\}$ を考える． 全体空間 $V$ は 3 ビットの全空間なので $V = \{000,001,010,011,100,101,110,111\}$ である． 例えば 2 個のベクトル$\{101,011\}$ を基底とすると， 表3.1のように全ての符号語を作り出すことができる．

表3.1

一般に符号に対して基底のとりかたは複数ある．上の例では $\{101,110\}$ を基底としても同じ符号を生成できる．

表3.2

線形符号の基底を行とする行列をその符号の生成行列 という．表3.1の例では \[ G =\left( \begin{array}{rrr} 1&0&1\\ 0&1&1 \end{array} \right) \] が生成行列である．また，表3.2で利用した基底から \[ G' =\left( \begin{array}{rrr} 1&0&1\\ 1&1&0 \end{array} \right) \] も同じ符号を生成する生成行列であることがわかる． 一般に線形符号は生成行列を複数もつ．

次に下の $G_1$ を生成行列とする[5,3]2元線形符号$C_1$を考える \[ G_1 =\left( \begin{array}{rrrrr} 1&0&0&1&1\\ 0&1&0&0&1\\ 0&0&1&1&1 \end{array} \right) \] 符号語は 3 つの行 10011, 01001, 00111 の和で生成される．

$G_1$ の第1,2,3列 \[ \left( \begin{array}{r} 1\\ 0\\ 0 \end{array} \right), \left( \begin{array}{r} 0\\ 1\\ 0 \end{array} \right), \left( \begin{array}{r} 0\\ 0\\ 1 \end{array} \right) \] に着目する． 第1列 \[ \left( \begin{array}{r} 1\\ 0\\ 0 \end{array} \right) \] は他の第2,3列 \[ \left( \begin{array}{r} 0\\ 1\\ 0 \end{array} \right), \left( \begin{array}{r} 0\\ 0\\ 1 \end{array} \right) \] からどのような和を計算しても作ることができない． 同様に第2列を第1,3列の和で作ることもできないし， 第3列を第1,2列の和で作ることもできない． このようなベクトルの集合は独立であるという． 第4列まで入れると第4列は第1列と第3列の和で 作られるので独立ではなくなる．

情報ビット位置は独立な列の集合ならどこでもいいが 第1,2,3列が独立なのでこれを情報ビット位置とすることができる． 入力が 3 ビットなので $C_1$ は $2^3=8$個の符号語をもつ． 第1,2,4列などの組み合わせも独立なので 1,2,4 ビットめを 情報ビット位置とすることもできる．

生成行列が与えられると線形符号が決まるので，線形符号は 生成行列によって記述できるといえる．例えば上の例の符号 $\{000,011,0101,110\}$は \[ G =\left( \begin{array}{rrr} 1&0&1\\ 0&1&1 \end{array} \right) \] や \[ G' =\left( \begin{array}{rrr} 1&0&1\\ 1&1&0 \end{array} \right) \] で記述できる．

線形符号を記述するもう一つの代表的な方法として パリティ検査方程式で記述する方法がある． $C_1$ の最初の3列を情報ビット位置とすると，$C_1$ の 符号化器への入力と生成行列から出力を作り出すための和， 出力される符号語の対応は表3.3になる． 生成行列 \[ G_1 =\left( \begin{array}{rrrrr} 1&0&0&1&1\\ 0&1&0&0&1\\ 0&0&1&1&1 \end{array} \right) \begin{array}{r} \cdots g_1\\ \cdots g_2\\ \cdots g_3 \end{array} \] の第1行を$g_1$,第2行を$g_2$,第3行を$g_3$とする．

表3.3

$C_1$ の符号語を $(a_1,a_2,a_3,a_4,a_5)$ と書くと， 最初の 3 ビットを情報ビット位置としたので $a_1,a_2,a_3$は入力と同一である．

冗長ビット位置の $a_4,a_5$ は生成行列の 第4列，第5列に 1 がある行に注意すると以下の方程式 で入力から求めることができる \[ a_4=a_1+a_3 \] \[ a_5 = a_1+a_2+a_3． \]

$C_1$ の全ての符号語は上の方程式を満たし，上の方程式を 満たすベクトルは $C_1$ の符号語である．この方程式の組みを 符号$C_1$ のパリティ検査方程式という．パリティ検査方程式 を使って全ての符号語を記述することができる．例えば 入力が $a_1=1,a_2=1,a_3=0$であれば，パリティ検査方程式より $a_4= 1+0 =1$, $a_5= 1+1+0=0$なので符号語は$11010 \in C_1$ であることがわかる．

パリティ検査方程式は行列を使って表現することができ， それを検査行列という．$C_1$の パリティ検査方程式 \[ a_4=a_1+a_3 \] \[ a_5 = a_1+a_2+a_3． \] に対応する検査行列は \[ H_1 =\left( \begin{array}{rrrrr} 1&0&1&1&0\\ 1&1&1&0&1 \end{array} \right) \] であるが，これには内積を使った直交の概念を使う． 内積については前回の内積の説明 を参照すること．

ベクトル$\vec{u}$と$\vec{v}$について，内積$\vec{u}\cdot\vec{u}$ が$0$ であるとき，ベクトル $\vec{u}$と$\vec{v}$は直交 するという．2元ベクトルの場合は「直交する」とは， 共通に1をもつ場所の数が偶数個であることを意味する． 例えば $111000 \cdot 101010$ の場合，第1,3ビット目に 共通に 1 をもつので 2 箇所，これは偶数なので内積は 0 となり，直交する．

もしベクトル $(a_1,a_2,a_3,a_4,a_5) \in V$が パリティ検査方程式の第1式を満たすとすると \[ a_4=a_1+a_3 \] を満たす．移項し，$GF(2)$では $-1$ は $1$ であることに注意すると \[ a_1+ a_3 +a_4 =0 \ \ \ (3.1) \] を満たす．ベクトル $(a_1,a_2,a_3,a_4,a_5)$ と $H_1$ の第1行 $10110$ の内積は定義から \[ 1\times a_1 + 0\times a_2 + 1\times a_3 + 1\times a_4 + 0\times a_5 \] であり，式(3.1)が成り立つと0となる． つまりベクトル$(a_1,a_2,a_3,a_4,a_5)$ はパリティ検査方程式の 第1式を成り立たせる場合は $H_1$ の第1行と直交することがわかる． 同様にパリティ検査方程式の第2式 \[ a_5 = a_1+a_2+a_3 \] を成り立たせる場合は $H_1$ の第2行と直交することがわかる．

符号$C_1$はパリティ検査方程式の第1式，第2式をみたすベクトル $(a_1,a_2,a_3,a_4,a_5)$の集合であるから，検査行列$H_1$ の各行と直交するベクトルの集合であるといえる．これは ベクトルがパリティ検査方程式を満たすことと同義である．

このように，検査行列$H$を使って符号を記述することができる． 検査行列$H$で示される符号は，$H$の全ての行と直行する ベクトルの集合である．検査行列はあるベクトルが 符号語であるかそうでないかのチェックを行うときに便利である．

例
検査行列 \[ H_1=\left( \begin{array}{rrrrr} 1&0&1&1&0\\ 1&1&1&0&1 \end{array} \right) \] が記述する符号$C_1$がある．ベクトル $10101$は $H_1$ の第1行との内積は $1+0+1+0+0=0$， 第2行との内積は $1+0+1+0+1=1$なので全てとは直交しないので 符号語でない． ベクトル $10100$は $H_1$ の第1行との内積は $1+0+1+0+0=0$， 第2行との内積は $1+0+1+0+0=0$なので全てと直交することから 符号語であることがわかる．

$C$ が符号長$n$ の線形符号であるとき，$C$ の全ての要素と直交するベクトル からなる集合を $C^\perp$（$C$ の双対符号，デュアル）と書く． $C$ が $k$ 次元であれば $C^\perp$ は $n-k$次元になることが知られている．

課題3

検査行列 \[ \left( \begin{array}{rrrr} 1&0&1&0\\ 1&1&0&1 \end{array} \right) \] で記述される符号の全符号語を書け．
授業の6日後までにメールで提出せよ． メールの件名（サブジェクト）は CT03 とせよ．

課題提出の注意事項

• hiroshi@tokai.ac.jp宛に 大学のメールアドレスから提出せよ．
• メールに不調があったときの ためにCc:で自分宛にも送信せよ．