XH YH YXH| YXI,

情報理論第 9 回
通信路(2)
2014/11/25
 通信路とエントロピー(前回の復習)

入力信号と出力信号をそれぞれ事象系 X , Y と考える

通信路で変化・消失があると、 X , Y は別のものになる

X , Y の相互情報量 I  X , Y  が大きいほど通信路の性能が良い
I  X , Y  ：出力信号 Y を知ったときに、入力信号 X について得られる情報量

H X 
X についての不確定さ
H Y 
Y についての不確定さ
H X | Y 
Y
について知っているときの
X
についての不確定さ
Y
について知った時に増える
X
についての情報量
I X ,Y 

途中で変化・消失が起こらない場合
⇒ I X , Y は H X 
( X についての不確定さ)に等しい
⇒ Y (出力信号)について知れば、 X (入力信号)について全て知ることができる

途中で変化・消失が起こる場合
⇒ I  X , Y  は H  X  より小さい
⇒ Y (出力信号)について知っても、 X (入力信号)について知らないことが残る

例

 x0 x1 
3 4 1 4 
で表わされるとき、これが通信路 T  

 を通
1 2 1 2
1 4 3 4
る場合を考える。「出力信号が 0 になる」という事象 y0 は、
入力信号の事象系が X  

入力が 0 で、変化が起こらなかった
(1 2  3 4  3 8 )

入力が 1 で、変化が起きた
(1 2 1 4  1 8 )
「出力信号が 1 になる」という事象 y1 は、

入力が 0 で、変化が起きた
(1 2 1 4  1 8 )

入力が 1 で、変化が起こらなかった
(1 2  3 4  3 8 )
1
情報理論第 9 回
通信路(2)
2014/11/25
 y0 y1 
 になる。
1 2 1 2
y0 が確定していれば x0 である確率は 3 8 1 2   3 4 、 y1 が確定していれば x0 である確率
からなり、出力信号の事象系は Y  
は 1 8 1 2   3 4 なので


x1 
x
X  0

3 4 1 4
x1 
x
X  0

1 4 3 4
( y0 (出力が 0)のとき)
( y1 (出力が 1)のとき)
がわかる。出力が 0 の場合のエントロピーは
H  X | y 0   3 4 log3 4   1 4  log1 4   0.82 となり、 H  X | y1  も同じ値になるので、
H  X | Y   p  y0 H  X | y0   p  y1 H  X | y1   0.82 になる。一方出力信号がわからないと
きの入力信号のエントロピーは H  X   1 なので、
I  X , Y   H  X   H  X | Y   1  0.82  0.18 となる。

50%の確率で 0→1, 1→0 の変化が起こる通信路



変化が全く起こらない通信路



x1 
x
1 2 1 2
X  0
で表わされる入力信号が通信路 T  

 を通る
1 2 1 2
1 2 1 2
H X | Y   1
⇒ I  X , Y   0 (出力信号を見ても入力信号についての情報は一切得られない)
x1 
x
1 0 
X  0
で表わされる入力信号が通信路 T  

 を通る場合
1 2 1 2
0 1 
H X | Y   0
⇒ I  X , Y   1 (出力信号を見れば入力信号の情報が完全にわかる)
100%の確率で 0→1, 1→0 の変化が起こる通信路


x1 
x
0 1 
X  0
で表わされる入力信号が通信路 T  

 を通る場合
1 2 1 2
1 0
H X | Y   0
⇒ I  X , Y   1 (出力信号を見れば入力信号の情報が完全にわかる)
 通信路容量


0, 1 からなる信号を通信路に通すと、入力と出力の相互情報量 I  X , Y  は…

入力信号のうちの 0, 1 の発生する確率によって変わる
(入力側の条件)

通信路での 0→1, 1→0 の変化がおこる確率によって変わる
(通信路の条件)

通信路の変化確率は変えずに、入力信号の 0, 1 の発生確率を変えて、 I  X , Y  が最大になる
通信路容量 C ：相互情報量 I  X , Y  の最大値 ⇒ 通信路の性能を表わす
ケースを見つける。そのときの相互情報量が通信路容量 C
2
情報理論第 9 回
通信路(2)
2014/11/25

p 
1  p
 の通信路容量を求める)
 p 1  p
例(通信路 T  
I X ,Y   H X   H X | Y 
⇒どっちの方法でも値は同じだが、この場合は下のほうが計算が楽。
I  X , Y   H Y   H Y | X 
x1 
 x0
入力信号の事象系を X  
 とすると、出力が 0 になる確率は、
 1 
入力が 0 で、通信路で変化しない→  1  p 
入力が 1 で、通信路で 0 に変わる→ 1    p
の両方を合わせた   p  2p になる。同様に、出力が 1 になる確率は、
入力が 0 で、通信路で 1 に変わる→ p
入力が 1 で、通信路で変化しない→ 1   1  p 
の両方を合わせた 1    p  2p になる。よって、出力の事象系は
y0
y1


Y 
 となるので、出力のエントロピーは
  p  2p 1    p  2p 
H Y     p  2p  log  p  2p   1    p  2p  log1    p  2p 
y1 
y1 
 y0
 y0
入力が 0 の場合 Y  
、入力が 1 の場合は Y  

 になるので、どちらの結
1  p p 
 p 1  p
果が確定していても Y のエントロピーは同じ値になる。すなわち
H Y | X    p log p  1  p  log1  p 
I  X , Y   H Y   H Y | X 
   p  2p  log  p  2p 
 1    p  2p  log1    p  2p 
 p log p  1  p  log1  p 
欲しいのは I  X , Y  の最大値。 I  X , Y  を  の関数と考えると、横軸を  、縦軸を I  X , Y  に撮
ったグラフのピークでは傾きが 0 になる。
グラフの傾きは I  X , Y  を  で微分した値なので、最高点では
I  X , Y 
1 2 p
1
 1  2 p  log  p  2p     p  2p 


  p  2p log e 2
 1  2 p  log1    p  2p   1    p  2p 
1 2 p
1

1    p  2p log e 2
 1    p  2p 
  0
 1  2 p  log
   p  2p 
log 1  0 であることから、上の式が成り立つのは
1    p  2p
 1 のとき、
  p  2p
すなわち   p  2p  1    p  2p すなわち   1 2 のとき。
I  X , Y  の  に 1 2 を入れると、 C  1  p log p  1  p  log1  p  が得られる。
3
情報理論第 9 回
通信路(2)
2014/11/25
1.0
C( =通信路の性能)と p の関係
0.8
変化が起こる確率が 0→100%情報を通す
0.6
C
変化が起こる確率が 1/2→情報が完全に失われる
0.4
変化が起こる確率が 1→100%情報を通す
0.2
0.0
0.00
0.20
0.40
0.60
0.80
1.00
p
※ 微分のルール
x   nx
n
①
n 1
(多項式なら次数が１つ下がって、元の次数がかかる)
②
 f x g x   f x g x   f x g x 
(積の微分は、片方ずつ微分したものの和)
③
log e x   1
(自然対数の微分は 1/x)
x
これと、対数の性質 log 2 x 
log e x
を組み合わせれば次の問題は解ける。
log e 2
練習問題 1
1  p
 0
通信路 T  
p
0 
(入力が 0, 1 のどちらでも確率 p で消失がおこる)の通信路容量を求めよ。
p 1  p 
※ 手順

入力信号の事象系 X を書き下す(事象は x 0 , x1 の 2 つ。片方の確率を適当に  などにする)

出力信号の事象系 Y を書き下す(事象は y0 , y x , y1 の 3 つ)

出力のエントロピー H Y  を求める

入力が 0 のとき、1 のときの事象系 Y を書き下す





それぞれの場合の出力のエントロピー H Y | x0  , H Y | x1  を求める
条件付きエントロピー H Y | X  を求める
H Y  , H Y | X  から I  X , Y  を求める
I  X , Y  を  で微分した式をもとめ、その式が 0 となる  を求める
上で求めた  を I  X , Y  に代入する ⇒ C
※ 結果の予想

入力が 0, 1 のどちらでも、確率 p で消失 ⇒ 情報が消える
⇒ C ：通信路の性能は p が大きくなるほど…
4
情報理論第 9 回
通信路(2)
2014/11/25
 一様通信路

符号アルファベットが 0, 1, 2 の 3 つある場合を考える
例：0,1,2 が確率 p で 1,2,0 に変化する通信路
0 
p
1  p

1 p
T  0
p 
 p
0
1  p 
1 p
0
0
p
符号アルファベットを 0→1, 1→2, 2→0 と
置き換えても通信路の特性は変わらない
1
1
1 p
p
こういう通信路のことを一様通信路という
p
2

2
1 p
一様通信路では、入力の符号アルファベットの発生確率が全部等しい時に相互情報量が最大にな
 x0 x1 x2 
 の場合の相互情報量が通信路容量 C になる
1 3 1 3 1 3
る ⇒ この例では X  
y1 y2 
y
Y  0
 なので、 H Y   1 3 log1 3 3  log 3
1 3 1 3 1 3
y1 y2 
 y
x0 が確定していれば Y   0
 ⇒ H Y | x0   1  p  log1  p   p log p となる。
1  p p 0 


x1 , x2 の場合も同様なので、結局 H Y | X   1  p  log1  p   p log p
通信路容量は C  I  X , Y   H Y   H Y | X   log 3  1  p  log1  p   p log p

1.6
C( =通信路の性能)と p の関係
1.4
1.2
変化が起こる確率が 0, 1
C
1.0
→100%情報を通す
0.8
0.6
変化が起こる確率が 1/2
0.4
→多くの情報が失われるがいくらかは通る
0.2
0.0
0.00
0.20
0.40
0.60
0.80
1.00
p
※ 0 を受け取ったときにわかること



p が 0：元の信号は絶対に 0
p が 1：元の信号は絶対に 2
p が 1/2：もとの信号は 0, 2 のどちらかであり、1 ではありえない
5
情報理論第 9 回
通信路(2)
2014/11/25
練習問題 2
p
p 
1  2 p

1 2 p
入力の符号アルファベットが 0, 1, 2 である場合の通信路 T 
p  の通信路容量を求
 p
 p
p
1  2 p 
めよ。また、通信路容量 C が最小になるときの p の値、 C の最小値を求めよ。
1.6
図から通信路容量が最小になるときの p は大体見当
1.4
がつく。 C を p で微分した式を 0 とおけば最小にな
1.2
1.0
るときの p が求められる。
C
0.8
0.6
0.4
0.2
0.0
-0.2
0.00
0.10
0.20
0.30
0.40
0.50
p
※
p は 0～0.5 の範囲の値しか取れない
※ 0 を受け取ったときにわかること

p が 0：元の信号は絶対に 0
p が 1/2：元の信号は 1,2 のどちらかであり、0 ではありえない

C が最小になるときの p ：もとの信号が 0,1,2 のどれである確率も 1/3

6

Download Report