情報理論
イーサネットなどの通信路上の通信が情報理論構築の主な動機である。電話を使ったことのある人なら誰でも経験することだが、そのような通信路では正確な信号の再現に失敗することもよくあり、ノイズや一時的な信号の途絶などにより信号が識別不能となることがある。そのようなノイズの多い通信路でどれだけの情報を伝えることが期待できるだろうか?
離散的な通信路による通信を考える。X を転送されるメッセージの集合とし、Y をある一定時間内にその通信路経由で受信したメッセージの集合とする。ここで、 p ( y | x ) {\displaystyle p(y|x)} を x が送信されたときに y が受信される条件付き確率の分布関数とする。ここで、 p ( y | x ) {\displaystyle p(y|x)} がその通信路に固有の属性であるとする(この通信路のノイズの性質を表している)。
伝達情報量の基本特性は次の式で表される:
I ( X ; Y ) = H ( X ) − H ( X | Y ) {\displaystyle I(X;Y)=H(X)-H(X|Y)\,}
この意味は、Y を知っていれば、知らない場合よりも X の符号化で平均して I ( X ; Y ) {\displaystyle I(X;Y)} ビット節約できることを意味する。伝達情報量は対称的であるため、次のようにも表せる:
I ( X ; Y ) = I ( Y ; X ) = H ( X ) + H ( Y ) − H ( X , Y ) {\displaystyle I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y)\,}
関連する尺度として、自己情報量、自己相互情報量(PMI)、カルバック・ライブラー情報量、差分エントロピーなども情報理論では重要である。
関数 H を確率分布で表すと次のようになる:
H ( p ) = − ∑ i = 1 k p ( i ) log  p ( i ) , {\displaystyle H(p)=-\sum _{i=1}^{k}p(i)\log p(i),} ここで ∑ i = 1 k p ( i ) = 1 {\displaystyle \sum _{i=1}^{k}p(i)=1}
これの重要かつ特殊な場合を2値エントロピー関数と呼び、次のようになる:
H b ( p ) = H ( p , 1 − p ) = − p log  p − ( 1 − p ) log  ( 1 − p ) {\displaystyle H_{\mbox{b}}(p)=H(p,1-p)=-p\log p-(1-p)\log(1-p)\,}
2つの離散確率変数 X {\displaystyle X} と Y {\displaystyle Y} の結合エントロピーとは、単にその組 ( X , Y ) {\displaystyle (X,Y)} のエントロピーである。例えば、 ( X , Y ) {\displaystyle (X,Y)} がチェスの駒の位置を表すとする。 X {\displaystyle X} が行、 Y {\displaystyle Y} が列を表すとすると、その結合エントロピーとは、駒の位置のエントロピーを表す。数学的には次のようになる。
連続的なアナログ通信路のノイズは主にガウス雑音である。シャノン・ハートレイの定理。
2元対称通信路 (Binary Symmetric Channel, BSC)でバイナリ値の取り違えが発生する確率を p とする。BSCの通信路容量は 1 − H b ( p ) {\displaystyle 1-H_{\mbox{b}}(p)} ビットであり、ここで H b {\displaystyle H_{\mbox{b}}} は2値エントロピー関数である。
2元消失通信路 (Binary Erasure Channel, BEC) で消失が発生する確率を p とする。消失とは入力側が入力したバイナリ値が出力側に届かない状態であり、結果として出力側は 0 と 1 以外に e (erasure)という第3の状態をとる。BECの通信路容量は 1 - pビットである。