混沌系工学特論 #5

Size: px

Start display at page:

Download "混沌系工学特論 #5"

もえりはぎにわ
4 years ago
Views:

1 混沌系工学特論 #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 回講義

2 デジタルデータの転送と復元再考 P ({ σ} ) = ex σ ( σσ ) < ij> i j ( σ ) iσ j ex < ij> 画像の復元では画像の特質を事前分布で表現できる劣化されたデジタル画像デジタル画像確率モデルで表現伝送路 { τ} 符号ビット列ノイズの乗ったビット列復元されたデジタル画像復号 { ξ} ビット列の場合は? { σ} 復号復元されたビット列

3 雑音のある状況でのデータ送信誤り訂正符号誤り率の元対称通信路ビット反転率ただ1 度だけでなく何回か同じ記号を繰り返し送信する受信者側は多数決で送信された記号を確定する元対称通信路 5 回送信した場合 : 等送信回数 n = 5 のときの誤り確率は f ( ) = C (1 ) + C (1 ) + (5) e = 1 (1 ) + 5 (1 ) ビットの誤りが 5 ビットの何番目にくるかという場合の数繰り返し回数 n を大きくするとどうなるか?

4 伝送速度と誤り確率 R log M 1 = = n n 伝送速度 ( レート ) 送信記号の種類の数 1, ならばビット誤り率繰り返し回数を限りなく多くとると誤り確率は限りなくゼロに近づくが同時に伝送速度もゼロになってしまう ( n) lim fe = n 実用的ではないしかし R < C 通信路容量ならば限りなく小さな誤り確率での情報伝送が可能通信路での反転確率

5 通信路容量 C = max I( X; Y) P X I( X; Y) = H( Y) H( Y X ) X : 入力 Y : 出力通信路容量の定義相互情報量 : 入力 X を知ったときに出力 Y に対して得られる知識の増加分入力の確率分布に関して相互情報量を最大化したものが通信路容量通信路容量は通信路が伝送できる最大の情報量という意味を持つ

6 通信路容量の計算例誤りの無い元対称通信路 1- P ( ) = P (1 1) = 1 YX YX P ( 1) = P (1 ) = YX YX 条件付き確率での表現グラフ表現 HY ( X) = log (1 ) log(1 ) { } C = I( X; Y) = max H( Y) H( Y X) = 1 h( ) P X = 1+ log + (1 )log(1 ) 入力分布によらない BSC の通信路容量同様にガウス通信路に対して通信路容量は C 1 = max I( X; Y) = log 1+ a a

7 通信路符号化定理通信路符号化定理 i) R< Cなる任意の速度 R= log M n に対し ii) 任意に小さな復号誤り率 R> CなるRに対し任意に小さな E の符号が存在する E の符号は存在しないゼロでなくてもよいしかし符号長 n を無限大ととることは必要情報源の記号数 M = nr この定理をランダム符号と呼ばれる符号に対して証明していく

8 ランダム符号情報源の記号 :,,..., ( 等確率で生成される ) 符号化 : 1 S1 S S M S, S,..., S の各々にランダムに,1を n個並べた系列を割りあてる S S S S 1 3 M M 符号長 n 各ビットに ½ の確率で,1 を割り振る M nr = < n R 1 として議論を進めるこれらを元対称通信路を介して転送する状況下で定理を証明していく

9 通信路符号化定理の証明 #1 一つの符号語が転送により拡大する大きさの評価入力出力 1- 転送によりオリジナルな符号語が取りうる場合の数 ( ) nh 典型的な系列の個数 z = = 符号語は元対称通信路を介して転送されるある符号語 S 1 = は通信路の雑音により1 11として受信される全 nビットのなかで誤りの生じるビット数はおおよそnと見積もられる (1 11), (111 1),, (11 111) n ビットの誤り n ビットの誤り n ビットの誤り通信路出力の典型的な系列典型的な系列のなかの一つが現れる確率 n n(1 ) nlog n+ n(1 )log(1 ) nh( ) = (1 ) = = 値エントロピー関数

10 通信路符号化定理の証明 # 復号誤り率の評価 S3 復号誤りが生じるのは S 受信される可能性のある 3 nh( ) S, S,..., S の ( M 1) 個のいずれかに間違って復号されるとき M 個の各々が実際に送信された符号語 S 以外の ( M 1) M = = = nh( ) nh( ) n( R + 1 h( )) n( R C) E n n 受信される可能性の (M-1) 個のいずれかある系列の個数が選ばれる確率 i) の証明終わ 1 ( C= 1 h( ) > R)

11 通信路符号化定理の証明 #3 ii) の証明受信系列の全ての可能性 1つの符号語に対する通信路出力の典型列を収める箱の数 = z = n M n 箱箱元対称通信路により実際に得られる典型列の数は全てこの箱に収まらなければならない n nh( ) n( C R) > > 1 M これはR> Cでは満たされない nh( ) ii) の証明終わり

12 スピンモデルを用いた符号 / 復号化ビット列を送るのではなく結合 = ξ ξ ij i j を送信エネルギー関数 H = ij ξ ξσσ i j i j エネルギー関数の最小状態を選ぶことで復号する = ξ ξ ij i j ノイズが無い場合 = ξ ξ ij i j ノイズのある場合フラストレーション無しエネルギー最小を与える配列が非自明 ( スピングラス ) フラストレーションフラストレーション ( 笑ってはいるが顔色が悪い ) ( 笑ってはいるが顔色が悪い ) ノイズにより反転したボンド

13 パリティと画素の同時送信 = ξ ξ ij i j 画素だけではなく隣接画素対も同時に送信する ( 正方格子で N 個ある ) 尤度 P ({ },{ τ} { σ} ) = パリティ送信部分 β ijσiσ j+ h ij τ i iσi e [cosh ] [cosh ] NB ( β ) ( h) 画素送信部分 N 事後分布とエネルギー関数 P ({ σ} { τ} ) = e H eff Heff e { σ} 事前分布の部分 H = β σσ σσ h τσ eff ij ij i j ij i j i i j MAP 復元 MPM 復元を行う

14 復元結果ビット誤り率パリティ有りパリティ無し原画像 % 劣化画像パリティ項の割合パリティ無し MPM 復号パリティ有り MPM 復号冗長性を付加することによりより効果的な復元が実現される

15 Sourlas 符号 N 個のビットの中から個をピックアップして送信する i i = ξi ξi 1 1 オリジナルビットの個の積を送る速度 R N = C N! 1 N ガウス通信路で送信 P i 通信路 ({ } { }) ( ) ( ) 1 1 N N! ξ = ex i i ξ 1 i ξi C π!! N i < < i ( a ) a = log ! N log 1 1 R C シャノンの限界式 = 1 log

16 P 事後確率 { σ} { } ( ) 平均場理論による性能評価 = e β σ σ { σ} i1 < < i i1 i i1 i e β σ σ i1 < < i i1 i i1 i 磁化 1 H ( ) m= σ i = Dxtanh G β q 1 ( ) q = σ i = Dxtanh G G = x + β m エネルギー関数レプリカ法から得られる状態方程式スピングラス秩序変数 = β σ σ eff i1 < < i i 1 i i 1 i セルフコンシステントに解く ( ) ( ( ) ) 1 ξ1 sgn σ 1 sgn ( ) i 1 1 Pb = = Dx G ビット誤り率

17 解析結果 #1 磁化スピングラス秩序変数強磁性常磁性相転移 = 3 シグナルノイズ比 =.8 ビット誤り率復号可能相復号不可能相転移

18 解析結果 # 温度に関する最良性ビット誤り率 = 3 =.8 西森温度 = 3 =.8 T =

19 解析結果 #3 磁化低温ではスピングラススピングラス秩序変数高温では常磁性 = 3 =.6 シグナルノイズ比ビット誤り率誤り訂正不可能

20 解析結果 #4 の増加につれて減少 : log, = 強磁性相の存在限界 R C Sourlas 符号は漸近的にシャノン限界を達成する次回は CDMA に移ります

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 通信路 (7 章 ) 通信路のモデル情報送信者通信路受信者 A a,, a b,, b B m = P( b ),, P( b m ) 外乱 ( 雑音 ) n = P( a,, P( a ) n ) 送信情報源 ( 送信アルファベットと生成確率 ) 受信情報源 ( 受信アルファベッと受信確率 ) でもよい生成確率 ) 受信確率 ) m n 2 イメージ外乱 ( 雑音 ) により記号 a