混沌系工学特論 #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> i j ( σ ) iσ j ex < ij> 画像の復元では画像の特質を事前分布で表現できる 劣化されたデジタル画像 デジタル画像 確率モデルで表現 伝送路 { τ} 符号 ビット列ノイズの乗ったビット列復元されたデジタル画像 1111111 復号 111111111 { ξ} ビット列の場合は? { σ} 復号 11111111 復元されたビット列

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

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

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

通信路容量の計算例 誤りの無い 元対称通信路 1- P ( ) = P (1 1) = 1 YX YX P ( 1) = P (1 ) = YX YX 1 1-1 条件付き確率での表現 グラフ表現 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

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

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

通信路符号化定理の証明 #1 一つの符号語が転送により拡大する大きさの評価 入力出力 1- 転送によりオリジナルな符号語が取りうる場合の数 1 1 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 ) = = 値エントロピー関数

通信路符号化定理の証明 # 復号誤り率の評価 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)

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

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

パリティと画素の同時送信 = ξ ξ 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 復元を行う

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

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 1+ 1 1! N log 1 1 R C シャノンの限界式 = 1 log

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 ビット誤り率

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

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

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

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