KnoNの学び部屋

落ち着きのない大学院生が専攻に関係ない(むしろそっちのけで)学んだコトを記録しておく場所

通信の数学的理論 まとめ(終)

気づいたら7月も終わりですね。

まだまだなんとか過ごせる暑さです。 

 

引き続き

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

全体のまとめ

をやります。

「訳者解説」を追いながら。

 

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

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

 

 

まえがき

◯通信とは「ある場所から他の場所に情報を伝えること」である。

→情報は、「出来事の生起確率」として評価できる。

→通信の目的は「記号列からなるメッセージを、受信者に、出来るだけ速く・正確に、通信路を通じて送り届けること」である。

 

◯シャノンの考える通信システムは次のようにモデル化される。

f:id:arcadia_1159:20140720185204p:plain

  1. 情報源:可能なメッセージの集合の中から、所望のメッセージを選ぶ
  2. 送信機:メッセージを信号に変換する
  3. 通信路:信号を伝達する
  4. 雑音源:望ましくない信号を加える
  5. 受信機:受信された信号をメッセージに変換する
  6. 受信者:メッセージを受け取る

 

Ⅰ 離散的無雑音システム

 まず「離散的」「雑音なし」「入力信号に何らかの制約がある*1」通信システムを考える。

 

◯離散的無雑音の通信路においては、送信可能な信号数の最大値{ \displaystyle N(T)}が通信路を使用する時間{ \displaystyle T}に対して指数関数的に増加し、この速度の増加{ \displaystyle \alpha}を通信路容量と定義する。

{ \displaystyle  N(T) = e^{\alpha T}}

 

◯離散的な値を取る情報源は、その生起する確率過程(特にマルコフ過程)を用いてモデル化することが出来る。

→情報源の生み出す情報量の尺度として、各メッセージが生起する確率によって定まるエントロピーを採用する。

{ \displaystyle  H = -\sum p_i\log p_1}

 

◯通信路容量Cを固定した場合、情報源のエントロピーHが小さければ小さいほど、情報は高速で伝達することが出来る。

定理9:情報源符号化定理

 情報源のエントロピー{ \displaystyle H}、通信路の容量を{ \displaystyle C}とする。

 送信メッセージが受信者に正しく伝送されるという条件(=あいまい度ゼロ)の下で、通信路上における平均伝送速度が{ \displaystyle \frac{C}{H}}に任意に近くなるように符号化することが可能である。

 しかし、{ \displaystyle \frac{C}{H}}を越えるような符号化はできない。

 →小さなエントロピーを有する情報源は、符号化を行った後の平均符号長を短くできる。

エントロピー(=情報源から出力されるメッセージの確率分布から計算される数学的な量)と、符号長の限界(=符号化という工学的な操作によって得られる量)が一致する。

 

Ⅱ 雑音のある離散的通信路

 次いで「離散的」「雑音あり」の通信システムを考える。

 符号化によってメッセージに冗長性を与えることで、通信の信頼性を向上できる。

 

情報の伝達速度Rを、「情報源のエントロピー」と「受信系列を得た時のエントロピー」の差によって定義する。

→伝送速度は「受信系列を得ることによって、どのくらい送信系列のあいまい度(エキヴォケーション)を減少できるか」ということを示している。

{ \displaystyle  R = H(x) - H_y(x)}

 

有雑音通信路の容量Cを、可能な伝送速度Rの最大値として定義する。

{ \displaystyle  C = \max(H(x) - H_y(x))}

  

◯伝送速度が通信路容量より真に小さければ、十分長いメッセージを一括して符号化することで(ここに遅延が生じる)、任意に小さい誤り率でメッセージを受信者に伝えることが出来る。

定理11:通信路符号化定理

 離散的通信路の容量を{ \displaystyle C}、離散的情報源のエントロピー{ \displaystyle H}とする。

 もし{ \displaystyle H \leq C}であるならば、ある通信路符号化法が存在して、情報源の出力は任意に小さい誤り率で通信路を通じて受信者に伝送できる。

 他方、もし{ \displaystyle H > C}ならば、あいまい度が{ \displaystyle H - C}以下になるような伝送は不可能である。

→誤り率とトレードオフ(二律背反)関係にあるのは、伝送速度ではなく、符号化のために遅延時間である。

通信路容量(=通信路の遷移確率と入力記号の確率分布によって数学的に定まる量)と、伝送速度の限界(=符号化という工学的操作から任意に小さい誤り率を得ることで定まる量)が一致する。

 

Ⅲ 連続情報

 転じて「連続的」「雑音あり」の通信システムを考える。

 

◯連続時間信号が帯域制限されていれば、加算無限個の離散時刻における標本値のみから元の信号を復元できる。

定理13:標本化定理

 { \displaystyle f(t)}{ \displaystyle W}を越える周波数成分を有していないとする。このとき、

{ \displaystyle  f(t) = \sum_{-\infty}^{\infty}X_n\frac{\sin \pi(2Wt - n)}{\pi(2Wt - n)}}

が成り立つ。ただし、

{ \displaystyle  X_n = f\left(\frac{n}{2W}\right)}

である。

連続時間信号を標本値の数列によって表すことが出来る

 

◯離散分布の場合にエントロピーが有する性質の大部分が、連続分布の場合についても成り立つ。

{ \displaystyle  H = -\int_{\infty}^{\infty}p(x)\log p(x)dx} 

 

◯ある帯域幅{ \displaystyle W}[Hz]に制限され、平均電力{ \displaystyle N}を有する雑音の中で、白色雑音*2と呼ばれる種類の雑音が最大のエントロピーを与える。

{ \displaystyle  H(x) = W\log {2\pi e N}}

 

Ⅳ 連続通信路

 引き続き「連続的」「雑音あり」の通信システムについて、その通信路容量をいかに定められるかについて考える。

 

◯情報の伝送速度は、連続的な通信路においても離散的な通信路の場合と同様に定義できる。

 ここから通信路容量についても同様に形式的な定義を与えることができる。

{ \displaystyle  R = H(x) - H_y(x) = \int_{\infty}^{\infty}\int_{\infty}^{\infty}P(x,y)\log\frac{P(x,y)}{P(x)P(y)}dxdy}

{ \displaystyle  C = \max R = \max\int_{\infty}^{\infty}\int_{\infty}^{\infty}P(x,y)\log\frac{P(x,y)}{P(x)P(y)}dxdy}

  

◯特に「送信信号と雑音が(確率的に)独立」「受信信号が送信信号と雑音の和になる」場合、送信信号xに対し受信信号yとなる条件付き確率{ \displaystyle P_x(y)}を送受信信号の差{ \displaystyle n = y- x}のみで定まる確率密度関数Qを用いて、{ \displaystyle P_x(y) = Q(n)}と表せる。

 このとき次の定理が成り立つ。

定理16:

 信号と雑音が独立であり、しかも受信信号が送信信号と雑音の和であるならば、伝送の速度は

{ \displaystyle  R = H(y) - H(n)}

であり、受信信号のエントロピーから雑音のエントロピーを減じたものである。

 また、通信路容量は

{ \displaystyle  C = \max H(y) -H(n)}

である。 

 

◯通信路の入力信号に制約があり、入力信号の平均電力が{ \displaystyle P}に制限された場合、帯域幅{ \displaystyle W}[Hz]、平均雑音電力{ \displaystyle N}を有するガウス性白色雑音通信路の通信路容量は、次にように与えられる。

{ \displaystyle  C = W\log\left(1 + \frac{P}{N}\right)}

→この種の通信路においては、伝送速度は「帯域幅{ \displaystyle W}」「信号-雑音比{ \displaystyle \frac{P}{N}}対数」に比例する。

 

Ⅴ 連続情報源のレート

 レート歪み理論と呼ばれる、連続時間信号の量子化の問題について考える。

 連続量と、それを量子化して近似した量について、その2値間の忠実度を用いることで連続信号のレートを定義する。

 

◯メッセージxに対し最終出力yが得られる確率密度を{ \displaystyle P_x(y)}としたとき、メッセージxと出力yとの間の忠実度を次式で定義する。

 ただし{ \displaystyle \rho(x,y)}はxとyとの間の歪み(あるいは距離)を表す関数。

{ \displaystyle  v(P(x,y)) = \int\int P(x,y)\rho(x,y)dxdy}

 

◯復元における忠実度が品質{ \displaystyle v_1}を有するために必要な情報の生成レートを次式で定義する。

 ただし最小化は、メッセージxと出力yの間の忠実度が{ \displaystyle v_1}以下になるような範囲で取られる。

{ \displaystyle  R_1 = \min\int\int P(x,y)\log\frac{P(x,y)}{P(x) P(y)}dxdy}

 

◯これらの定義の妥当性は次の定理によって示されている。

定理21:歪みを許した情報源符号化定理

 もし情報源が品質{ \displaystyle v_1}での生成レート{ \displaystyle R_1}を有するならば、{ \displaystyle R_1 \leq C}を満たす容量Cを有する通信路を通じて、望むだけ{ \displaystyle v_1}に近い忠実度で送ることが出来る符号化が存在する。

 これは{ \displaystyle R_1 > C}ならば不可能である。

→連続信号の量子化ビット数{ \displaystyle R_1}と、量子化によって生じる雑音{ \displaystyle v_1}トレードオフの関係にある。 

 

◯特に、電力{ \displaystyle Q}と帯域{ \displaystyle W}を有する白色雑音情報源において、その忠実度の評価を平均2乗規範で行う場合のレートは次式で与えられる。

{ \displaystyle  R_1 = W\log\frac{Q}{N}}

 

 

【今回の三行まとめ】

  • 通信路の効率を示す伝送速度は「情報源のエントロピーと途中で失われるエントロピー(=あいまい度)の差」として定義することが出来る。また通信路容量は伝送速度の最大値、つまり「あいまい度を最小化できる時の通信路の効率」として定められる。
  • 符号化の方法を工夫することで、通信における誤りを任意に小さくすることが出来る(通信路符号化定理)。しかしそのためには符号化のためにより長い遅延時間を必要とする。
  • エントロピーと符号長の限界」「通信路容量と伝送速度の限界」という「数学的な量と工学的な量」が一致することを示した点が、シャノンの情報理論の本質である。

 

【今回の宿題】

  • 「入力信号の制約」の理由

 

……これにて『通信の数学的理論』は終了です。

 読み始めた時は「わけわかんない!」って感じだったのですが、こうして見返し見てるとすらすらとまとめられて、意外と理解できているのかもしれない。

 理解すると尚更シャノンの議論に隙がないのが分かります。「シャノンの古典的な理論をひっくり返して、新しいコミュニケーションの原理を定義する!」とか考えてたのですが、やっぱり難しいようです。

 この理論を現実の"コミュニケーション"に当てはめるのなら、「情報源の確率過程の精緻化」「符号化の実態解明」「毎回通信路の条件が異なることをどう処理するか」あたりが考えられるでしょうか。

 特に「情報源」の正体をはっきりさせるのが重要そうです。

 

 明日は軽く「7月のまとめ」をして、明後日からは少しメインテーマから離れた思想的なテキストをやります。院試対策を兼ねて。

 

それでは

 

KnoN(140min)

 

シャノンの情報理論入門 (ブルーバックス)

シャノンの情報理論入門 (ブルーバックス)

 

 

 

 

*1:入力信号がなんらかの確率によって制限されるものでなければ、以下の議論が無意味になる。
実践的な意味においても、工学的な通信路は何らかの制限の元で設定される。

議論の大前提となるので以下の章では省略する。

*2:標本化定理において、各標本値が平均ゼロ・分散Nの正規分布に従って独立に定めることで得られる雑音