完全符号:もう1度

今回は動画&記事&課題をもって講義1回分とします。
内容は
 完全符号
です。

6月21日の講義で扱いました。
まずは復習の意味を込めて、
次の動画を視聴ください。

復習:完全符号

さて、なぜ完全符号を敢えて2回学ぶか。
それは、7月5日に行われた数学で最も権威のある「フィールズ賞」に起因します。

私のブログに解説記事を書きました。
というわけで、
 【こちら】
読んでください。

すごいでしょ。

以下、記事を読んだ前提で話を進めます。

「ハミング符号を拡張する」の意味は
 外符号として「ハミング符号」を内符号として「シングルパリティ符号」を
 組み合わせる
という意味です。

まず、外符号を使って符号化して、つぎに内符号と使って符号化します。

この場合、
 符号化前のビット数が4。
 外符号(ハミング符号)による符号化後のビット数が7。
 内符号(シングルパリティ符号)による符号化後のビット数が8。
となります。

ここで課題:
 拡張ハミング符号の符号語を全て書き出しなさい。
その際に、
 符号化前に4ビットと、符号語の対応を書くこと。
 外符号の符号化も、内符号の符号化も、講義で教えたものを用いること。
 (インターネット等で調べると、他のやり方が見つかる場合もある。
  この課題では、講義に沿った方法を重視する。)

記事の中で出てきた E8格子 の作り方を述べます。
今回の講義のゴールです。
こちらを理解するように手を動かしてみましょう。

E8格子とは、実数体上の8次元空間の点の集合です。
以下の特徴をもつ点全体として定義されます。
 次の条件を満たす
   整数ベクトル a の各成分を ルート2 で割った a / √2  。

 条件:各成分に対し奇数を1、偶数を0で置き換えたものが
    拡張ハミング符号の符号語である。

ルート2で割ることを忘れて、
整数ベクトルaが条件を満たすとは何か、
慣れていきましょう。

例えば、次の3つの整数ベクトル
 (0,0,0,0,0,0,0,0)、(1,1,1,1,1,1,1,1)、(0,0,0,1,1,1,1,0)
は拡張ハミング符号の符号語そのものなので
条件を満たします。
続いて、つぎの2つの整数ベクトル
 (2,2,6,10,100,-4,-90000,8888)、(2,-2,0,0,0,0,0,0)
は、偶数を0に、奇数を1に置き換えると、どちらも(0,0,0,0,0,0,0,0)となり
拡張ハミング符号の符号語なので条件を満たします。
しかし、つぎの整数ベクトル
(2,-2,0,0,0,0,0,11)
は、偶数を0に、奇数を1に置き換えると(0,0,0,0,0,0,0,1)となり
条件を満たしません。

課題
 上で列挙した16個の拡張ハミング符号の符号語それぞれに対して、
  偶数を0に、奇数を1に置き換えたらその符号語になるように
   整数ベクトルを16個作りなさい。

では、最後に。
フィールズ賞受賞者の マリナ・ヴィヤゾフスカさんの結果のE8版を。
上記で作った整数ベクトル(を√2で割らずに)の各点を中心として、
半径1のボールを配置します。
これが、
 8次元空間に半径1のボールを置くのが
 最も密度の高い方法
という定理です。

数学の最高の賞が、ハミング符号から学べるのは面白くないですか?