情報通信システム（6） http://www10.plala.or.jp/katofmly/chiba-u/ 2015年6月9日 火曜日 午後4時10分～5時40分 NTT-IT Corp. 加藤 洋一 千葉大学 6- 2 通信速度の単位 • • • • • bps Kbps Mbps Gbps Tbps 1秒間に伝送される「ビット」の数 bpsの1,000倍の単位 Kbpsの1,000倍の単位 Mbpsの1,000倍の単位 Gbpsの1,000倍の単位 • 通信速度の場合には、通信速度は通常「ビット／ 秒」で表現される。バイト（＝8ビット）／秒もまれに使 われるので注意が必要。 • 一方、ファイルの大きさなど、データ量を表す場合に は、「バイト」を単位とするのが普通。 – さらに、ファイルなどの場合、K=1,024、M=1,048,576 （1,024の２乗）などの場合もあるので要注意。 千葉大学 6- 3 通信システムの速度 通信システム ディジタル通信速度 注釈 音響カプラー 300bps 講師は昔卒研で使った。 電話回線 ISDN ADSL 最大56Kbps モデムを使う。 64Kbps～128Kbps 上り １Mbps 下り 1～20Mbps 上り 7.4Mbps 下り 39Mbps 唯一のディジタル交換網 実効値は千差万別 FOMA 上り 64Kbps 下り 384Kbps パケット LTE 上り 80Mbps 下り 300Mbps ～100Gbps パケット FTTH 基幹網光 講師自宅実測 DWDM 千葉大学 6- 4 音声と画像の無圧縮時情報速度 メディア 周波数帯域、 標本化周波数、 チャンネル数 ビット数/標本 無圧縮時 ビットレート 電話音 声 3.4KHz 1チャンネル 8KHz 8ビット 64Kbps 音楽 ２０KHｚ 2チャンネル 44.1KHz,48KHz 1.4Mbps 16ビット ビデオ （SD） 4.2MHz 13.5MHz,14.3M 108Mbps~ Hz 8ビット HDTV ２０ ~30MHｚ 1920*1080*30 8ビット 3840*2160*60 4K 1.6Gbps~ 12bps 千葉大学 6- 5 音声と画像の情報量圧縮の目的 • 伝送コストを安くしたい。 – 携帯電話 – ビデオ伝送 • 効率よく蓄積したい – ビデオ – 音楽 – 映画 千葉大学 6- 6 （あらためて）「情報量」とは何か？ • 「情報量」とは、捉え方によって異なる。 – 「横浜ベイスターズが勝った」という情報は、ファンには意 味があるが、野球に興味のない人には無意味な情報であ る。つまり「情報量０」。 – 通信工学という立場からは、受信側の情報の「捉え方」は 問題にしないこととする。 やった！ 情報：横浜ベイスターズが勝った！ 俺には関係ないね。 千葉大学 6- 7 情報量（定義） いま、 N個の記号から、ひとつ が選択されるとする。 記号を S 1, S 2, S 3......SNとする。 S 1, S 2, S 3......SNが生起する確率を p1, p 2, p 3...pN とする。当然、 p1 p 2 p 3 .. pN 1である。 ここで、記号 Siが選ばれたときの情報 量を log piと定義する。 （事象の生起確率は pと書かれることが多い 。これは確率の英語 「 probability」の pである） さて、0 pi 1なので、 log piは正の実数となる。 nat bit 対数の底がeのとき、単 位はnat（なっと）という 10 8 対数の底が2のとき、単 位はbit（びっと）という 15 10 6 4 P=0.5のとき1ビット 5 2 0.2 0.4 0.6 0.8 1 p 0.2 確率が小さいほど、情報量は多い。 0.4 0.6 0.8 1 p 千葉大学 6- 8 情報量の期待値＝平均情報量＝情報エントロピー いま、 N個の記号S 1, S 2, S 3......SNから、ひとつが選択さ れる直前である。 S 1, S 2, S 3......SNが生起する確率は p1, p 2, p 3...pNなので記号が選択され た時に 得られる情報量 log piは不明である。しかし 、その期待値は、 得られる情報量の平均 として下の式で計算で きる。 N p N i i 1 ( log pi ) pi log pi （発生確率 情報量）の総和 i 1 これを情報エントロピ ーという。 簡単な例：赤い玉と黒 い玉が同数袋に入って いる。そこから玉をひ とつ 取り出す。赤い玉を取 り出す確率は、 p1 0.5、黒い玉を取り出す 確率は、 p 2 0.5である。このときの情 N 報エントロピーは、 p log p 0.5 log 0.5 0.5 log 0.5 1bit と計算できる。 i i 1 i 2 2 千葉大学 6- 9 エントロピーの性質 前頁の例で、赤球が 75個、黒球が 25個であるとすると、 赤だまの確率 p1 0.75、黒い玉の確率 p 2 0.25、情報エントロピーは 、 N p log p 0.75log 0.75 0.25log 0.25 i i 2 2 i 1 0.811bit と計算できる。 entropy 前頁では、赤黒の生起確 率は0.5で情報エントロピー は1bitだった。 1 ２つの事象の生 起確率とエントロ ピー 0.8 0.6 0.4 0.2 0.2 0.4 0.6 0.8 p1 ( = 1 – p2) 一般に、場合の数をNとすると、それぞれの事象の発生確率が1/Nのとき（即ち、全て 同じとき）、エントロピーが最大となり、その値は、log2(N)となる。逆に、発生確率が 「片寄る」と、エントロピーは減る。 千葉大学 6- 10 Harry Potter and the Order of Phoenix Harry Potter and Order of the Phoenix, J.K. Rowling Chapter One “DUDLEY DEMENTED” The hottest day of the summer so far was drawing to a close and a drowsy silence lay over the large, square houses of Privet Drive. Cars that were usually gleaming stood dusty in their drives and lawns that were once emerald green lay parched and yellowing; the use Of hosepipes had been banned due to drought. Deprived of their usual car-washing and lawn-mowing pursuits, the inhabitants of Privet Drive had retreated into the shade of their cool houses, windows thrown wide in the hope of tempting in a nonexistent breeze. The only person lea outdoors was a teenage boy who was lying flat on his back in a Rower bed outside number four. 各文字の発生頻度 …………………. 最初の9ページ分 文字数 15717 文字の種類の数 28 （大文字と小文字を区別 しないこととした） エントロピー 計算結果 4.15 bit ‘ ‘ 2840 . 197 a 1032 b 217 c 266 d 640 e 1554 f 213 g 325 h 879 i 800 j 11 k 117 l 486 m 234 n 956 o 876 p 224 q 9 r 794 s 781 t 1075 u 388 v 132 w 346 x 10 y 306 z 9 千葉大学 6- 11 効率的な符号化 • 前頁の例では、場合の数は28であった（26のアルファベット ＋スペース＋ピリオド）。この28のシンボルを2進数で表すこ とを考える。 • 最も簡単な方法は、1シンボルあたり、5ビットの数字をひとつ ずつ割り付ける方法である（5ビットでは、2の5乗、即ち32個 のシンボルを表すことができる）。これを固定長符号化という。 • エントロピーの実測値は4.15bitなので、この方法では、元来 の情報量の約20%増の符号量となり得策ではない。 固定長符号化の例 ‘ ‘ 00000 . 00001 a 00010 b 00011 c 00100 d 00101 e 00110 F 00111 g 01000 h 01001 i 01010 j 01011 k 01100 l 01101 m 01110 n 01111 o 10000 p 10001 q 10010 r 10011 s 10100 t 10101 u 10110 v 10111 w 11000 x 11001 y 11010 z 11011 （11100から 11111までの4つ の符号は使用し ない） 千葉大学 6- 12 効率的な符号化（可変長符号化） • 前頁の例では、固定長(5bit)の符号を用いた。固定 長の符号は扱いやすいが、効率が悪い場合がある。 • 符号には固定長の他に、可変長符号がある。 例： 袋には4種類の玉が入っている。赤と黒は10個ずつ、 白は20個、黄色は、40個とする。全部で80個。玉をひとつ取り出したときの発生 確率は、黄色 50%、白25%、赤12.5%、黒12.5%である。 以下のような符号を割り振る。 黄色 0 白 10 赤 110 黒 111 玉を16回取り出したところ（出したら元に戻してかきまぜる） 黄 白 黒 黄 黒 白 黄 赤 黄 白 黄 白 黄 赤 黄 黄 とでた。これを符号化すると、 0 10 111 0 111 10 0 110 0 10 0 10 0 110 0 0 となる。詰めて表示すると、 0101110111100110010010011000 (total 28bit) これを復号してみる。左のビットから順番に見ていくと、まず0なので直ちに決まって黄、次 は1なので決まらずさらに次を見ると10つまり白、というように、正しく復号できる。 場合の数は4なので、固定長符号なら2ビット、16シンボル分では32ビットとなる。可変長 符号化の場合には28ビットだったので、効率が上がったことが分かる。 千葉大学 6- 13 効率的な符号化方法（ハフマン符号化） • 効率的な可変長符号を決める方法のひとつとして、ハフマン 符号化がある。手順は以下のとおり。 1. シンボルについて、その生起確率の小さいものから２つを探 す。 生起確率が最小のシンボルに”0”、2番目に小さいシンボル に”1”の符号を与える。シンボルが、（３）の合成シンボルの場 合、合成前のオリジナルのシンボル全てに符号を与える。 この２つのシンボルを合わせてひとつのシンボルと考える（合 成シンボル）。新しいシンボルの生起確率は元の値を足した ものとする。 1-3の操作で、全体のシンボル数はひとつ減る。全体のシン ボル数が1になるまで1-3の操作を繰り返す。 終わり。 2. 3. 4. 5. 千葉大学 6- 14 効率的な符号化方法（ハフマン符号化） ‘‘ . a b c d e f g h i j k l 111 010010 1010 100000 110001 11010 000 010011 110110 0111 0101 1100101011 11001011 10001 m n o p q r s t u v w x y z 110000 1001 0110 100001 1100101000 0011 0010 1011 01000 1100100 110111 1100101010 110011 1100101001 前述のHarry Potterのテキスト の各文字発生確 率から生成したハ フマン符号 • 生起確率の高いシンボルほど短い符号が割り当てられている。 • 平均符号長 4.18 （エントロピーは4.15ビットだった） • 固定長符号化に比べ、ずっと効率が良い。 千葉大学 6- 15 確率事象の結合 今、二つの確率事象 xと yを考える。 xのシンボルに 1, , , i, , ,と番号を 振る。同様に、 yのシンボルは、1, , , j , , ,と表す。それぞれのシ ンボル の発生確率を p(i ), p( j )と表す。さらに、 xと yを組で発生させる。こ とき xはiが発生し yはjが発生する確率を p(i, j )と表す。エントロピー H ( x, y ) p(i, j )log p(i, j ) の は、 となる。 i, j なお、 p(i ) p(i, j ), j ところで、片方だけの p( j ) p(i, j ) となることは明らかで あろう。 i 確率事象に注目したと きのエントロピーを、 それぞれ、 H ( x)、 H ( y )とする。このとき、 H ( x, y ) H ( x ) H ( y ) となる。つまり、２つ の確率事象を結合した 事象のエントロピーほ うが、 それぞれの事象のエン トロピーの和より小さ これを次ページ以降で 証明する。 くなる、ということで ある。 結合確率 j p(i ,j) i 千葉大学 6- 16 Triangle Circle Rectangle Star Red 0.0500 0.0600 0.0300 0.0600 0.20 Blue 0.0750 0.0900 0.0450 0.0900 0.30 Yellow 0.0375 0.0450 0.0225 0.0450 0.15 Pink 0.0875 0.1050 0.0525 0.1050 0.35 0.25 0.30 0.15 0.30 Triangle 25 Circle 30 Rectangle 15 Star 30 Red 20 Blue 30 Yellow 15 Pink 35 p(i) p(j) 独立な場合 結合確率 j p(i ,j) i 千葉大学 6- 17 Triangle Circle Rectangle Star Red 0.1000 0.0100 0.0700 0.0200 0.20 Blue 0.0250 0.1400 0.0050 0.1300 0.30 Yellow 0.0775 0.0050 0.0625 0.0050 0.15 Pink 0.0475 0.1450 0.0125 0.1450 0.35 0.25 0.30 0.15 0.30 Triangle 25 Circle 30 Rectangle 15 Star 30 Red 20 Blue 30 Yellow 15 Pink 35 p(i) p(j) 独立でない場合 千葉大学 6- 18 確率事象の結合 xと yが独立なときは、 p(i, j ) p(i ) p( j )であるから、 H ( x, y ) p(i, j )log p(i, j ) p(i ) p( j )log p(i ) p( j ) i, j i, j p(i ) p( j )log p(i ) p(i) p( j )log p( j ) i, j i, j p( j ) p(i )logp(i ) p(i ) p( j )logp( j ) j i i j H ( x) H ( y ) log p(i ) p( j ) log p(i ) log p( j ) p(i) p( j )log p(i) p( j ) p(i)log p(i) i, j i, j p( j ) p(i)logp(i) j i p( j ) 1 j 参考 x1y1+x1y2+x1y3+… x2y1+x2y2+x2y3+… …. = (x1 + x2 + x3 + …)(y1 + y2 + y3 …) 千葉大学 6- 19 結合確率のエントロピー とき、 yが jになる条件付確率を、 xの値が iであることが分かった pi ( j )とする。 pi ( j )は、 pi ( j ) p (i, j ) p (i ) p (i, j ) である。 (注) p (i, j ) p (i ) pi ( j ) p(i, j ) j このときのエントロピ ー pi ( j ) log pi ( j )は、 xの値が判明したときの yの j エントロピーなので、 H x ( y )と書くことにする。 H x ( y ) pi ( j ) log pi ( j ) p (i ) pi ( j ) log pi ( j ) p (i, j ) log pi ( j ) i j (注) p (i ) 1 さらに計算を進めると i, j j 、 i H x ( y ) p (i, j ) log i, j p (i, j ) p (i, j ) log p (i, j ) p (i, j ) log p (i, j ) j i, j p(i, j ) i, j j H ( x, y ) H ( x ) (注) p (i, j ) log p (i, j ) p (i, j ) log p (i ) i, j j i, j i p(i, j ) log p(i) p(i) log p(i) j i 千葉大学 6- 20 結合確率のエントロピー H ( x, y ) H ( x ) H x ( y ) 前頁の式から、 さて、 xと yが独立のときは、 H ( x, y ) H ( x) H ( y ) が得られる。 であった。 ところで、 H ( y ) はyのエントロピー、 H x ( y ) は、 xの値が判明したときの yのエントロピーである 従って、 H x ( y ) H ( y )は明らかであろう。つ からといって、 H ( y )が増加することはあり 。 まり、 xの値が判明した えない。 xと yが全く無関係 の場合には、等号が成 り立つし、 xが分かると yの値が予想しやすくな る 場合には、不等号とな る。上の２つの式を比 H ( x, y ) H ( x ) H ( y ) べると、 が成立することが分か る。 重要：つまり、各々の事象のエントロピーより結合事象のエントロ ピーの方が小さい（あるいは等しい）、ということになる。 千葉大学 6- 21 結合確率 • 前頁の性質を使うと、情報量の圧縮ができる。つま り、複数のイベントの結合確率p(i,j,…)を求め、その 複数のイベントをまとめて符号化すれば、イベントを ひとつずつ符号化するより出力符号量を減らすこと ができる。 • 例えば、 イベント１は、テキストの奇数番目の文字 イベント２は、テキストの偶数番目の文字 と考え、文字を２つずつ組にして符号化することが 考えられる。 The hottest day of the summer so far was drawing to a close and a drowsy silence lay over the large, square houses of Privet Drive. 千葉大学 6- 22 確率事象の結合 • 前述のHarry Potterのテキストで、1文字ずつを事象とした場 合、2文字ずつを事象とした場合、3文字ずつを事象とした場 合で計算してみた。 • 複数の文字をまとめてひとつの事象と捉えることで、一文字 あたりのエントロピー、即ち情報量が減ることが分かる。これ は、隣り合う文字間に何らかの関連があるからである。 事象の 数 1文字 15717 場合の 数 28 エントロ ピー 4.14 一文字あたりの エントロピー 4.14 2文字 7858 385 7.44 3.72 3文字 5239 1521 9.70 3.23 千葉大学 6- 23 確率事象と確率過程 • 「確率事象」とは、「袋から玉を取り出す」ことのよう に、確率的に生起する事象のことを言う。 • 確率事象が連続的に起きる場合、それを「確率過 程」という。 • 通信システムで伝送する信号は「確率過程」である ということができる。 – 信号がメールであれば、一文字一文字が「確率事象」で あり、そのまとまりであるメールは、 「確率過程」である。 – 例えば、音声信号のような一次元信号であれば、サンプ ル値ひとつひとつが「確率事象」であり、その連続である ディジタル音声信号は「確率過程」である。このような場合 の「確率事象」を「確率変数」と呼ぶ。 千葉大学 6- 24 マルコフ過程 • テキスト、音声信号、画像信号などは、時間的、ある いは、空間的に「近い」標本間での関連が高い。 • 例えば、テキストの場合、ある文字の発生確率は、 その直前、さらにその前、．．．の文字により変化す る。このように、ある時点での事象の発生確率がそ れ以前に生起したN個の事象に影響されるとき、そ れを「N次のマルコフ過程」という。 – マルコフ過程は、実際の信号の近似的なモデルとしてよく 利用されている。 • 本講義では「マルコフ過程」について詳しく調べるこ とはしませんが、その概念は覚えておいてください。 千葉大学 6- 25 量子化 • 量子化とは、連続的な値（アナログ値）を飛び飛び の値に「丸める」ことである（ディジタル化）。 • 既に量子化されている信号をさらに粗く「丸める」こ とも「量子化」という場合がある。 • 量子化を行うと、もとの信号との誤差が発生する。こ れを量子化誤差、あるいは、量子化雑音という。 量子化出力 量子化誤差 量子化代表値 真値 千葉大学 6- 26 量子化雑音 量子化出力 量子化出力 真値 細かい量子化 量子化雑音小 代表値数は多くなる 即ち、情報量大 真値 粗い量子化 量子化雑音大 代表値数が少ない 即ち、情報量小 WAVEファイルを量子化する実験を行う。量子化誤差を「量子化雑音」という意味が分か ると思う。 画像ファイルを量子化する実験を行う。画像の場合、劣化は雑「音」ではないが、慣習的 にやはり「量子化雑音」という場合が多い。 千葉大学 6- 27 再生信号の評価 • 前頁で、音声や画像では、「完全再生」は必要ないと 述べた。では、どの程度不完全でも良いのであろう か？ – いくつかの尺度がある。例えば、次の式で与えられる平均 二乗誤差。 元信号をfn、再生された信号を fnとするとき、平均二乗 E ( fn fn) 2 誤差は、 で計算される。 n • しかし、最終的には、複数の人間が実際にオリジナ ル信号と再生信号（復号された信号）を聞き（見）比 べて評価することが多い。 – このような方法を「主観評価」という。 千葉大学 6- 28 量子化雑音のパワー 量子化出力 e=S/2 e=-S/2 真値 「四捨五入」のように 左の図のように等間隔 で量子化する場合を一 様量子化という。量子化 代表値の間隔（ステップ サイズ）をSとすると、量 子化雑音は、以下のよ うに計算できる。 量子化値を決めるとす ると、量子化雑音 eは、 S S から に一様に分布すると考 えられる。量子化雑音 の平均電力は、 2 2 S /2 3 2 1 1 e S 2 S /2 e de [ ] S /2 S S / 2 S 3 12 となる。 千葉大学 6- 29 確率過程の効率的符号化方法？ ここまでの学習をまとめると、信号の効率的符号化方法は、以下のようになるであろう。 信号の標本化と量子化 量子化には、情報量と雑音のト レードオフがある。 Nサンプルずつグループ化する Nを大きくすると、シンボル数が 一サンプルの代表値数のN乗の 比例して増加してしまう。 グループのサンプルの結合確率密度に 従いハフマン符号化を行う 千葉大学 6- 30 現実論 • ディジタル音声信号を符号化しよう。ここで、互いに関係しあ うサンプルをまとめて符号化することで、効率を上げる。この まとまりを、例えば、20サンプルとする（本来、もっと多くのサ ンプルが互いに関連していると思われる）。 • 標本値は、256通りである。20サンプルまとめてひとつの事 象だと考えるので、場合の数は256の20乗となる。 • ハフマン符号を生成するため、 256の20乗のそれぞれのパ ターンの発生確率を求めねばならない。発生確率は、その母 集団から十分なサンプルを収集してそのヒストグラムから計 算できる。しかし、 256の20乗個（49桁）のパターンに対する 発生確率を求めるためのサンプル数は膨大となる。またそ のハフマン符号の生成、利用も容易ではない。 • つまり、この方法は現実的でない。 • 現実的な情報量圧縮符号の「戦略」は次ページ。 千葉大学 6- 31 音声と画像の情報量圧縮の「戦略」 音声、音楽、画像の各標本値は、他の近隣の標本値と関連がある。 即ち、冗長性がある。最初に、信号の性質に着目して、冗長性を削 減することで情報量を減らす。 音声や画像では、完全に再生できなくても支障がない場合が多い。 「完全に再生する」ことをあきらめる事で、さらに情報量を削減する。 最終的に得られた値（シンボル）を効率よくビット列にする。 「完全に再生できない」場合の元信号との差を「符号化雑音」という。 これを目立たせないように、復号の後で何らかの処理を加える。 次回へ続く。。。
© Copyright 2024 ExpyDoc
