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

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

HPに行く
manabaに行く

来週(5/29)は休講ですので、今週(5/22)はレポートを出しました。

レポートは、数学の問題を解くということではなく、

MatousekのＭiniature 5の要約を作ってくださいということです。


要約ということは...

外書輪講の授業中によく言っていますが、セミナー発表は英文和訳ではないということです。
つまり、ここは英語科でもなんでもなく、筆者の気持ちになって文脈を読み取るとか
言外の意味をしるとかそのようなことは想定されていません。

むしろ、論理的に筆者の数学のアイデアをわかりやすく説明をするという

科学的なアクティビティです。

Miniature 5の内容について

これは、簡単にいえば符号理論の話です。
符号理論(coding theory)とは、Wikipedia(符号理論)にあります。

何か情報を相手に送信し、それを受信をしたり、CDのように書き込まれた情報を
読み取ったりするときに、以下に書くように、一度符号(code)と呼ばれる
列に変換してから送ります。どうして、情報をそのままにして送らないのか？
は以下のような理由があります。

情報は電気信号、つまり電気のオンとオフの状態として送ります。
つまり、０と１からなる数字を電気信号として送るのです。
デジタル機器やパソコンなどにも0,1からなる数字とその電気信号が使われています。

しかし、このような信号を用いて大量の情報を送るとすると、経験上、
必ずバグなど間違った情報が入ったり、間違った情報が送られてしまうことがあります。

例えば、計算機で正しいプログラムを組んで計算を走らせても、
途中にバグが見つかりプログラムがストップしてしまったり、
CDの細かな傷のために、再生できないということにもなります。

毎回毎回プログラムが止まったり、買ったばかりのＣDが聞けないということだと
話になりません。
そこで、たまたま間違っが情報がはいっても、それが自己修正能力を兼ね備えた
プログラムであれば、間違った信号を直しながら作業を続けることが
できるはずです。この自己修正のメカニズムが誤り訂正符号理論が必要となるのです。

そのアイデアとして、バグ修正のために、オリジナルのメッセージに
一旦冗長なメッセージ(少し長めのコード)を含ませておいて、
それを同時に送り、受信先でその冗長コードから
もとのオリジナルのメッセージを切り取って受信するという
方法がとられます。訂正のために付け加えた余分なコードの
ことをここでは訂正コード(訂正ディジット)ということにします。



日常的に我々が行っているバグ修正は、例えば言語です。
アルファベットやひらがななどで書かれた文章に誤植があったときに、
前後関係から、また、辞書に載っている単語の中でという縛りの元、
ほぼ一意に誤りを直すことができます。

また、例えば、滑舌の悪い人の話を聞くときにも、話の内容や状況、
そのニュアンスや単語の縛りなどから、聞き取りにくいところを
補完しながら聞くことができます。

仮に、アルファベットの並び全てのパターンに何らかの意味をもつ単語にしておいた
とすると、間違えたり、聞き取りにくい時に、復元することがかなり困難になる
のはずです。そのようなバグ修正ができる範囲の文字の総数として
アルファベットの26文字が選ばれているともいえます。

言語能力が高い人というのは、この修正能力が優れていると言っても
よいかもしれません。


誤り訂正コードの話に戻します。冗長なコードを使ってどのように訂正されているのか
を考えます。下のマーカスの本の中で説明しているコードの例を用います。

次のような、８マスに入る０と１からなる数列(とうか行列)を考えます。
ここでは、２個の元からなる２元体 ${\mathbb F}_2$ からなる数と考えても良いです。
つまり、$1+0=1$ かつ、$0+0=0$ かつ $1+1=0$ を満たす足し算からなる数体です。

0	1	1
1	1	0
1	0

今、オリジナルの情報(伝えたい情報)は左上の４つの $2\times 2$ 行列 $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ とします。ここで、誤り訂正のための成分は、
各行の3つめと各列の3つ目です。つまり、(1,3) 成分の1、(2,3)成分の 0、
(3,1)成分の 1、(3,2)成分の 0 です。この数は、各行を足し算してできた値を
置いています。例えば、(3,2)成分の 0 は、上の (1,2)成分と(2,2)成分の1 から
$1+1=0$ となります。これらの４つのディジットは本当はなくても、４つの
文字を読めばよいはずなので、冗長です。
つまり、それらは訂正ディジットということになります。

しかし、例えばコードが間違って伝わると、

1	0	1
1	0	0
1	0

のようなコードも伝わってしまったりします。このとき、各行と各列の関係から
間違いコードであることが判別できます。さらに、間違いを一つだけ
修正できることも分かります。

この場合だと、
間違っている行は、2行目で、
間違っている列は、1列目になります。

なので、間違っているのは、(2,1)成分だということになります。
つまり、(2,1)成分の1を0に直せばよいということになります。
また、間違っているのが1箇所だけであれば、訂正ディジットを直せばよいということになります。


訂正したら完全に正しいメッセージになるか？
ここで分かって欲しいことは、間違いを訂正したものは、確実に正しいメッセージ
とはかぎらないということです。おそらくそこに間違いがあるだろうと
推定されるだけです。

例えば、上の例において、正しいコードに、
オリジナルのメッセージの部分の1と0を全て入れ替えたコード
(訂正ディジット同じまま)は４つも誤りがあるくせに、
そもそも間違いかどうかさえわかりません。

また、行と列全てにおいて間違いが発見されるとすると、
2箇所以上の誤りを含んでおり訂正できません。

ハミングの方法

上の方法では、4つの文字のメッセージに4つの文字を付け加えてやると、1つの
文字の修正ならできるということになります。

しかし、ハミングはそれより効率の良い方法を考えたのです。

それが今回読んでもらう話です。
そのアイデアが

• ハミング距離
• 線形代数

です。

まず、コードとはアルファベットの全ての並び(もしくは0,1の全ての並び)ではなく
その部分集合を指定したものです。
つまり、コードから外れてしまったものから本当のコードに復元する操作が符号訂正理論ということになります。


　ハミング距離とは、コードとコードのうち、アルファベットの違う部分の
数を数えたものです。n こまで訂正できる(correct n errors) とは、
間違いがあった(コードから外れた)ときに、その間違いコードから
推定される正しいコードで n 個のアルファベットまで訂正したものが
たかだか一つ存在するということです。
(もしなければ、一番近いコードにするか、もう一度送ってもらって比べるか？など
になります。)

　今の場合、コードとなりうるのは、${\mathbb F}_2$ 上のベクトル空間の、
部分ベクトル空間です。
そのベクトル空間の基底を並べた行列のことを generator matrixとよび、
その部分ベクトル空間を定めている係数行列のことをParity check matrixといいます。

書いてある通りそのような部分ベクトル空間を作るには、オリジナルのメッセージが
4であるのに対して、3つの訂正ディジットを用意すればよいということが
分かります。

さっきの最初の例と比べてみると、１つだけ、文字数が減っています。
つまり、送る量として節約できたということになります。


なお、このハミングが開発したコードはその修正能力の高さから、
彼の同僚は、特許をとって大儲けしようとしたようです。しかし、純粋数学者であった
ハミングは全く興味がなかったようですね。Marcusの本にも

Hamming was keen to get the new codes into print. However, because he was working for a commercial company and the codes clearly had very significant commercial implications, Bell Labs were not so eager to go public. They wouldn’t let Hamming release the details until they had got the codes patented. But Hamming was rather sceptical about whether it was possible to patent pure maths: ‘I didn’t believe that you could patent a bunch of mathematical formulas. I said they couldn’t. They said, “Watch us.” They were right. Things that you shouldn’t be able to patent-it’s outrageous-you can patent.’

と書いています。これを訳した日本語(下記の参考文献)

ハミングは、ぜひこの新たなコードについての論文をまとめたいと思った。しかし所栓は民間企業に勤める身であり、しかもこのコードは莫大な利益を生む可能性があったので、ベル研究所はこの件を公にしたがらなかった。まず特許を取って、それから詳細を発表させればいい。一方ハミングは、純粋数学で特許が取れるはずがないと考えていた。「数式の束で特許が取れるとは、思っていなかった。無理だっていったんだがね。連中は『まあ見てろ』といった。そして連中のいうとおりになった。特許を与えるべきではないものにまで特許が与えられるんだから、まったくひどい話だ。」

としています。

この話はさらに有名な後日談があります。
この特許騒ぎで、そのハミングの理論が世にでるのが遅くなった
ため、その理論から広がる数学的に大変興味深い発見のための
数学的な研究に完全に出遅れてしまいます。(下の参考文献を参照)。
これらの発見はもしかしたらハミングがしていたかもしれません。

ゴレイは、ハミングと共同研究者のシャノンの論文に書いたことに着想を得て
独立に符号の理論に到達し、研究成果を発表しました。

彼は、符号の理論を発展させ、ハミングさえも見つけられなかった、
符号理論と、24次元細密充填問題、リーチ格子、有限単純群などの関係を発見するのです。
その時見つかった符号は今ではゴレイコード(Golay code)と言われています。
ゴレイにしてみれば、長年温めて来た研究に対して、他の論文から着想を得ただけで、
学問の自由さからして、これは正当なクレジットだと言わざるを得ません。
もちろんハミングが最初に符号理論をやり始めたということにも異論はありません。

数学のこのような熾烈な競争はよくあることで、目の付け所というか、
センスというか、同じことをやっていても、
「あ、その方向があったか。思いつかなかった。」
という悔しい思いをすることは少なくありません。諦めずに考え続けることと、
さらにもう一歩だけ進める力が必要となるのです。
「こんなに面白いんだから何かできるに違いない！」というその人にしか見えない
特別な思いに他なりません。

1. Marcus du Sautoy, Symmetry: A Mathematical Journey,  Harper/HarperCollins
2.  マーカス・デュ・ソートイ(冨永星訳) シンメトリーの地図帳　(新潮文庫)