通信路 (7 章 )
通信路のモデル 情報 送信者 通信路 受信者 A a,, a b,, b B m = P( b ),, P( b m ) 外乱 ( 雑音 ) n = P( a,, P( a ) n ) 送信情報源 ( 送信アルファベットと生成確率 ) 受信情報源 ( 受信アルファベッと受信確率 ) でもよい 生成確率 ) 受信確率 ) m n 2
イメージ 外乱 ( 雑音 ) により記号 a i を送信したら 記号 b j が受信される 記号の種類や数は異なっていてもかまわない ai 通信路 b j ai を送信する 外乱 ( 雑音 ) b j を受信する 3
a i 通信路は 送信記号を送った時 受信記号 b j が受信される確率 P( ai b j ) でモデル化される すべての組み合わせの確率で一つの通信路が定義される P( a ) a b P(b ) P( a b P( b 2 ) a b 2 j 2 2 ) a i P ( a i b j ) P( a ) a bm P(b m ) n n ( j i) = P b a ある生成確率で 条件付き確率 送信記号が送信される ( 順序に注意 ) ある受信確率で 受信記号が受信される
i, i n, m j= p(a b ) = A i j a a 2 a 3 通信路線図 雑音により 記号が変化する P( a b ) P(a b m ) P( a b) 2 3 b b 2 b 3 B a n bm P( an b m ) 送信アルファベット ( n 個の送信記号受信アルファベットの集合 ) ( m 個の受信記号の集合 ) b m 5
通信路行列 a b b b j m ア m 送信ルフ受信アルファベット t t i i n m T = t tij = a i ij j= tn t nm a n P( a b ) P( a b ) P( a b m ) j = P( ai b ) P( ai b j ) P( ai b m ) P( a n b ) P( an b j ) P( an b m ) i, i n, ァベット 行で和をとると ( 確率ベクトル ) 6
通信路行列 ( 条件付き確率 ) Pb ( ) ( ) a P b j a P( b m a) T = P b a P b a P b a ( ) ( ) i j i ( m i) Pb ( ) ( ) ( ) an P b j an P b m a n β P ( β α= a) = 条件付き確率の性質 ある条件を固定したとき 確率の総和は. 正方行列とは限らない ( 行数と列数が違っていても良い ) 7
通信路行列の意味 i n, j m t = P(b a ) = P(a b ) ij j i i j 通信路行列の要素 a i b j 通信路行列の関係式 を送くる条件の下で が受信される確率 i, j, i n, j m 0 t ij m i, i n tij = j= a を送信したら i が受信される確率 b j 確率の式 ( 行ベクトルが確率ベクトル ) 8
通信路例 (2 元対称通信路 ) A ={0=, } p p p 0 0 p p: B ={0, } T S p p = p p 応用上重要 誤り確率により 対称的に送信記号が変化する 9
具体的な 2 元対称通信路 p = 02. A ={0=, } 08. 0 0 02. 02. 08. B ={0, } T S 08. 02. = 02. 08. 通信路行列は 対称行列になる 0
通信路例 2(2 元対称消失通信路 ) A = {0, } T X 0 p p x e pe p e p p x e p x p x p : e 0 p : x B = {0,X, } X p p p p = x e x e p p p p e x x e Xは消失を意味する記号 応用上重要 送信記号の消失と誤りの両方が起こる
具体的な 2 元対称消失通信路 p e = 0. p x = 03. 06. 03. 0 0 0. A = {0, } T X 0. 03. 06. X 06. 03. 0. = 0. 03. 06. 存在する B = {0,X, } ( 数学的な対称行列ではないが ) ある種の対称性が 2
練習 次の通信路線図で表されている通信路の 通信路行列を求めよ p () (2) 0 x p x 0 a p p p p b b q X x c c p p d d qx p p 3 a
練習 2 次の通信路行列で表されている通信路の通信路線図を示せ () 送信情報源 A { } 受信情報源 B (2) 送信情報源 A = { a,b,c,d } 受信情報源 B = { a,b,c,d } T 2 07. 02. 0. = a,b,c T = 02. 06. 02. = { a,b,c} 0. 02. 07. p q p 0 q p p q q 0 = 0 p p q q q 0 p p q
通信路での確率の関係 ( 全確率の公式 ) 通信路を通して受信される j, j m, n P( b ) = P( b a)p(a) n j j i i i= = P( a i )P( ai b j ) i= n = i== pt i ij 記号の受信確率は 送信記号の生成確率と通信路の確率的振る舞いで定まる 5
証明 A B P( a ) a a 2 P( a b ) i b P( a ) P( a ) i i a i an P( a b ) i n i P(a b ) i b j bm P( b j ) 図より 成立する b i が受信される全ての可能性 ( 径路 ) を考えて総和をとる QED 6
別証明 結合確率と条件付き確率の関係式 () i j j i i P( a,b ) = P( b a )P( a ) a i 結合確率 : 事象が起こりかつ事象 b j が起こる確率 2つの事象が同時に起こる確率 a i 条件付き確率 : 事象が起こったとしたときに事象が起こる確率 b j 結合確率による確率の計算 P(b ) = P(a,b ) (2) j i j i 結合確率を片方の事象系において総和をとる () (2) より成り立つ QED 7
通信路での確率の関係 2( ベーズの定理 ) ベーズの定理 i, j, i n, j m, 条件付き確 P( a b ) = i j n k= P( b a )P( a ) j i i P(b a )P(a ) j k k 率の条件と発生事象を交換する公式 ( 一般の確率論で成立する ) b j 通信路を通して記号 j が受信されたとき 送信側で記号 a i を送っている確率が計算できることを表す式 通信路の性質と送信アルファベットの発生確率は既知であることに注意する 8
証明結合確率の式 P( a,b ) = P( b a )P( a ) = P( a b )P( b ) i j j i i i j j P( a,b ) P( b a )P( a ) P( a b ) = i j = j i i i j P(b ) P(b ) 全確率の式を適用する i j P( a b ) j P( a,b ) P( b a )P( a ) = i j = j i i n n j k k j k k k= k= P( b a )P( a ) P( b a )P( a ) j QED 9
通信路行列と確率 P P 送信情報源の生成記号確率分布 A 受信情報源の受信記号確率分布は 通信路行を用いて次式で表される B T = (P(a ),),P( a n )) = (P(b ),,P(b )) m との関係 P B = P T A m ( P( b ),,P( b m )) = ( P( a ),,P( a n )) t t n t t nm 情報理論では 行ベクトル ( 横ベクトル ) が確率ベクトルになるように扱うことが多い 20
別表現 転地を行うと 左右が反転することに注意 t P = t t B T P A P( b ) t t P( a ) n = P( b ) m t t m nm P( a ) n 線形代数等では 列ベクトルを多く扱う これらを混同せずに扱う必要がある 2
通信路で送信される情報量 ( 相互情報量 ) A a,, a n = P(a ),, P(a n ) 通信路 T B b,, b H( A) H( A B) m = P( b ),, P( b m ) 通信路を通さずに直に情報源 Aに関する情報を得られる場合 通信路を通して 間接的に情報源 Aに関する情報を得る場合 22
通信路で伝送される情報量 = 送信情報源の情報量 - 受信情報を条件とする送信情報源の情報量 I( A;B ) H( A) H( A B) 伝送される情報量は 相互情報量として求められる 23
様々なエントロピー ( 復習 ) HB ( ) エントロピー HA ( ) 条件付きエントロピー HA ( B) HB ( A) 条件付きエントロピー 結合エントロピー HAB (, ) 相互情報量 IAB ( ; ) 2
HA ( ) = P( α)log P( α) α AA HB ( ) = P( β)log P( β) β B HA ( B) = P( β) HA ( β ) HB ( A ) = P ( α ) HB ( α ) β B α A = P( β) P( α β)log P( α β) = P( α) P( β α)log P( β α) β B = α A, β B α A P( αβ, )log P( α β) α A, β B α A = α A, β B HAB (, ) = P( αβ, )log P( αβ, ) = HA ( ) + HB ( ) IAB ( ; ) β B P( αβ, )log P( β α) IAB ( ; ) = HA ( ) HA ( B ) = HB ( ) HB ( A) = HA ( ) + HB ( ) HAB (, ) 25
相互情報量の様々な計算式 ( 公式 ) IAB ( ; ) = HA ( ) HA ( B) = P( α)log P( α) P( α, β)log P( α β) α A β B α A = P( αβ, )log P( α) + P( αβ, )log P( α β) α A β B α A β B = P( α β) P( αβ, )log P ( α ) α A β B P α P( αβ, ) P ( α, β)log α A β B P ( α ) P ( β ) P ( α, β ) P( ( α, β )log A, B P ( α ) P( ) = = 26 α β β
例 3/ / 通信路行列 T = の通信路で / 3/ 0, 情報源 A = / 2, / 2 を伝送するとき 受信される情報源 B 0, = および P( 0 ), P( ) 伝送される情報量 ( 相互情報量 ) P( 0) = / 2 P( ) = / 2 3/ / / I( A;B) を求めよ 0 0 2 元対称 3/ 通信路 27
( 計算例 ) まず 受信記号 B = 0, の生成確率 P( 0),P( ) を求める P B = PT A { } ( P( 0),P( )) = ( P( 0),P( )) T 3 / / (P( 0),P( )) = ( / 2, / 2) = ( / 2, / 2) / 3/ 次に 結合確率を求める 3 3 P( 00, ) = P( 0 0)P( 0) = = 0を送信 2 8 P( 0, ) = P( 0)P( 0) = = 2 8 P( 0, ) = P( 0 )P( ) = = 2 8 3 3 P(, ) = P( )P( ) = = 2 8 を送信 28
以上より 相互情報量を求める P( αβ, ) I( A;B) = P( α, β)log α A, β B P( α )P( β ) P( 00, ) P( 0, ) = P( 00, )log + P( 0, )log + P( 0)P( 0) P( 0)P( ) P( 0, ) P(, ) P( 0, )log + P(, )log P( )P( 0) P( )P( ) 3 3 3 3 = log + log + log + log 8 2 8 2 8 2 8 2 3 = log 3 0. 89 [ bit / ] 29
練習 通信路行列 3/ / T = の通信路で / 3/ 0, 情報源 A = を伝送するとき / 3, 2/ 3 0, 受信される情報源 B = および P( 0 ), P( ) 伝送される情報量 ( 相互情報量 ) P( 0 ) = / 3 P( ) = 2/ 3 3/ / / I( A;B) 0 0 3/ を求めよ 2 元対称通信路 30
通信路容量 ( 重要 ) ( 定義 ): 通信路容量相互情報量は 情通信路 T に対して 次式で表される報源 A と情報源 B 値を通信路容量という の組み合わせで定まる C = max I(A;B) また 受信情報源 Bは送信情報源 A A と通信路 T で定まる ここで, max は送信情報源の確率的一番多く情報を伝な組み合わせ全ての中で最大値を選達できるよう送信ぶ 側の確率を定めて送信する 通信路の 太さ を表す式 情報を伝送してみて最大の情報量で定義する 3
イメージ 情報 通信路 水 水路 物理的でないので 直接 太さを測ることができない 伝送されるもので 間接的にに 太さ は測ることができる 32
例 3/ / 通信路行列 T = の通信路の通信路容量 C を / 3/ T 求めよ ( 誤り確率の2 元対称通信路 ) p = / ( 解答例 ) 誤り確率と 0, 記号発生送信情報源を A = とし 確率 p A, p A 記号受信確率を混 0, B 同しないこ受信情報源を = とする と p B, pb また PA = (p A, p A ), P B = (p B, p B ) とする 33
まず 受信記号の生起確率を求める P = P T B A 3/ / (p B, p B ) = (p A, p A ) / 3 / pa 3 pa (p B, p B ) = ( +, ) 2 2 pa + 2pA pb = + = 2 0を送信という条件で 次に 結合確率を求める 0 を受信する確率 0 0 を送信して しかもしかもが受信される確率 3 P( 00, ) = P( 0 0)P( 0) = p A P( 0, ) = P( 0)P( 0) = p A 0 を送信する確率 3
P( 0, ) = P( 0 )P( ) = ( p A ) を送信 3 P(, ) = P( 0)P( ) = ( p A ) 条件付きエントロピー H(B A) を求める H(B A) = P( α, β)logp( β α) α A, β B 3 3 = p Alog + p Alog + ( p A )log + ( p A )log 3 3 3 = log + log 3 通信路の誤り確率だけで定まる =H ( ) H (p) は2 元のエントロピー関数 H ( p ) = plog p ( p )log( p ) =H (p) 35
C 従って 相互情報量 I( A;B) は次式で求められる I(A;B) = H(B) H(B A) = H(p B ) H(p) = H( + p A ) H( ) 2 よって 通信路容量は以下のように求められる T = maxi(a;b) A C T ここで 最大値は pa max ( ) ( ) p = H + H + A = p 0, 2 2 A [ ] 2 p A p max A = = H( + ) H ( ) 2 p A [ 0, ] 2 のときの p B 3 = ( log + log ) 089. pa 3 p B = + = 2 2 のときに実現される また こは以下である 36
練習 2/ 3 / 3 通信路行列 T = の通信路の通信路容量 C を / 3 2/ 3 T 求めよ 37
2 元対称通信路の通信路容量 2 元対称通信路の通信路容量路 誤り確率 p の 2 元対称通信路の通信路容量 C は次式で求められる C = H(p) 通信路容量が達成されるとき 送信 受信の各確率は以下で表される 対称性より 送信を均等に行うと 受信 P A = (P(( 0 ),P( )) = ( / 2, / 2 ) も均等になる P B = (P( 0),P( )) = ( / 2, / 2) ( 式で計算して確かめると良い ) 38
証明通信路行列は 次式のようになる p p Tp = p p 例題と同様にして以下のように求められる p p ( p, B p) B = (p, A p) A p p p = p + p 2 p p C T B A A = maxi(a;b) A p [ 0, ] { H H } = max ( p ) ( p ) A p [ 0, ] A B { H } = max ( p ) H( p ) B (p A = / 2 p B = / 2 H H (p ) = ) = H (p) QED B 39
2 元対称通信路の通信路容量 ( 概形 ) 0
2 元対称消失通信路の通信路容量 送信情報源 A = {0, } T X p p x e p p x e p e p x px p : e : e x p x p e p x p e 0 0 p X p = pe px px pe p C = ( p ) HH e TX x p x 受信情報源 B = {0, X, } 誤り確率と消失確率の関数 ( 導出は省略 )
2 元対称消失通信路の通信路容量 p = x だと2 p だと情報が全て元対称通信路と x = 消失 容量は0 同じ 0 2
雑音のない通信路 ( 定義 ) 雑音の無い通信路受信記号から送信記号が一意に確定できるような通信路を雑音の無い通信路という 雑音の無い通信路の通信路行列 / 3 2/ 3 0 0 0 0 0 T = 0 0 / 3 / 0 0 0 0 0 0 0 / 5 / 5 3/ 5 列ベクトルが全て 要素以外 0 ( 行ベクトルは確率ベクトル ) 3
雑音の無い通信路の通信路線図 a / 3 2 / 3 b b b 2 a / b 2 3 b 3/ b / 5 5 a / 5 b 3 6 3 / 5 b 7 雑音がないので 受信記号から送信記号を特定できる
雑音のない通信路の通信路容量 雑音の無い通信路では 受信記号を条件とする条件付き確率が必ず または 0 となる すなわち α A, β B P( α β ) = or 0 β B H(A β ) = P( α β)logp( α β ) = したがって α A H( A B) = P( β)h( A β ) = 0 β A よって I( A;B) = H( A) H( A B) = H( A) C = max I( A;B ) = max H( A ) = log n A ただし P(a ) = P(a 2 ) = = P(a n ) A 0 5
雑音の無い通信路の通信路容量例 P(a ) = / 3 a / 3 2 / 3 b b 2 P(a 2 ) / 3 b = 3 a / 2 3/ b P(a 3 ) = / 3 a 3 b / 5 5 / 5 b 6 3 / 5 b log 3 [bit/ ] 7 6
練習 送信アルファベット A = { a,a} 2 受信アルファベット B = { b,b,b,b,b } 通信路行列 2 3 5 2 3 0 0 0 5 5 T = 2 3 0 0 9 9 9 で表わされる ( 雑音の無い ) 通信路の通信路容量と T を実現する際の送信情報源 および受信情報源を定めよ C T C T 7
確定的通信路 ( 定義 ) 確定的通信路各送信記号が唯一つの受信記号に伝送されるような通信路を確定的通信路という 確定的通信路の通信路行列 0 0 0 0 0 0 0 0 0 行ベクトルが全て 要素以外 0 T = ( 行ベクトルは確率ベクトル ) 0 0 0 0 0 0 0 0 0 0 0 0 行ベクトルが全て 要素以外 0 8
確定的通信路の通信路線図 a b 送信先の受信記号がつに確定されるので確定的通信路 a 2 b a 2 3 a a 5 b 3 a 6 a a b 7 9
確定的通信路の通信路容量 確定的通信路では 送信記号を条件とする条件付き確率が必ず または 0 となる すなわち α A, β B P( β α ) = or 0 α A H(B α ) = P( β α)logp( β α ) = よって β B H(B A) = P( α)h(b α ) = α A I(A A;B) = H(B) H(B A) = H(B) 0 順序に注意 0 したがって C = max I( A;B ) = max H( B ) = log m A ただし P(b ) = P(b 2 ) = = P(b m ) A 受信側の確率が均等になるように 送信記号の確率選べる 50
確定的通信路の通信容量例 P( a ) = / Pa ( ) 2 = / 8 Pa ( ) 3 = / 8 = a Pa ( ) = / 2 Pa ( ) 5 = / 2 P( a ) 6 = / 2 P ( a ) 7 = / a a 2 a3 a 5 a 6 a 7 b b 3 ( ) b ( ) 2 P b = / P b 2 = / ( ) b ( ) P b 3 = / P b = / log [bit/ ] 5
通信路容量を満足する送信情報源例 2 P( a ) = / Pa ( ) 2 = / 2 Pa ( ) 3 = 2 / 2 = a Pa ( ) = / 2 Pa ( ) 5 = 2 / 2 P( a ) 6 = 3/ 2 P ( a ) 7 = / a a 2 a3 a 5 a 6 a 7 b b 3 ( ) b ( ) 2 P b = / P b 2 = / ( ) b ( ) P b 3 = / P b = / log [bit/ ] 52
練習 { } 送信アルファベット A = a,a,a,a,a 2 3 5 受信アルファベット B = { b,b,b } 通信路行列 0 0 0 0 T = 0 0 0 0 0 0 2 3 で表わされる ( 確定的 ) 通信路の通信路容量と を実現する際の送信情報源 および受信情報源を定めよ C T C T 53