KnoNの学び部屋

大学に8年在籍した後無事に就職した会社員が何かやるところ。

通信の数学的理論 その2(後編)

Texはまだ無理です。 

というか明らかに未完成なんだけど、とりあえず置いておく。 

 

引き続き

通信の数学的理論 (ちくま学芸文庫)クロード・シャノン、2009)

Ⅰ 離散的無雑音システム

の後半をやります。

 

通信の数学的理論 (ちくま学芸文庫)

通信の数学的理論 (ちくま学芸文庫)

 

  前半では「離散的」「無雑音」の通信システムにおける、情報源のエントロピーの定義まで確認した。

 エントロピーの話を続けつつ、基本定理を確認し、全体の議論を行う。

 

 

情報源のエントロピー

 全体のエントロピーHに対し、各々の状態に対してのエントロピーHiが存在する。

 情報源のエントロピーは問題となっている状態の生起確率に応じて重みづけられたHiの平均として定義される。これが「文章の1記号あたりのエントロピー」である。

(式6) 

 

定理3:

 任意のε>0とδ>0に対し、あるN0が存在して、任意の長さN≧N0を有する系列は2つのクラスに分類される。

  1. 全体の生起確率がε以下であるような系列の集合
  2. 上記以外の系列の集合で、その全要素が次の不等式を満足する生起確率を有しているもの
    (式7)

 →Nが大きいとき、(式8)はほとんど確実に、ほぼHに等しい。

 

定理4:

 qが0でも1でもなければ、次式が成り立つ

(式9)

→log n(q)は、全体の確率がqになるような最も起こりやすい系列のみを考えたときに、系列を特定するのに必要なビット数である、とも解釈できる。

 

 次の二つの定理は「状態や状態間の遷移確率を参照せずに、HとH'(単位時間辺りのエントロピー)がメッセージ系列の統計から、極限操作によって直接決定できる」ことを示している。

定理5:

 p(Bi)によって、情報源から記号の系列Biが生起する確率を表す。そして、

(式10)

とする。ただし、和はN記号から成る系列Bi全てに渡って取られる。

 このときGNはNに関する単調減少関数であり、次式が成り立つ。

(式11)

 定理6:

 系列Biに続いて記号Sjが生起する確率をp(Bi,Sj)とし、pB(Sj)=p(Bi,Sj)/P(Bi)をBiのあとにSjが出現する条件付き確率とする。ここで

(式12)

とする。ただし、和はN-1記号からなるブロック(系列)Bi全てと記号Sj全てについて取られる。

 このときFNはNに関する単調減少関数であり、

(式13)

であり、(式14)がなりたつ。

 

 記号集合を同一に制限して得られるエントロピーの最大値に対する、情報源のエントロピーの比を「相対エントロピー」とよぶ。

→同一のアルファベットに符号化する際の最大の圧縮可能性を示す。

→1から相対エントロピーを引いたものが「冗長度」である。

 

符号化の操作の表現

定理7:

 有限状態の統計的情報源によって駆動された有限状態変換器の出力は、有限状態の統計的情報源であり、その単位時間辺りのエントロピーは、入力列のエントロピーに等しいかそれ以下である。もし変換器が非特異ならば、それらは等しい。

非特異=最初の変換器の出力に作用する他のある変換器が存在して、元の入力を復元する場合、前者の変換器は非特異であるという。

 

定理8:

 制約を持つシステムが通信路とみなされ、容量C=log Wをもつとする。ここで確率

(式15)

を割り当てる。ただしlsijは、状態iを状態jに導くs番目の記号の持続時間を表し、Biは

(式16)

を満足する。

 このとき、Hは最大になり、Cに等しい。 

 →遷移確率を適切に割り当てることによって、通信路上の記号のエントロピーを最大にし、通信路容量に等しくすることが出来る。

 

 

無雑音通信路に関する基本定理

 最も効率的な符号化について要求される通信路容量をHが定める、ということを証明し、Hが情報を生成する速度であるという解釈を正当化することを試みる。

 

定理9:

 情報がエントロピーH(ビット/記号)を持ち、通信路が容量C(ビット/秒)を有するとする。

 このとき、情報源の出力を通信路上において平均速度C/H-ε(記号/秒)で伝送するように符号化できる。ただし、εは任意に小さい数。

 しかも、平均速度がC/Hを越えるような伝送は不可能である。

→証明がいろいろと書いてあるがここでは省略

 

 通信の効率を上げるためには、通信路から変換器を通してみた情報源と、通信路のエントロピーを最大にする情報源とが同一の統計的構造を持たなければならない。

→通信路容量Cに対する実際の伝送速度の比として、符号化システムの効率を定義する。

 

 一般に、理想的な符号化を行うには変換器において長い遅延を必要とする。

→符号化する系列の確率とそれに対応する符号化の系列長との合理的な良い適合の為に時間が必要。

 

 

【今回の三行まとめ】

【今回の宿題】

  • 共に省略

 

 

……うーん、うすうす感じていたけれど、このテキストやっていてそんなに面白くない。

 アウトラインは知っているから新しい驚きはないし、かといってその証明を丁寧に追って行くには数学がめんどくさい。なによりブログ向きじゃない。

 やっててストレスがたまるくらいなら、別のアプローチの仕方を考えた方がいいかもしれない。

 

それでは

 

KnoN(120min)