情報理論

通信路（７章）
1
通信路のモデル
情報
送信者
ìï a1
A = ïí
ïï P( a1 )
î
受信者
通信路
, L
,
, L
,
ü
ïï
ý
P( a n )ïþ
ï
an
ìï b1
B = ïí
ïï P( b1 )
î
, L
,
, L
,
ü
ïï
ý
P( b m )ïþ
ï
bm
外乱（雑音）
送信アルファベット
受信アルファベット
m¹ n
でもよい。
2
イメージ
外乱も確率的に扱う。
ai
から b j に変更する確
率で通信路が定義される。
ai
a i を送信する。
通信路
bj
bj
を受信する。
3
通信路は、送信記号 a i
を送った
時、受信記号 b j が受信される確
率 P( a ® b ) でモデル化される。す
べての組み合わせの確率で一つの
通信路が定義される。
i
P ( a1 )
a1
P( a2 )
a2
M
M
P( an )
an
j
P( a i ® b j )
ai
ある生成確率で、
送信記号が送信される。
bj
b1
P( b1 )
b2
P( b 2 )
M
M
bm
P( b m )
ある（存在）確率で、
受信記号が受信される。
4
通信路線図
" i ,1 £ i £ n ,
m
å
p( a i ® b j ) = 1
雑音により、記号が変化する。
j= 1
a1
P( a1 ® b1 )
b1
b2
a2
A
a3
P( a 2 ® b3 )
b3
B
P( a1 ® bm )
bm - 1
an
P( a n ® bm )
送信アルファベット
bm
受信アルファベット
5
通信路行列
送
信
ア
ル
フ
ァ
ベ
ッ
ト
b1
a 1 é t11
ê
M êM
ê
T = a ê®
i ê
êM
M ê
ê
êë t n 1
an
éP ( a 1
ê
ê
ê
= ê
ê
ê
ê
ê
êëP ( a n
® b1 )
受信アルファベット
L
L
bj
L
bm

L
t1 m ù
ú
M ú
ú
ú
ú
M ú
ú
ú
t nm ú
û

®
t ij
L
L
L
" i ,1 £ i £ n ,
m
å
j= 1
行で和をとると１。
（確率ベクトル）
L
M
P ( ai ® b j )
M
® b1 )
L
t ij = 1
L
P ( a1 ® b m )ù
ú
ú
M
ú
ú
ú
ú
M
ú
ú
P ( a n ® bm )ú
û6
通信路行列の意味
1 £ i £ n ,1 £ j £ m
t ij = P( b j | a i ) = P( a i ® b j )
通信路行
列の要素
a i を送くる条件の下で、
b j が受信される確率
a i を送信したら、
b j が受信される確率
通信路行列の関係式
ìï " i , j ,1 £ i £ n ,1 £ j £ m
ï
ïï
í
ï " i ,1 £ i £ n
ï
ïï
î
0 £ t ij £ 1
m
å
t ij = 1
確率の式。
（行ベクトルが
確率ベクトル）
j= 1
7
通信路例１（２元対称通信路）
p :誤り確率
1- p
0
p
0
p
A = {0 ,1}
1
é
1- p
2
Ts = ê
ê p
ë
B = {0 ,1}
1- p
p ù
ú
1- pú
û
1
応用上重要。
誤り確率により、対
称的に送信記号が
変化する。
8
通信路例２（２元対称消失通信路）
p e :誤り確率
1 - p x - pe
0
A = {0 ,1}
pe
0
px
pe
px
1
1 - p x - pe
é
1 - p x - pe
2
TX = ê
êp
ë e
px
px
B = {0 , X ,1}
X
Xは消失を意
味する記号。
1
ù
ú
1 - p x - pe ú
û
pe
p x :消失確率
応用上重要。
送信記号の
消失と誤りの
両方が起こる。
9
練習
次の通信路線図で表されている通信路の、
通信路行列を求めよ。
（１）
1- px
0
0
px
qx
X
1
（２）
1- p
p
p
1- p
a
b
c
1
d
b
c
p
p
1- qx
a
1- p
d
1- p
10
練習２
（１）
次の通信路行列で表されていいる通信路の通信
路線図を示せ。
é0 . 7 0 . 2 0 . 1 ù
A = { a ,b ,c }
ê
ú
T1 = ê0 . 2 0 . 6 0 . 2 ú
ê
ú
B = { a ,b ,c }
ê0 . 1 0 . 2 0 . 7 ú
ë
û
（２）
A = { a ,b ,c , d }
é1 - p - q
ê
ê
p
ê
T2 =
ê
0
ê
ê
q
ë
B = { a ,b ,c ,d }
p
0
1- p - q
q
p
1- p - q
0
p
ù
ú
ú
0
ú
ú
q
ú
1- p - qú
û
q
11
通信路での確率の関係１
（全確率の公式）
通信路を通して受信される
" j ,1 £ j £ m ,
記号の受信確率は、送信記
号の生成確率と通信路の確
率的振る舞いで定まる。
n
P( b j ) =
å
P ( b j | a i )P ( a i )
i= 1
n
=
å
P ( a i )P ( a i ® b j )
i= 1
n
=
å
p i t ij
i= 1
12
証明
A
a
P( a1 )
1
B
P( a1 ® bi )
b1
a2
1
P( a i ) a i
P( a i ® bi )
P( a i ) a n
P( a n ® bi )
bj
P( b j )
bm
bi が受信される全ての可能性（経
路）を考えて総和をとる。
図より、成立する。
QED
13
別証明
結合確率と条件付き確率の関係式。
(1)
P( a i ,b j ) = P( b j | a i )P( a i )
結合確率：事象 a i が起こりかつ
事象 b j が起こる確率。
２つの事象が同時に起こる確率。
条件付き確率：事象 a i
が起こったとしたときに事
象 b j が起こる確率。
結合確率による確率の計算
(2)
P( b j ) =
å
P( a i ,b j )
i
結合確率を片方の事象系において総和をとる。
（１）、（２）より成り立つ。
QED 14
通信路での確率の関係２
（ベーズの定理）
" i , j ,1 £ i £ n ,1 £ j £ m ,
P( a i | b j ) =
P( b j | a i )P( a i )
n
å
P( b j | a k )P( a k )
k= 1
通信路を通して記号 b j が受信されたとき、
送信側で記号 a i を送っている確率が計算で
きることを表す式。通信路の性質と送信アルファ
ベットの発生確率は既知であることに注意する。
15
証明
結合確率の式
P( a i ,b j ) = P( b j | a i )P( a i ) = P( a i | b j )P( b j )
\ P( a i | b j ) =
P( a i ,b j )
P( b j | a i )P( a i )
=
P( b j )
P( b j )
全確率の式を適用する。
\ P ( ai | b j )
=
P ( a i ,b j )
n
å
k= 1
P ( b j | a k )P ( a k )
=
P ( b j | a i )P ( a i )
n
å
k= 1
P ( b j | a k )P ( a k )
QED
16
通信路行列と確率
PA = ( P( a1 ),L , P( a n ))
PB = ( P( b1 ),L , P( bm ))
として、次式で表される。
PB = P A T
ét11 L
ê
( P( b1 ),L , P( b m )) = ( P( a1 ),L , P( a n )) ê M O
ê
êt
ë n1 L
t1 m ù
ú
Mú
ú
t nm ú
û
情報理論では、行ベクトル（横ベクトル）が確率ベク
トルになるように扱うことが多い。
17
別表現
転地を行うと、左右が反転す
ることに注意
t
t
t
PB = T P A
éP( b1 ) ù
ê
ú
ê M ú=
ê
ú
êP( b ) ú
m û
ë
ét11 L
ê
êM O
ê
êt
ë1m L
t n 1 ùéP( a1
úê
Múê M
úê
t nm úê
ûëP( a n
)ù
ú
ú
ú
)ú
û
線形代数等では、列ベクトルを多
く扱う。これらを混同せずに扱う必
要がある。
18
通信路で送信される情報量
（相互情報量）
ìï a1
A = ïí
ïï P( a1 )
î
, L
,
, L
,
ìï b1
B = ïí
ïï P( b1 )
î
ü
ïï
ý
P( a n )ïþ
ï
an
, L
,
, L
,
ü
ïï
ý
P( b m )ïþ
ï
bm
通信路T
H( A)
通信路を通さずに直に
情報源Aに関する情報
を得られる場合。
H( A|B )
通信路を通して、間接
的に情報源Aに関する
情報を得る場合。
19
通信路で伝送
される情報量＝
送信情報源の
情報量
I ( A; B )
H( A)
－
受信情報を条件と
する送信情報源
の情報量
H( A|B )
伝送される情報量は、
相互情報量として求め
られる。
20
様々なエントロピー（復習）
H (B )
エントロピー
H (A )
H (B | A )
条件付
きエン
トロ
ピー
H (A | B )
条件付
きエン
トロ
ピー
結合エントロピー
H (A , B )
相互情報量
I (A ; B )
21
å
H (A ) = -
P ( a ) logP ( a )
H (B ) = -
å
P ( b )H ( A | b )
H (B | A ) =
bÎ B
= -
å
= -
å
å
P ( a )H ( B | a )
aÎ A
P ( b ) å P ( a | b ) log P ( a | b )
bÎ B
P ( b ) logP ( b )
bÎ B
aÎ A
H (A | B ) =
å
= -
aÎ A
å
P ( a ) å P ( b | a ) log P ( b | a )
aÎ A
P ( a , b ) log P ( a | b )
å
= -
a Î A ,b Î B
bÎ B
P ( a , b ) log P ( b | a )
a Î A ,b Î B
H (A , B ) = -
å
P ( a , b ) logP ( a , b )
a Î A ,b Î B
= H (A ) + H (B ) - I (A ; B )
I (A ; B ) = H (A ) - H (A | B )
= H (B ) - H (B | A )
= H (A ) + H (B ) - H (A , B )
22
相互情報量の確率表現
I (A ; B ) = H (A ) - H (A | B )
= -
å
aÎ A
æ
P ( a ) log P ( a ) - çççç
è
å
= -
å
a Î A ,b Î B
=
å
P ( a , b ) log
å
a Î A ,b Î B
P ( a , b ) log P ( a | b )
a Î A ,b Î B
P (a | b )
P (a )
a Î A ,b Î B
=
å
P ( a , b ) log P ( a ) +
a Î A ,b Î B
ö
÷
P ( a , b ) log P ( a | b ) ÷
÷
÷
ø
P ( a , b ) log
P (a , b )
P ( a )P ( b )
23
例１
ì 0
情報源 A = ïïí
1 ü
ïï を
ý
, 1 / 2 ïþ
ï
,
ïîï 1 / 2
é3 / 4
通信路行列 T = ê
ê1 / 4
ë
1/ 4ù
ú の通信路で
3 / 4ú
û
ìï 0
,
1
ï
伝送するとき、受信される情報源 B = í
ï P( 0 ) , P( 1
îï
送信元の情報源の相互情報量 I ( A; B ) を求めよ。
ü
ïï
ý
)ïþ
ï
と
3/4
P( 0 ) = 1 / 2
0
1/ 4
0
1/ 4
P( 1 ) = 1 / 2
1
3/4
1
２元対称
通信路
24
（計算例）
まず、受信記号 B =
{0 , 1 }の生成確率
P( 0 ), P( 1 )
を求める。
PB = P A T
\ ( P( 0 ), P( 1 )) = ( P( 0 ), P( 1 ))T
é3 / 4
\ ( P( 0 ), P( 1 )) = ( 1 / 2 ,1 / 2 ) ê
ê1 / 4
ë
次に、結合確率を求める。
P( 0 , 0 ) = P( 0 | 0 )P( 0 ) =
P( 0 , 1 ) = P( 1 | 0 )P( 0 ) =
P( 1 , 0 ) = P( 0 | 1 )P( 1 ) =
3
´
4
1
´
1
2
1
=
=
3
8
1
4
2
8
1
1
1
´
=
1/ 4ù
ú= ( 1 / 2 ,1 / 2 )
3 / 4ú
û
4 2
8
3 1
3
P( 1 , 1 ) = P( 1 | 1 )P( 1 ) = ´
=
4 2
8
0を送信
１を送信
25
以上より、相互情報量を求める。
å
I ( A; B ) =
P( a ,b )
P ( a , b ) log
P ( a )P ( b )
a Î A ,bÎ B
P( 0 , 0 )
= P ( 0 , 0 ) log
+ P ( 0 , 1 ) log
P ( 0 )P ( 0 )
P ( 1, 0 )
P ( 1 , 0 ) log
=
8
=
3
log
3
2
+
1
8
log
1
+
2
1
8
log
+
P ( 0 )P ( 1 )
+ P ( 1 , 1 ) log
P ( 1 )P ( 0 )
3
P( 0 ,1 )
P ( 1, 1 )
P ( 1 )P ( 1 )
1
2
+
3
8
log
3
2
log 3 - 1 ; 0 . 189
4
26
練習
ì 0
情報源 A = ïïí
ïîï 1 / 3
,
,
1 ü
ïï を
ý
2 / 3ïþ
ï
é3 / 4
通信路行列 T = ê
ê1 / 4
ë
1/ 4ù
ú の通信路で
3 / 4ú
û
ìï 0
,
1
ï
伝送するとき、受信される情報源 B = í
ï P( 0 ) , P( 1
îï
送信元の情報源の相互情報量 I ( A; B ) を求めよ。
ü
ïï
ý
)ïþ
ï
と
27
通信路容量（重要）
（定義）：通信路容量
通信路 T に対して、次式で表される値を
通信路容量という。
C = m ax I ( A; B )
A
ここで, max は送信情報源の確率的な組み合
わせ全ての中で最大値を選ぶ。
通信路の”太さ”を表す式。情報を伝送してみて
最大の情報量で定義する。
28
イメージ
情報
通信路
物理的でないので、直接”太
さ”を測ることができない。
水
水路
伝送されるもので、間接的に
に”太さ”は測ることができる。
29
例
é3 / 4
通信路行列 T = êê
ë1 / 4
求めよ。（誤り確率
1/ 4ù
ú
3 / 4ú
û
の通信路の通信路容量 C T を
p = 1 / 4 の２元対称通信路）
（解答例）
ìï 0
ï
送信情報源を A = í
ïï p A
î
ü
ïï
ý
, 1 - p A ïþ
ï
ìï 0
ï
B
=
í
受信情報源を
ï pB
îï
ü
ïï
ý とする。
, 1 - p B ïþ
ï
また、
,
1
,
とし、
1
PA = ( p A ,1 - p A ), PB = ( p B ,1 - p B )
とする。
30
まず、受信記号の生起確率を求める。
PB = PAT
é3 / 4
\ ( p B ,1 - p B ) = ( p A ,1 - p A ) ê
ê1 / 4
ë
1/ 4ù
ú
3 / 4ú
û
pA 3
pA
\ ( p B ,1 - p B ) = ( +
, )
4
2 4
2
1
\ pB =
1
4
+
pA
2
=
1+ 2 pA
4
次に、結合確率はを求める。
P( 0 , 0 ) = P( 0 | 0 )P( 0 ) =
P( 0 , 1 ) = P( 1 | 0 )P( 0 ) =
3
4
1
4
pA
0を送信
pA
31
P( 1 , 0 ) = P( 0 | 1 )P( 1 ) =
P( 1 , 1 ) = P( 1 | 0 )P( 1 ) =
1
4
3
4
１を送信
(1- pA )
(1- p A )
条件付きエントロピー H ( B | A ) を求める。
å
H(B| A)= -
P( a , b ) log P( b | a )
a Î A ,bÎ B
=
3
4
=
1
p A log
log 4 +
4
= H (
4
+
3
3
4
1
)
4
= H ( p)
1
4
log
p A log 4 +
1
4
( 1 - p A ) log 4 +
3
4
( 1 - p A ) log
4
3
4
3
通信路の誤り確率だけで定まる。
H ( p ) は２元のエントロピー関数
H ( p ) = - p log p - ( 1 - p ) log( 1 - p )
32
従って、相互情報量
I ( A; B )
は次式で求められる。
I ( A; B ) = H ( B ) - H ( B | A )
= H ( pB )- H ( p )
= H (
1
+
4
1
2
pA )- H (
1
)
4
よって、通信路容量 C は以下のように求められる。
T
C T = m ax I ( A; B )
ここで、最大値は
A
ìïï
pA
1
1 ü
ïï
= m ax í H ( +
) - H ( )ý
p A Î [ 0 ,1 ] ï
4
2
4 ïïþ
îï
1
ìïï
pA ü
1
1
ïï
= m ax í H ( +
)ý - H ( )
p A Î [ 0 ,1 ] ï
4
2 ïïþ
4
îï
\ pA =
= 1- (
1
4
log 4 +
3
4
log
4
3
) ; 0 . 189
+
4
pA
=
2
1
2
1
2
のときに実現される。また、こ
のときの p B は以下である。
pB =
1
4
+
pA
2
=
1
2
33
練習
é2 / 3
通信路行列 T = êê
ë1 / 3
1/ 3ù
ú
2 / 3ú
û
の通信路の通信路容量 C T を
求めよ。
34
２元対称通信路の通信路容量
２元対称通信路の通信路容量
誤り確率 p の２元対称通信路の通信路容量
は次式で求められる。
C
C = 1- H ( p )
通信路容量が達成されるとき、送信、受信の各確率は
以下で表される。
対称性より、送信を
均等に行うと、受信
PA = ( P ( 0 ), P ( 1 )) = (1 / 2 ,1 / 2 )
も均等になる。
（式で計算して確か
PB = ( P ( 0 ), P ( 1 )) = (1 / 2 ,1 / 2 )
めると良い。）
35
証明
通信路行列は、次式のようになる。
é1 - p
Tp = ê
ê p
ë
p ù
ú
1- pú
û
例題と同様にして以下のように求められる。
é1 - p
p ù
ú
( p B ,1 - p B ) = ( p A ,1 - p A ) ê
ê p
ú
1
p
ë
û
\ pB = pA + p - 2 p A p
C T = m ax I ( A ; B )
A
=
=
m ax {H ( p B ) - H ( p )}
p A Î [ 0 ,1 ]
Q ( pA = 1 / 2
® pB = 1 / 2
® H ( pB ) = 1 )
m ax {H ( p B )}- H ( p )
p A Î [ 0 ,1 ]
= 1- H ( p )
QED
36
２元対称通信路の通信路容量（概形）
37
雑音のない通信路
（定義）雑音の無い通信路
受信記号から送信記号が一意に確定できるような
通信路を雑音の無い通信路という。
雑音の無い通信路の通信路行列
é1 / 3
ê
T = ê 0
ê
ê 0
ë
2/3
0
0
0
0
0
1/ 4
3/ 4
0
0
0
0
0
1/ 5
1/ 5
列ベクトルが全て、１要素以外０。
（行ベクトルは確率ベクトル）
0 ù
ú
0 ú
ú
3 / 5ú
û
38
雑音の無い通信路の通信路線図
a1
a2
1/ 3
b1
2/3
b2
1/ 4
b3
b4
3/4
1/ 5
a3
1/ 5
b5
b6
雑音がないの
で、送信記号を
特定できる。
3/5
b7
39
雑音のない通信路の通信路容量
雑音の無い通信路では、受信記号を条件とする条件付き確率が
必ず１または０となる。すなわち、
" a Î A ,b Î B
\ "bÎ B
P( a | b ) = 1
H( A|b )=
å
or
0
P( a | b ) log P( a | b ) = 0
aÎ A
\ H( A|B )=
å
P( b )H ( A | b ) = 0
bÎ A
よって、
I ( A; B ) = H ( A ) - H ( A | B ) = H ( A )
したがって、
C = m ax I ( A; B ) = m ax H ( A ) = log n
A
ただし、
A
P( a1 ) = P( a 2 ) = L = P( a n )
40
雑音の無い通信路の通信路容量例
P( a1 ) = 1 / 3
P( a 2 ) = 1 / 3
a1
a2
b1
1/ 3
2/3
b2
1/ 4
b3
b4
3/4
1/ 5
P( a 3 ) = 1 / 3
a3
1/ 5
b5
b6
3/5
lo g 3
[b it/ 送信記号 ]
b7
41
確定的通信路
（定義）確定的通信路
各送信記号が唯一つの受信記号に伝送されるような
通信路を確定的通信路という。
確定的通信路の通信路行列
é1 0 0 ù
ê
ú
ê0 1 0 ú
ê
ú
行ベクトルが全て、１要素以外０。
ê0 1 0 ú
ú
（行ベクトルは確率ベクトル）
T = ê
ê0 0 1 ú
ê
ú
ê
ú
0
0
1
ê
ú
ê
ú
0
0
1
êë
úû
42
確定的通信路の通信路線図
1
a1
a2
送信先の記号
が確定されるの
で確定的通信
路
1
b2
a3
1
a4
a5
a6
b1
1
1
1
b3
43
確定的通信路の通信路容量
順序に注意
確定的通信路では、送信記号を条件とする条件
付き確率が必ず１または０となる。すなわち、
" a Î A ,b Î B
\ "a Î A
P( b | a ) = 1
H ( B |a ) =
å
or
0
P( b | a ) log P( b | a ) = 0
bÎ B
\ H ( B | A ) = å P( a )H ( B | a ) = 0
aÎ A
よって、
I ( A; B ) = H ( B ) - H ( B | A ) = H ( B )
したがって、
C = m ax I ( A; B ) = m ax H ( B ) = log m
A
ただし、
A
P( b1 ) = P( b2 ) = L = P( bm )
受信側の確率
が均等になるよ
うに、送信記号
の確率選べる。
44
確定的通信路の通信路容量例
P( a1 ) = 1 / 3
P( a 2 ) = 1 / 6
P( a 3 ) = 1 / 6
a1
1
b2
a3
a4
P( a 5 ) = 1 / 9
a5
a6
b1
P( b1 ) = 1 / 3
a2
P( a 4 ) = 1 / 9
P( a 6 ) = 1 / 9
1
1
P( b2 ) = 1 / 3
1
1
1
b3
P( b3 ) = 1 / 3
lo g 3
[b it/ 送信記号 ]
45

Download Report