大学院総合コミュニケーション科学 第②回 （ 4月13日） 担当： 情報・通信工学専攻 情報通信システムコース 川端 勉 教授

Presentation on theme: "大学院総合コミュニケーション科学 第②回 （ 4月13日） 担当： 情報・通信工学専攻 情報通信システムコース 川端 勉 教授"— Presentation transcript:

1 大学院総合コミュニケーション科学 第②回 （ 4月13日） 担当： 情報・通信工学専攻 情報通信システムコース 川端 勉 教授
情報通信システムの設計原理 大学院総合コミュニケーション科学　　 第②回　（ 4月13日） 　 担当：　情報・通信工学専攻 情報通信システムコース 川端　勉　教授 TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAAAAA

2 講義の目的 情報通信システムの設計原理がどのような過程を経て成立したのかを理解する。
その過程で明らかになった情報量の概念を符号化定理において意味付けする． 情報量概念がネットワーク情報通信の問題の体系化にどのように用いられているか触れる。

3 情報通信システムの設計原理がどのような思考過程で成立したのか

4 離散データに対する 通信のモデル 離散データ Xn 情報源 送信機 信号 通信路 離散データ Xn 受信者 受信機 信号
　　離散データに対する 　　　通信のモデル　 離散データ　 Xn 情報源 送信機 信号 データレート：　Fsサンプル毎秒 通信路 離散データ Xn 受信者 受信機 信号 問題：離散データを無歪みで再現するような、送信機受信機が作れるか？ 　　　　（ただし、送信電力は固定する）

5 情報通信のモデル（Shannon-Fano)
離散情報源データに対する 情報通信のモデル（Shannon-Fano) 離散 データ ビットデータ 情報源 情報源 符号化 （圧縮） 通信路 符号化 信号 Xn データレート：　Fsサンプル毎秒 定常性を仮定 定常 通信路 離散 データ ビットデータ 受信者 情報源 復号化 （解凍） 通信路 復号化 Xｎ 信号 問題１：　情報源からの離散データを復元可能な条件で, 圧縮（情報源符号化）する時, 圧縮 後のビットレート（ビット毎秒）はどれだけ必要か？　 　　　　　　　　答：　Fs x H　 （但し　H　は情報源のエントロピー(ビット毎サンプル）） 問題２：　通信路を通して伝送可能なデータレート（ビット毎秒）の最大値は？　 　　　　　　　　答：　C　（通信路の容量(ビット毎秒）） 問題３：　Fs x Ｈ＜C　なら通信ができる。逆に　 Fs x H >C　なら通信ができないか？　　　

6 （最も古典的）なアナログ通信のモデル 信号 Xｓ(t) 情報源 送信機 信号 定常 通信路 信号 Xｄ（ｔ） 受信者 受信機 信号
（最も古典的）なアナログ通信のモデル　 信号　Xｓ(t) 情報源 送信機 信号 定常性、帯域(－Fs/2,Fs/2) 制限を仮定 定常 通信路 信号　Xｄ（ｔ） 受信者 受信機 信号 問題：　時間当の信号歪みを平均的に一定値以下にするような、送信機受信機が作れるか？　（ただし、送信電力は固定する）

7 アナログ信号に対する情報通信のモデル 信号 ビットデータ 情報源 情報源 符号化 通信路 符号化 信号 定常 通信路 信号 ビットデータ
Xs(t) 定常性、帯域(－Fs/2,Fs/2) 制限を仮定 定常 通信路 信号 ビットデータ Xd(t) 受信者 情報源 復号化 通信路 復号化 信号 問題１：　時間当たり信号歪みを平均的に一定値（ｄ)以下にするためには情報源符号化 の出力ビットレート（ビット毎秒）として最低どれだけを必要とするか？　　　R0(d)　 問題２：通信路を通してビットテータの信頼性が確保されるためには，そのレート（ビット 　　　　　毎秒）としてはどこまで許されるか？　　C 問題３：R0(d) ＜C なら所望の通信ができる。では逆の不等号ならできないか？　　　

8 アナログ信号に対する情報源符号化のモデル
Xs(t) ビットデータ 定常性、帯域(－Fs/2,Fs/2) 制限を仮定 信号 情報源 復号化 Xd(t) 受信者 問題１：時間当たり信号歪みを平均的に一定値（d)以下にするためには情報源符号化 の出力ビットレート（ビット毎秒）として最低どれだけを必要とするか？　　　R0(d)　

9 ＝標本化＋離散時間有歪みデータ圧縮・解凍
アナログ信号に対する情報源符号化 ＝標本化＋離散時間有歪みデータ圧縮・解凍 信号 離散時間 データ　Xｓ,n 情報源 Xs(t) バイナリ データ 有歪み データ 圧縮 標本化 定常性、帯域(－Fs/2,Fs/2) 制限を仮定 信号 離散時間データ　Xd,n Xd(t) 平滑化 受信者 有歪み データ 解凍 ･　処理１：信号Xs（ｔ）をレートFsで標本化する．標本化定理により、Xs(n/Fs)=Xs,n ならびにXｄ(n/Fs)=Xｄ,n が成立． ・　問題２：　離散時間データXs,nを有歪みデータ圧縮解凍する。許容歪みをD (毎サンプル）とする．最低どれだけのデータレート（ビット毎サンプル)が必要か？ 答え：R(D)とする．　 ・　R0 （ｄ）　はどうなるか？:　答え　Ｒ０（ｄ）＝Ｒ（ｄ/Fs）Fs

10 情報通信のモデル（データの暗号化の挿入）
信号 データ データ 情報源 情報源 符号化 暗号化 通信路 符号化 信号 通信路 信号 データ データ 受信者 情報源 復号化 暗号の 復号化 通信路 復号化 信号 ・　情報源符号化後のデータに冗長性が含まれていると、情報論的に安全な暗号化の ためにはその冗長性に相当するビットレートの暗号鍵が必要である。

11 情報量　H （エントロピー）, C （通信路容量）, R(D)（レート歪み関数）の符号化定理による意味付け

12 無歪み情報源符号化 例：二進{0,1}ファイルの符号化
無歪み情報源符号化 例：二進{0,1}ファイルの符号化 Xn : 長さn二進列, ｋ:　Xn 中の１の数，　logの底は２ 符号化：ｋの表現＋組合せｎCk個内での番号表現 符号長：（高々）　　log （n＋１）+logｎCk＋２ 符号長の主要項： 　logｎCk =log n!-logk!-log(n-k)! ~nlogn –klogk –(n-k)log(n-k) 　　　　　 =-klog(k/n)-(n-k)log((n-k)/n) =nH(k/n) 但し、H(θ）：＝ θlog １/θ+（1－θ）log 1/（1－θ） 　　　二進エントロピー関数

13 確率 データ ｘｎが出現する確率をｐ（ｘｎ）とかく ｐ（ｘｎ） は非負 Σｐ（ｘｎ）＝１, 和はデータｘｎ全てについて
データ　ｘｎが出現する確率をｐ（ｘｎ）とかく ｐ（ｘｎ） は非負 Σｐ（ｘｎ）＝１, 　和はデータｘｎ全てについて l(ｘｎ ) = データｘｎ の符号語c(ｘｎ)の長さ 期待符号長　 Σｐ（ｘｎ）ｌ（ｘｎ）

14 期待符号長に関する不等式： Σｐ（ｘｎ）ｌ（ｘｎ）≧ Σｐ（ｘｎ）log 1/ｐ（ｘｎ）
Σ２-l(xn)≦１　 (1) 　　　　　証明： ２-l(xn) ≦１/(n+1)ｎCk （表題式の）左辺ー右辺 ＝Σｐ（ｘｎ）ｌ（ｘｎ）＋Σｐ（ｘｎ）log ｐ（ｘｎ） ＝Σｐ（ｘｎ）log ｐ（ｘｎ）/ ２-l(xn) ≧ log 1/Σ２-l(xn) 　ｐｆ：　Log和不等式：　a, b,…,A,B,…正数 　　　　　　　　　　a log a/A +b log b/B +… 　　　　　　　　　　　　　　　　　　≧（a+b+…) log (a+b+…)/(A+B+…) ≧０ 　　実は，全ての”一意復号可能な”符号について，（１)式（Kraftの不等式）が成り立つ，すなわち全ての一意復号可能な符号について表題の式が成り立つ．

15 偏りのあるコイン投げ情報源のエントロピー
偏りのあるコイン投げの結果生じる時系列Xn=X1,X2,…,Xn を情報源とする。 P(Xm=表)＝１－P(Xm=裏)=:θ, 1≦ｍ≦n 　とおく， 但し０≦θ≦１ H(Xn)=Σｐ（ｘｎ）log 1/ｐ（ｘｎ） 　　　　　=ΣｍΣｘｎ　ｐ（ｘｎ）log 1/ｐ（ｘｍ） 　　　　　＝ｎ Σｘ　ｐ（ｘ）log 1/ｐ（ｘ） 　　　　　＝ｎH(θ）　　←　nH(k/n) 一般に　（1/n) H(Xn) 　のｎ→∞　の極限が存在するときこれを情報源のエントロピーと呼ぶ。従って，偏りのあるコイン投げ情報源のエントロピーはH(θ）

16 定常情報源符号化定理 　定常な情報源はエントロピーＨをもつ。この情報源の出力を一意復号可能な符号により符号化するとき二進記号当たりの符号長の期待値はHで下界される。一方ブロック長nを十分大きくとれるならば一意復号可能な二進情報源符号で１二進記号当たりの期待符号長がHに任意に近いものが構成できる。

17 通信路容量 離散無記憶通信路は，時間的に独立な離散時間確率的入出力システムであって，入力がiのときに，jを出力する条件付確率　p(j|i)　を与えることにより定まる． 通信路容量 Ｃ （単位：ビット/記号）は次式で与えられる． 　　　 　C＝ ただし， q(j)は出力分布 q(j)=Σr(i)p(j|i)とする． 例：クロスオーバ確率μ（μ＝p(0|1)=p(1|0)）の二元対称通信路の場合　Ｃ＝１+μlog μ＋（1-μ）log (1-μ)

18 ブロック長n,レートＲの 通信路符号化/復号化：
｛１,…2ｎR｝をメッセージ集合という 通信路符号化とは　　　φ：｛１,…2ｎR｝ Χｎ 通信路の入出力　　　　　Χｎ　→　Ｙｎ 通信路復号化とは　　　　ψ：Ｙｎ ｛１,…2ｎR｝ 平均ブロック誤り確率：等確率で選ばれたメッセージが上の処理の結果元のメッセージに戻らない確率

19 離散無記憶通信路に関する通信路符号化順定理
通信路容量がＣで与えられる離散無記憶通信路について、ブロック長ｎさえ長くとればレートＲが任意にＣに近く，平均ブロック誤り確率も任意に小さいブロック符号器/復号器を構成することができる．

20 離散無記憶通信路に関する通信路符号化逆定理
通信路容量Ｃの離散無記憶通信路について，レートがＲ（Ｒ＞Ｃ）以上のブロック長ｎの通信路符号化/復号化をどのように選んでも平均ブロック誤り確率に対するｎによらない正の下限が存在し，さらにｎが十分大ならばその誤り確率は１に漸近する。

21 加法的白色ガウス通信路の容量 （Ｓｈａｎｎｏｎ １９４８）
加法的白色ガウス通信路の容量 （Ｓｈａｎｎｏｎ　１９４８） 信号帯域：　（-Ｗ,W) or |ｆ±fc|<W/2 (Ｈｚ) 白色雑音スペクトル密度：　Ｎo/2　（ワット/Hz) 送信全電力： Ｐ　（ワット） 容量：　Ｗ log (1+P/(WN0)) 　　（ビット毎秒） 　　　あるいは　Ｗ log (1+SN比）　（ビット毎秒）

22 レート歪み関数（離散時間無記憶情報源の場合）
・離散時間無記憶情報源　Xs,n は（一般には）連続入力アルファベットＸ上の確率分布p(x),x∈Ｘ によって特徴つけられる． ・圧縮による歪みは所与の二変数関数 ρ（Ｘs,ｎ, Xd,n） の期待値によって評価される． ・レート歪み関数Ｒ（Ｄ）は次式で定義される．

23 離散時間白色ガウス情報源のＲ（Ｄ） Xｓ,n～N(0,σ２), 無記憶 歪み尺度：期待二乗誤差 E(Xs,n-Xd,n)2
R(D)=(1/2) max{ log σ２/D, 0}

24 レート歪み順定理（離散時間無記憶情報源の場合）
任意の正数εについて，ブロック長ｎを十分長くさえとれば，レートがＲ（Ｄ）＋ ε以下のnブロック符号器，ｎブロック復号器が存在し，その平均期待歪みをＤ＋ε以下にすることができる。

25 レート歪み逆定理（離散時間無記憶情報源の場合）
　ブロック長ｎが何であれ，レートがＲ（Ｄ）以下の任意のｎブロック符号器・復号器を用いて達成可能な平均期待歪みはＤ以上である。

26 情報概念によるネットワーク情報通信の問題の体系化

27 ネットワーク情報通信 MIMO（Multi-Input Multi-Output 通信）は本質的に1対１の通信路であり、ネットワークを構成しているとはいえない。 ネットワーク通信の分類　情報源符号化と通信路符号化に大別 情報源符号化 　　　　Slepian-Wolf 問題：センサーネットワーク 　　　　Successive Refinement問題（画像符号化） 　　　　Multi-Description問題（ビデオ符号化）

28 例：Slepian-Wolf 問題（相関のある2無記憶情報源の独立符号化の問題）
下図に示す符号化復号化が可能であるための必要十分条件）：Ｒｘ>H(X|Y)，Ｒｙ>H(Y|X)，Ｒｘ＋Ｒｙ>H(X,Y) (=H(Y)+H(X|Y)) Ｘｎ 圧縮率　Ｒｘ のデータ 符号器Ｘ 復号器ＸＹ Ｘｎ Ｙｎ 圧縮率　Ｒｙ のデータ Ｙｎ 符号器Ｙ ・　復号器がＹを補助情報として得ているならば、符号器Ｘは　H(X|Y) だけの情報量で十分

29 ネットワーク情報通信（情報源符号化） データ圧縮率は情報源あるいは伝送パスが複数あるため一般にベクトルで表現される。基本的な情報源モデルについて許容歪みに関する条件をみたす圧縮率ベクトルに関する必要十分条件を情報理論的に単一文字化して決定する問題が重要（未解決問題多い）

30 ネットワーク情報通信（通信路符号化） 通信路符号化 多重アクセス通信 多対１ 放送型通信 １対多 干渉型通信 多対多 リレー通信
　　　　多重アクセス通信　多対１ 　　　　放送型通信　　　　　１対多 　　　　干渉型通信　　　　　多対多 　　　　リレー通信 　　これらの問題に関しても、通信路符号化レートベクトルが定義される。通信の信頼性が確保されるためのレートベクトルが満たす必要のある条件を情報理論的に（単一文字化して）決定する問題が重要。

31 まとめ 情報通信システムの設計原理がどのようなプロセスを経て成立したのか説明した。
明らかになったH,C,R(D)などの抽象的情報概念を符号化定理として意味つけした． 情報概念がネットワーク情報通信の問題の体系化にどのように用いられているか簡単に触れた。

32 ご清聴ありがとうございました

33 本スライドへのアクセス （課題を含む）本講義のスライドは、川端研究室のＨＰ
から「大学院総合コミュニケーション科学」 をたどることにより得られる。

34 課題１ 以下の論文①②③のうちいずれかを読んで、講義との関連で考察しなさい。
　以下の論文①②③のうちいずれかを読んで、講義との関連で考察しなさい。 ①「多次元球の体積と表面積ー初等的導出と通信理論における意味」　　川端研究室ＨＰ　 にリンクがある. Ｃ．Ｅ．シャノン著, W. ヴィ－ヴァー著，植松友彦訳，「通信の数学的理論」筑摩学芸文庫，　ISBN: 　　に収録されている ②　W. ヴィ－ヴァー著の論文 ③　Ｃ．Ｅ．シャノンの論文

35 課題２ 本講義のスライドが川端研ＨＰ