情報理論

対称鍵暗号系

http://is-education.naist.jp/Data/Syllabus/2010/TeachingMaterial/info-0006_1274259017.pdf 今日から暗号理論の内容。黒い感じの話が多いのであんまり好きになれないんだよなぁ、暗号理論。。。 平文 盗聴や覗き見から守りたい情報 中身が公開されたもの…

やや実用、研究的な話題

巡回符号 シャノンの通信路符号化定理 新しいタイプの誤り訂正符号 「実用的な」線形符号の模索 符号化、誤り検出、訂正は行列演算によって実行可能 性能を向上させるためには、符号長を大きくすると有利 規模の大きい線形符号が必要 生成行列、検査行列が大…

符号の性能評価

9回目。一限はお腹が減る。。。 色々な線形符号が存在 性能がよいものもあれば悪いものもあるので、性能を客観的に測れる指標が欲しい 最小ハミング距離や符号の重み分布を使った性能評価のやり方をやる ベクトル間の距離を定義してやる必要がある 常識的な…

線形符号と生成行列

復習 偶パリティ符号は線形符号だったら、奇パリティ符号は線形符号ではない 具体的な生成行列の生成方法の復習 p3の例。分かりやすい modに乗せて、排他的論理和で考える 先週の続き(誤り訂正符号)。 線形符号は 符号語集合がベクトル空間をなすような符号 …

情報を正確に伝える

今日から通信路符号化の話。信頼性の低い情報伝達媒体を介した情報通信を考えよう、という内容(効率化より、正確に伝えるというところにウエイトを置いてる)。 誤りが起きないようにするのがベストだが、全く起きないようにするのは現実的に困難 発想を変え…

LZ78方式符号化をRubyで実装、を改良

Trieちゃんと使ったので、それなりの速度になりました。100MBくらいのテキストが40MBくらいまで縮んだかと思えば、2.8MBのテキストが2.6MBにしかならなかったりと圧縮したいテキストの性質によって圧縮率が全然違う感じでした。WEB+DB PRESS Vol.54によると…

LZ78方式符号化をRubyで実装

してみたはいいけど、激しく遅い。なんでかなーと思って調べているとWEB+DB PRESS Vol.54にid:naoyaさんのPerlでの実装が載ってた。位置どこどこに何があったかを記録しておくような辞書を容易しておくようだ。そりゃ遅くなるな。。。なお、辞書はTrieでやる…

ハフマン符号以外の符号化法

3部構成の1/3が今日で終了、らしい。前回の補足 ブロック化すると、どうして効率が良くなるか? 理想と現実の違いがあるから 理想的な符号語長は実数値、現実では整数値 頻繁に「悪化」して、ときどき「改善」される→理想と現実のギャップ 確率が大きくなると…

ハフマン符号の性能との限界、その他の符号化

前回の復習 4元のハフマン符号 何種類か木の作りかたがある => どの作り方がいいんだろう、どうやったら作れるだろう 仮想的な点を作って3k + 1個の節点を容易してあげればいいんじゃないんだろうか ハフマン符号の性能と限界 ハフマン符号は理解しやすくて…

情報をコンパクトに表現する

ハフマン符号まで。情報源符号化情報源に一番近いところで使われるべきもの。情報源から発生した通報(または通報の系列)を、記録系や処理系で利用可能な記号系列に変換すること。 通報を符号語(0 or 1からなる系列)に変換する 符号語の集合を符号という 一意…

情報量

基本的なエントロピーとか情報量の話。ブロック化のところとか、極限エントロピーの話とか知らなかった。マルコフ情報源での極限エントロピーの「求め方」は分かるんだけど、「なんでそれでうまくいくのか」が直感的に理解できなかった。来週は情報圧縮関係…