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

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

HPに行く

これは6月10日の分の内容です。

誤り訂正符号についてと平面上に奇数の距離をもつ4点集合についてやりました。

誤り訂正符号

とは、離れた距離の場所に電子信号を送るときに含まれるノイズを

いかに小さくすることができるか？という話です。

たとえば、0と1の列からなるような電子信号が送られたとき、

ある桁の数値が途中で何かの衝撃があって0を1として送られたとした時に、

受け取った側で何らかの操作をして、その間違い1を0に直すシステムです。

どうしてそのようなことができるのでしょうか？

例えば、マトウセクの本ではabcdの列を、aaabbbcccddd

に送るとしたら、

110000101111のように送られてきたものを直す時、(おそらく間違いは

少ないだろうから)3つずつの桁の中で多い方が正解と判断し、

111000111111

を送りたかったものとして直します。

このとき、1011というデータが送られたことになります。

このように、多少の間違いがあってもそれを正しいと思われる
ワードに訂正するシステムを誤り訂正符号といいます。

実は、このような誤りを訂正符号のためには、
4 bitの情報をわざわざ12 bitにして送る必要はありません。
もっと少ないbit数で十分です。

実は7 bitにしておけば、誤り訂正符号を作ることができます。

情報abcdに対して、たった3digit の情報efgを付け加えることて

abcdefg として送ることで謝り訂正符号を作ることができます。

まず、このような情報の列のことをワードといいます。

アルファベットの集合を$S$ と書けば、$n$ 桁のワードの集合は $S$ の $n$ この

ペア(直積)の集合であり $S^n$ とかくことができます。

今、$S$ として2元体 ${\mathbb F}_2$ (0,1の2つからなる体)とします。

${\mathbb F}_2^7$ につぎのように誤り訂正符号を構成します。

e=a+b+c

f=a+b+d

g=a+c+d

としますと、例えば1011というワードは、

1011001

というワードとして送られます。

このように最初の4つのワードを任意に与えれば自動的にのこりの3つのワードが
決まるので、

0,1の7個の任意の列は全部で $2^7=128$個ありますが、その中でたった7桁のワードとして
正しく送られなければならないものは次のたった16個の列のみです

$$C=\{0000000,0001011,0010101,0011110,0100110,0101101,0110011,0111000,1000111,1001100,1010010,1011001,1100001,1101010,1110100,1111111\}$$

これらをコードと呼ぶことにします。

ポイントは、どんなコードを持ってきても、少なくとも3つのbitを変えないと他のコードにならないということです。

ワード $w\in {\mathbb F}_2^7$ に対して $w$ のあるbit を1つ変えることで得られる他のワード $w’$
が得られたとします。このとき、$w$ と $w’$ の間に橋を掛けます。

このようにして ${\mathbb F}_2^7$ のすべてのワードに対して橋をかけます。

1つのグラフだと考えることもできます。

そうすると、あるコード $a$ のうちちょうど3つのbitを変えて他のコード $b$ に

なったとします。そうすると、$a$ と $b$ の間に2つのワード $x,y$ を通って

橋が $a, x,y,b$ のように橋が結ばれることになります。

もし、情報を送ったとき、$x$ として送られてしまった場合、
それを $a$ として直し、$y$ として送られてしまった場合、$b$ として直すことで一意的に近くのコードを直すことができます。例えば、$x$ に対してほかの直し方があるとすると、

$a,x,c$ のようにコード $a,c$ が橋でつながることになり、

3つ以上でdigit を変えないと他のコードにならないということに矛盾します。

よって、ワードを直せるとしたら一意的にコードを選ぶことができます。

注意しなければならないこととしてこのようにして直した

コードが直したかったものに本当になっているかどうかは保証はありません。

もしかして、1つ直すだけではなくて、4つ直さないとならないものかもしれません。

ただ、そのようなものはそんなに多くはないだろう

と考えるのです。

距離空間を用いて

このことを距離空間の言葉でいい直すことができます。

ワード全体に、次のような距離を入れるのが自然だと思うでしょう。

$w_1,w_2$ をワード $S^n$ の要素とします。
$d(w_1,w_2)$ をその桁のうち、異なる桁の個数とします。

例えば、

$d(0001011,0010101)=4$ となります。

そうすると、$d$ は距離の公理を満たしワード全体は距離空間になります。

距離空間とは、以下の性質を満たす関数

 $d:X\times X\to {\mathbb R}_{\ge 0}$ を持つ集合 $X$ のことです。

任意の $\forall x,y,z\in X$ に対して、

(1) $d(x,y)=0\Leftrightarrow x=y$

(2) $d(x,y)=d(y,x)$

(3) $d(x,y)+d(y,z)\ge d(x,z)$

を満たす。
この関数のことを距離関数と言います。

先ほどの $d$ もこの性質を満たすことをチェックしてください。

コード$C\subset S^n$ が $t$ 個の誤りを直すというのは、

$\forall u\in S^n$ に対して、$d(u,v)\le t$ となる $v\in C$ となる元が高々1つ存在する
ことを言います。

また、$d(C)=\min\{d(u,v)|u,v\in C,u\neq v\}$ とします。

このとき、以下が成り立ちます。

補題

$C\subset S^n$ が $t$ 個の誤りを直すことと、$d(C)\ge 2t+1$ ということは

同値である。

この証明は簡単なので証明してみてください。
こちら(リンク)にもその証明を載せています。

先ほどの例に戻ります。

このとき、$d(C)=3$ であることから、

コード $C$ は$t\le 1$ であることがわかります。

つまり、このコードは高々1個誤りを直すことができるということになります。

コードの生成

また、どのようにしてコードを作っていたかというと、

ワードの集合 ${\mathbb F}_2^n$ は、ベクトル空間を成しており、

情報 $v=abcd$ はベクトル $(a,b,c,d)$ とみなすことができます。

それをコード $w$ にするには、

生成行列 $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}=(I_4|A)$ を用いて、

$w=G^t\cdot v$ のように書くことができます。

送りたいワードからコードを作るのに線型写像を用いています。

よって、コード全体の集合は、ベクトル空間をなします。

つまり、$L_{G^t}$ を $G^t$ による左からの積とします。

このとき、$C=\text{Im}(L_{G^t})$ となります。

線形写像の像の集合はベクトル空間であるので

特に $C$ にベクトル空間になります。

よって、$w\in {\mathbb F}_2^7$ が $C$ の元であるか

判定するのは、ある連立方程式 $P{\bf x}={\bf 0}$ の解であることがわかります。

この $P$ のことをパリティチェック行列と言います。

パリティチェック行列は、具体的には、$P=(-A^t |I_3)$ とすることで得られます。

なぜなら、$P\cdot G^t= (-A^t|I_3)\begin{pmatrix}I_3\\A^t\end{pmatrix}=-A^t+A^t=O$

なり、任意の $G^t$ の像の元 $w$ は、$P{\bf w}={\bf 0}$ を満たします。

平面上に奇数の距離を持つ4点は存在しない

これもマトウセクの本の中の話です。

表題の通り、${\mathbb R}^2$ の中の4点で、そのそれぞれの距離

が奇数となるような点が取れないという定理を証明します。

こちら(リンク)にも記事を書きました。
ちなみに、3点であれば、そのような3点はすぐ作れます。
ただし、三角不等式を満たさなければなりませんが。

そのような4点が取れたとして、矛盾を導きます。

1つの点を固定して、その点を原点として、残りの平面上の

${\bf a}.{\bf b},{\bf c}$ を用いて考えます。

そのとき、内積 $\langle {\bf a},{\bf b}\rangle, \langle {\bf b},{\bf c}\rangle, \langle {\bf b},{\bf c}\rangle$ の2倍も整数であり、$1\bmod 8$ となることが重要です。

例えば、$2\langle {\bf a},{\bf b}\rangle=||{\bf a}||^2+||{\bf b}||^2-||{\bf a}-{\bf b}||^2$

となるからです。

${\bf a},{\bf b},{\bf c}$ のグラム行列の2倍が正則になることがわかり、

一方、グラム行列の作り方から正則にならず、矛盾が導かれます。