About 符号理論

ブログ「数学者の一人ぐらし」のカテゴリ「符号理論」に投稿された全てのエントリーです。新しいものから過去のものへと並んでいます。

前のカテゴリは確率と統計です。

他にも多くのエントリーがあります。メインページアーカイブページも見て下さい。

アーカイブ

メイン

符号理論 アーカイブ

2006年5月 7日

第4回

5月8日
連休明けでしんどいかもしれぬ

今日は、情報理論基礎でも取り上げたハミング符号のおさらい
シンドロームから誤りをみつけこれを訂正する問題を取り扱う
行列により誤り訂正符号をどのように生成したり、あやまり検出したり、これを訂正するのか
生成行列、パリティ検査行列の扱い方を復習する

図書館で見つけた本

ゼロからわかる数学数論とその応用
戸川美郎著
朝倉書店
シリーズ数学の世界
2500円
6章は暗号系について書かれている
予備知識は小学算数

2006年4月26日

第3回

ガロア体の要素は原始元でべき表現される。
拡大体の場合、既約多項式のゼロ点αをあらたに導入するが、このゼロ=αは
原始元になり、すべての要素はこのべきで書き表される。

2006年4月17日

第2回

誤り訂正符号とはなにか
整数環
多項式環
の四則演算
割ってあまりの世界でも割る数が素数でないと

にならない。

2006年3月30日

教科書

誤り訂正符号と暗号の基礎数理
笠原正雄
佐竹賢治
コロナ社
2100円
を用いる。竹内書店などで購入してください
符号理論については、2年で学んだ情報理論でのハミング符号あやまり訂正について復習になるが、
それ以外には、代数学にふれる。代数学については、
硲 文夫著 初等代数学 森北出版
硲 文夫著 代数学 森北出版
を読んでおくことで、自分で符号理論を作り直せるぐらい非常に望ましいが、授業を理解するためだけなら
代数学すべてをマスターする必要はなく、たとえば有本のホームページにある符号代数練習帳にあらかじめ眼を通しておくだけでよい。さらに暗号理論についてもふれるつもりであるが、これには整数理論、因数分解などが必要となる。
RSA暗号といわれる暗号にはこの因数分解をおこなうアルゴリズムが計算量的に困難であることを利用する。

2005年12月 7日

教科書について

今年度教科書
のほかに授業中プリントを配布しているが、ソースは

昨年度教科書:符号理論入門(平澤茂一・西島利尚共著)培風館

参考書:誤り訂正符号と暗号の基礎数理 (笠原 正雄 (著), 佐竹 賢治 (著), 映像情報メディア学会 (編集)

である。そのため記号の統一がなされていない。時間ごとにその説明をいちいち行っているので注意してください。

続きを読む "教科書について" »

BCH符号リードソロモン符号

ここまで巡回符号を扱ってきたが、これらの特別な場合として
原始元のべきを連続的に配置したパリティ検査行列を作る
このとき、最小多項式を複数組み合わせることにより、
それを反映したパリティ検査行列を用いれば、
2文字、3文字訂正と性能をアップさせるlことができる
2文字のエラー訂正については2次方程式を解くことになる
リードソロモンについても同じであるが取り扱う符号の表記は単に0,1だけでなく
原始元そのものが入る

2005年11月10日

テクニカルターム

原始元
GF(q)のすべての非ゼロ元をαのべき上で表現できるとき、αをGF(q)の原始元という

原始多項式
拡大体の原始元αを根として持つ素多項式

最小多項式
GF(q')をGF(q)の拡大対とする。βεGF(q')に対しm(β)=0となるGF(q)上の最小次数の多項式m(x)を
GF(q)上の最小多項式という

2005年11月 5日

最小多項式

生成多項式は、いくつかの原始元にたいする最小多項式をもとめ、
それらの最小公倍多項式から求められる。
最小多項式の意味の説明、計算方法
その演習を行う。

11月9日講義の説明

1)多項式の周期
生成多項式(原始多項式)が与えられたとき、これから作られる符号の大きさ(長さ)
nは、周期に等しくとられる。最初に、周期の計算方法を説明する
2)ベクトル表現、多項式表現、べき表現について説明する

続きを読む "11月9日講義の説明" »

2005年11月 1日

有限体の加減乗除、べき乗、原始元

整数全体では無限個の要素が出てくる。
コンピュータのレジスタは有限桁である。
符号は有限個だけで表現したい。
誤りを見つけ訂正するなど方程式をとくこと
つまり割り算ができるようにしたい。
このようなものを実現するため有限体を考察する。
有限拡大体については来週述べる。

続きを読む "有限体の加減乗除、べき乗、原始元" »

2005年10月26日

10月26日演習問題について

1番の組織符号はたいていの人が正解していました。
それに対して、2番の問題は間違えている人のほうが多かったです。
前回の説明をやはりそのまま書いた人が多かったです。
パリティ検査行列は生成行列に対して逆向きにベクトルを配列するようにしてください。
gの次数x(n-k)今の場合x8を情報多項式f(x)にかけてやります。
その結果
(11110101010110100)となります。情報ベクトル1101がいて後ろに00をつけてやります。

2005年10月20日

10月19日演習問題の解答に対するコメント

因数分解は思いの外困難な問題でした。6個の項に分解されます。(x+1)はすぐに見つかるのでこれが因数として書いていない物はbとしました。しかし、それ以外は完全には分解されていなくとも3項以上にかかれている物は正解としました。生成行列Gについては同じ間違いがたくさんありました。
巡回符号なので行を一個ずつずらしていくのだが、各行は独立でなくてはなりません。同じ行があってはいけないのです!

2005年10月19日

10月26日講義予定

1.巡回符号の作り方(復習)
2.巡回組織符号の作り方
3.パリティ検査行列とパリティ検査多項式の関係
4.双対符号
5.拡大ハミング符号
6.原始元とは

2005年10月17日

10.19の演習問題

10月19日の説明で、パリティ検査多項式からパリティ検査列への変換方法で
誤った説明をしてしまいました。次回、説明をやり直し、なぜそうなのか詳しく解説します。
改めて同じ問題を次回の課題でもやってもらいます。今回の採点ではそこので減点する
ことはありません。

2005年10月16日

先週と今週は、前期情報理論基礎の復習

先週と今週は、前期情報理論基礎の復習に当たる。
しかし、前期情報理論基礎では、特に証明という物をせずに来たが
符号理論で、その穴を埋める。数学は結果だけ知ってそれを使えばよいと言う立場もあろうが
証明を丁寧に読んだり、自分でもっと簡単な証明はないか考えたりすることは重要で
将来、暗号の生成などに携わる場合など、きっとやっておいてよかったと感じることができると思う。

「誤り訂正符号と暗号の基礎数理」
笠原正雄、佐竹賢治共著 コロナ社
を参考書としてあげておく。暗号理論には、整数理論が必要となる。

アーカイブ