数学外書輪講I(第8回)

[場所1E501（月曜日5限）]

HPに行く
manabaに行く

今回は

• ハミングの誤り訂正符号理論についてののこり
• 奇数町のクラブ(Miniature 3)
• 線形代数

について発表してもらいました。

生成行列とパリティチェック行列

ここで、文字(アルファベット)の集合を位数2 の有限体 $S={\mathbb F}_2$ としておきます。

メッセージをコード化するとするとき、

その元のメッセージにチェックディジットをいくらか付け加えることで

行います。線形コードを作るとき、その操作をある線形写像

$$c:{\mathbb F}_2^k\to {\mathbb F}_2^n$$

となるように行います。このとき、$c$ の像がコード全体の集合 $C$ となるのです。

送られた後元のメッセージとして戻さなければならいので、 $c$ は当然、単射です。

このとき、線形写像を行列によって表すと、

$$G=[E_k|A]$$

のようなブロック行列として表示されます。

ここで、$E_k$ は $k$ 次単位行列で、$A$ は何らかの $k\times (n-k)$ 行列です。

この行列 $G$ の $i$ 行は、$e_i$ をコード化したものものと見なせます。

ここで、$e_i$ は $k$ 次元の基本ベクトルで、$i$ 番目の成分だけ1 でそのほかが0 となる

ベクトルです。

この行列のことを生成行列と言います。教科書では、

$$G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{pmatrix}$$

のような $4\times 7$ 行列を取っています。

この４つの行ベクトル ${\bf w}_1$, ${\bf w}_2$, ${\bf w}_3$, ${\bf w}_4$

が $\text{Im}(c)$ の基底となります。($c$ が単射であったことを思い出してください。)

また、パリティチェック行列とは $C$ を解空間にもつ連立一次方程式を定める

行列をいいます。

$$P=[-A^T|E_{n-k}]$$

とおきます。ここで、$T$ は転置行列を表します。例えば今の場合、

$$P=\begin{pmatrix}1&1&1&0&1&0&0\\1&1&0&1&0&1&0\\1&0&1&1&0&0&1\end{pmatrix}$$

となります。

実は、この行列 $P$ は $PG^T=O$ となる行列になっています。

どうしてかというと、

$$PG^T=[-A^T|E_{n-k}]\cdot[E_k|A]^T=-A^TE_k+E_{n-k}A^T=-A^T+A^T=O$$

となるからです。

線形空間

$$\langle G^T{\bf e}_i|i=1,\cdots, k\rangle $$

と

$$\langle {\bf v}|P{\bf v}={\bf 0}\}$$

が一致することを確かめます。前者を$V_G$ とし、後者を $V_P$ とします。

$V_G$ の任意の元 ${\bf v}$ は $G^T{\bf a}$ として書き表されます。

ここで、${\bf a}\in {\mathbb F}_2^k$ なる数ベクトル空間です。

上記の示したことから、$PG^T{\bf a}=P{\bf v}={\bf 0}$ となります。

ですので、$V_G$ の任意のベクトルは、$V_P$ のベクトルだということがわかります。

集合の言葉を使えば、

$$V_G\subset V_P$$

ということになります。あとは、$V_P\subset V_G$ であることがわかれば、$V_G=V_P$

が言えます。

ここで、次元を数えることにすると、$\dim V_G=k$ であることは $G$ のランクを計算すれば

わかります。

また、$\dim V_P=\dim(\ker{P})=n-\text{rank}(P)=n-(n-k)=k$

となり、$V_G\subset V_P$ であることから、$V_P=V_G$ であることがわかりました。

つまり、$V_P=V_G=C$ であるのです。

問題は生成行列の作り方ですが、実は、チェックディジットを作るために、

$P$ として ${\mathbb F}_2^{n-k}$ の単位行列以外のベクトルを全て並べたものにしていました。

こうすると、最後に書かれているように、どこかで、一箇所転送ミスをしてしまうと、

そのミスがどこにあるかチェックすることがでます。

つまり、${\bf v}\in {\mathbb F}_2^n$ を送って $v’\in {\mathbb F}_2^n$ が届いたとします。

また、そのベクトルが せいぜい1 個以下の間違いが含まれるとします。

このとき、$P{\bf v}’$ を調べたとき、もしゼロベクトルではないものが得られたとすると、それが間違いコードであることが判明し、さらに、そのベクトルが $P$ の縦ベクトルの $i$ 番目に一致したとします。このとき、${\bf v}’$ の第 $i$ 成分が違うということがわかります。つまりそのベクトルを $1\to 0$ もしくは $0\to 1$ となおせば正しい ${\bf v}$ が得られることになるのです。

ハミングの原論文は 

• R.W. Hamming, Error-detecting and error correcting codes, Bell System Tech. J. 29 (1950), 147--160

ですが、あまり読む方法もなさそうですので、マトウセクも挙げている以下の文献

(FOCSの学会の予稿)を挙げておきます。マデュー・スーダンは著名なcomputer scientist

• M. Sudan, Coding theory: Tutorial & Survey, in Proc. 42nd Annual Symposium on FOCS 2001, 36-53
  http://people.csail.mit.edu/madhu/papers/2001/focs01-tut.pdf

奇数町のクラブ

次に Miniature 3を読んでもらいました。

この話に関連して、とりあえず、文献を挙げておくと、

• L. Babai, P. Frankl, Linear algebra methods in combinatorics with applications to Geometry and Computer Science

です。(P. Franklとは、日本人にも馴染み深いピーターフランクルのことですが....。)この文献の最初に
奇数町(文献には、偶数町も登場する)の話が出てきます。
この文献は、Babai, Frankl を検索すると出てきます。

話の内容は、こうです。


$n$ 人の市民がいる。市民はクラブ(集まりのこと)を許されているが、次のような規則がある。

• 各クラブに入る人数は奇数人である。
• ある２つのクラブに対して、共通して入っている人の数は偶数人でる。

このような規則があるとき、必ず、

クラブの数 $\le$ 市民の数

がいえる。

この定理を奇数町定理といいます。

これは${\mathbb F}_2$ 上の線形代数を使ってごく簡単に証明できます。

面白いことは、クラブの数を特に制限しているわけでもないのに、いつの間にか、

市民の数よりは多いクラブを作ることができなくなっている点です。

上のババイとフランクルの本を見るともっと面白い定理が沢山あるので

読んで見ると面白いと思います。