Microsoft PowerPoint - 7.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 7.pptx"

ひろきやがい
4 years ago
Views:

1 通信路 (7 章 )

2 通信路のモデル情報送信者通信路受信者 A a,, a b,, b B m = P( b ),, P( b m ) 外乱 ( 雑音 ) n = P( a,, P( a ) n ) 送信情報源 ( 送信アルファベットと生成確率 ) 受信情報源 ( 受信アルファベッと受信確率 ) でもよい生成確率 ) 受信確率 ) m n 2

3 イメージ外乱 ( 雑音 ) により記号 a i を送信したら記号 b j が受信される記号の種類や数は異なっていてもかまわない ai 通信路 b j ai を送信する外乱 ( 雑音 ) b j を受信する 3

4 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 ある生成確率で条件付き確率送信記号が送信される ( 順序に注意 ) ある受信確率で受信記号が受信される

5 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

6 通信路行列 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

7 通信路行列 ( 条件付き確率 ) 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

8 通信路行列の意味 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

9 通信路例 (2 元対称通信路 ) A ={0=, } p p p 0 0 p p: B ={0, } T S p p = p p 応用上重要誤り確率により対称的に送信記号が変化する 9

10 具体的な 2 元対称通信路 p = 02. A ={0=, } B ={0, } T S = 通信路行列は対称行列になる 0

11 通信路例 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は消失を意味する記号応用上重要送信記号の消失と誤りの両方が起こる

12 具体的な 2 元対称消失通信路 p e = 0. p x = A = {0, } T X X = 存在する B = {0,X, } ( 数学的な対称行列ではないが ) ある種の対称性が 2

13 練習次の通信路線図で表されている通信路の通信路行列を求めよ 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

14 練習 2 次の通信路行列で表されている通信路の通信路線図を示せ () 送信情報源 A { } 受信情報源 B (2) 送信情報源 A = { a,b,c,d } 受信情報源 B = { a,b,c,d } T = a,b,c T = = { a,b,c} p q p 0 q p p q q 0 = 0 p p q q q 0 p p q

15 通信路での確率の関係 ( 全確率の公式 ) 通信路を通して受信される 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

16 証明 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

17 別証明結合確率と条件付き確率の関係式 () 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

18 通信路での確率の関係 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

19 証明結合確率の式 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

20 通信路行列と確率 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

21 別表現転地を行うと左右が反転することに注意 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

22 通信路で送信される情報量 ( 相互情報量 ) 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

23 通信路で伝送される情報量 = 送信情報源の情報量 - 受信情報を条件とする送信情報源の情報量 I( A;B ) H( A) H( A B) 伝送される情報量は相互情報量として求められる 23

24 様々なエントロピー ( 復習 ) HB ( ) エントロピー HA ( ) 条件付きエントロピー HA ( B) HB ( A) 条件付きエントロピー結合エントロピー HAB (, ) 相互情報量 IAB ( ; ) 2

25 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

26 相互情報量の様々な計算式 ( 公式 ) 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 α β β

27 例 3/ / 通信路行列 T = の通信路で / 3/ 0, 情報源 A = / 2, / 2 を伝送するとき受信される情報源 B 0, = および P( 0 ), P( ) 伝送される情報量 ( 相互情報量 ) P( 0) = / 2 P( ) = / 2 3/ / / I( A;B) を求めよ元対称 3/ 通信路 27

28 ( 計算例 ) まず受信記号 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( ) = = P(, ) = P( )P( ) = = 2 8 を送信 28

29 以上より相互情報量を求める 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( ) = log + log + log + log = log [ bit / ] 29

30 練習通信路行列 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

31 通信路容量 ( 重要 ) ( 定義 ): 通信路容量相互情報量は情通信路 T に対して次式で表される報源 A と情報源 B 値を通信路容量というの組み合わせで定まる C = max I(A;B) また受信情報源 Bは送信情報源 A A と通信路 T で定まるここで, max は送信情報源の確率的一番多く情報を伝な組み合わせ全ての中で最大値を選達できるよう送信ぶ側の確率を定めて送信する通信路の太さを表す式情報を伝送してみて最大の情報量で定義する 3

32 イメージ情報通信路水水路物理的でないので直接太さを測ることができない伝送されるもので間接的にに太さは測ることができる 32

33 例 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

34 まず受信記号の生起確率を求める 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

35 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 = log + log 3 通信路の誤り確率だけで定まる =H ( ) H (p) は2 元のエントロピー関数 H ( p ) = plog p ( p )log( p ) =H (p) 35

36 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

37 練習 2/ 3 / 3 通信路行列 T = の通信路の通信路容量 C を / 3 2/ 3 T 求めよ 37

38 2 元対称通信路の通信路容量 2 元対称通信路の通信路容量路誤り確率 p の 2 元対称通信路の通信路容量 C は次式で求められる C = H(p) 通信路容量が達成されるとき送信受信の各確率は以下で表される対称性より送信を均等に行うと受信 P A = (P(( 0 ),P( )) = ( / 2, / 2 ) も均等になる P B = (P( 0),P( )) = ( / 2, / 2) ( 式で計算して確かめると良い ) 38

39 証明通信路行列は次式のようになる 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

40 2 元対称通信路の通信路容量 ( 概形 ) 0

41 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, } 誤り確率と消失確率の関数 ( 導出は省略 )

42 2 元対称消失通信路の通信路容量 p = x だと2 p だと情報が全て元対称通信路と x = 消失容量は0 同じ 0 2

43 雑音のない通信路 ( 定義 ) 雑音の無い通信路受信記号から送信記号が一意に確定できるような通信路を雑音の無い通信路という雑音の無い通信路の通信路行列 / 3 2/ T = 0 0 / 3 / / 5 / 5 3/ 5 列ベクトルが全て要素以外 0 ( 行ベクトルは確率ベクトル ) 3

44 雑音の無い通信路の通信路線図 a / 3 2 / 3 b b b 2 a / b 2 3 b 3/ b / 5 5 a / 5 b / 5 b 7 雑音がないので受信記号から送信記号を特定できる

45 雑音のない通信路の通信路容量雑音の無い通信路では受信記号を条件とする条件付き確率が必ずまたは 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

46 雑音の無い通信路の通信路容量例 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

47 練習送信アルファベット A = { a,a} 2 受信アルファベット B = { b,b,b,b,b } 通信路行列 T = で表わされる ( 雑音の無い ) 通信路の通信路容量と T を実現する際の送信情報源および受信情報源を定めよ C T C T 7

48 確定的通信路 ( 定義 ) 確定的通信路各送信記号が唯一つの受信記号に伝送されるような通信路を確定的通信路という確定的通信路の通信路行列行ベクトルが全て要素以外 0 T = ( 行ベクトルは確率ベクトル ) 行ベクトルが全て要素以外 0 8

49 確定的通信路の通信路線図 a b 送信先の受信記号がつに確定されるので確定的通信路 a 2 b a 2 3 a a 5 b 3 a 6 a a b 7 9

50 確定的通信路の通信路容量確定的通信路では送信記号を条件とする条件付き確率が必ずまたは 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

51 確定的通信路の通信容量例 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

52 通信路容量を満足する送信情報源例 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

53 練習 { } 送信アルファベット A = a,a,a,a,a 受信アルファベット B = { b,b,b } 通信路行列 T = で表わされる ( 確定的 ) 通信路の通信路容量とを実現する際の送信情報源および受信情報源を定めよ C T C T 53

混沌系工学特論 #5

混沌系工学特論 #5 情報科学研究科井上純一 URL : htt://chaosweb.comlex.eng.hokudai.ac.j/~j_inoue/ Mirror : htt://www5.u.so-net.ne.j/j_inoue/index.html 平成 17 年 11 月 14 日第 5 回講義デジタルデータの転送と復元再考 P ({ σ} ) = ex σ ( σσ ) < ij>