このページでは、情報量と平均情報量(エントロピー)の計算、ハフマン符号化とランレングス符号化による圧縮、PCMでアナログ信号をデジタルにする手順がわかります。
-
記号の書き方(このメモのルール):
- 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
- 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
-
一言で言うと:
- 情報の「量」をビットで測り、データをできるだけ短くし(圧縮)、音などのアナログをデジタルに変える話。
量を測る(情報量)→ 短くする(情報源符号化)→ デジタルにする(デジタル符号化)
覚え方の軸
- 情報量は「めずらしいほど大きい」:
- I=−log₂P。確率が1/2ⁿなら、ちょうどnビット
- 平均情報量(エントロピー)は「あいまいさ」:
- どれも同じ確率で起こるとき最大(k個ならlog₂k)。結果がわかりきっていれば0
- 圧縮の考え方は2つ:
- よく出るものを短い符号にする(ハフマン符号化)、同じものが続く部分をまとめる(ランレングス符号化)
- PCMは「標本化 → 量子化 → 符号化」:
- データ量=サンプリング周波数×量子化ビット数×秒数(÷8でバイト)
情報量:情報の大きさをビットで測る
- 情報には、情報の質(内容が妥当か、正当か)と情報の量(多いか少ないか)の両面がある。ここでは量の話
- 情報:
- 処理の対象は、すべて有限長のビット列に符号化される。この符号化されたデータに、何らかの意味(判断に必要な知識)を付けたものが「情報」
- 情報量 I(information content):
- ある事象Jが起こったときに伝わる情報の大きさ。単位はビット
- 情報量 I(J)= −log₂P(J)(P(J)は事象Jの生起確率、0≦P(J)≦1)
- 例:
- コインを投げて表が出る(確率1/2):
- −log₂(1/2)= −log₂2⁻¹ = 1ビット
- サイコロで1が出る(確率1/6):
- −log₂(1/6)= log₂6 ≒ 2.58 → 3ビット
- コインを投げて表が出る(確率1/2):
- 性質:
- 生起確率が大きい(よく起こる)ほど、情報量は小さい
- 生起確率が小さい(めずらしい)ほど、情報量は大きい
- 「何ビット必要か」の尺度としても使える
- 例:
- 3桁の数字(000〜999の1,000通り)を表すには、−log₂(1/1000)=log₂1000 ≒ 9.97 → 10ビット必要
- 簡単な見積もり方:
- 2⁹=512、2¹⁰=1024 なので、9<log₂1000<10。つまり「9.…」とわかる
- 例:
- 対数の重要公式(a>0、a≠1、M>0、N>0)
- logₐa=1、logₐ1=0
- logₐMᵏ=k×logₐM
- logₐM=log_bM ÷ log_ba(底の変換。bは何でもよい)
- logₐ(M/N)=logₐM−logₐN
- logₐMN=logₐM+logₐN
- 暗記:
- log₁₀2=0.301、log₂10=3.32
- 情報量の加法性:
- 互いに独立な事象JaとJbが同時に起こったときの情報量は、それぞれの情報量の和
- 例:
- 「コインで表が出る」と「サイコロで1が出る」が同時に起こる:1+2.58=3.58 → 4ビット
- 平均情報量 H(エントロピー):
- すべての事象(J₁〜Jₙ)の、情報量の平均
- H=Σ{P(Jₖ)×I(Jₖ)}(k=1〜n)
- 意味:
- あいまいさの程度。小さいほど予測しやすく、大きいほど予測しにくい
- 例:
- 当たり50%・はずれ50%:H=0.5×1+0.5×1=1ビット(2つの事象で最大。いちばん予測しにくい)
- 当たり70%・はずれ30%:H=0.7×(−log₂0.7)+0.3×(−log₂0.3)≒0.7×0.515+0.3×1.737≒0.88ビット(あいまいさが減る)
- 当たり100%:H=1.0×(−log₂1.0)=0ビット(あいまいさなし)
- 最大平均情報量:
- 事象がk個のとき、−log₂(1/k)=log₂k。k=2なら1
情報源符号化:データを短くする
- 通信路符号化:
- 情報を正しく伝えるための符号化(パリティチェック、CRC、ハミング符号など)
- 情報源符号化:
- 大きな情報を、できるだけ短く(小さく)するための符号化
- 情報源:
- 情報を記号の並び(一定の順序に従って並べた一連のもの)とみなしたとき、その記号を次々に発生させる源
- ハフマン符号化(★試験によく出る):
- 出現率の高い文字は短いビット列、低い文字は長いビット列で符号化し、1文字あたりの平均ビット長を最小にする圧縮方法
- 4文字(a〜d)なら1文字2ビットで区別できるが、出現率に差があれば平均2ビットより短くできる
- 例:
| 文字 | 符号 | 出現確率 |
|---|---|---|
| a | 0 | 40% |
| b | 10 | 30% |
| c | 110 | 20% |
| d | 111 | 10% |
- 1文字あたりの平均ビット数(期待値)=
- 1×0.4+2×0.3+3×0.2+3×0.1=1.9ビット(2ビット固定より短い。100文字で約190ビット)
- 期待値 E(X)=
- x₁p₁+x₂p₂+…+xₙpₙ = Σxᵢpᵢ(値×確率を全部足す。確率の合計は1)
- Σ記号:
- 和を表す。例えば Σ2k(k=1〜5)は「kを1から5まで1ずつ増やしながら2kを足す」
- 性質:
- Σ(a×k)=a×Σk、Σa=n×a(aは定数)
- ハフマン木の作り方(葉から根へ、ボトムアップに作る)
- 手順:
- ①文字を葉にして、出現確率を重みにした「葉だけの木」を作る
- ②重みの大きい順に並べる
- ③重みが最小の木を2つ選び、それを子にもつ木を作る(重みは2つの和)
- ④1つの木になるまで②③を繰り返す
- 符号の読み方:
- 根から目的の文字(葉)へ進み、左に進むと「0」、右に進むと「1」
- 例(上の表):
- d(10%)とc(20%)をまとめて30% → それとb(30%)をまとめて60% → それとa(40%)をまとめて100%。a=0、b=10、c=110、d=111
- 手順:
- ランレングス符号化:
- データの冗長さに注目し、同じ値が続く部分を「反復回数とデータ値の組」に置きかえて短くする圧縮方法
- 例(「続く個数から1を引いた数を1バイトで書き、その後に文字を置く」方式):
- PPPPPPPQRRRR(12バイト)→ 6P 0Q 3R(6バイト)。圧縮率50%
- Pが7個なので「6P」、Qが1個なので「0Q」、Rが4個なので「3R」
- 注意:
- 1個しかない文字も「0Q」の2バイトになるので、同じ文字があまり続かないデータでは、かえって長くなる
- この方式で圧縮率が最大になるのは、256個の同じ文字を2バイトにするとき
- 2値画像の圧縮にも使う。同じ色が続いた個数だけを記録する
- 例:
- 白0・黒1で「0000000011111000」→「8,5,3」
- 最初は白から始まるものとする。最初の画素が黒なら、先頭に「白が0個」あるとして符号化する
- 例:
デジタル符号化:アナログをデジタルに変える
- PCM(パルス符号変調、Pulse Code Modulation):
- アナログデータをデジタル符号に変える方式
- PCMの手順(★順番が大事)
- ①標本化(サンプリング):
- アナログ信号を一定の時間間隔で切り出す
- サンプリング周波数:
- 1秒間にサンプリングする回数
- サンプリング周期:
- サンプリングの時間間隔。サンプリング周波数の逆数
- ②量子化:
- 切り出したアナログ値をデジタル値(整数)に変える
- 量子化ビット数:
- 1回のサンプリングで作られるビット数。8ビットなら0〜255の値になる
- ③符号化:
- デジタル値を2進数のビット列にする(例:200→11001000、150→10010110)
- ①標本化(サンプリング):
- 1秒間に生成されるデータ量=
- サンプリング回数(=サンプリング周波数)× 量子化ビット数
- 例:
- サンプリング周波数8kHz、量子化ビット数8ビットで5秒間:
- (8×10³)×8×5 ÷ 8 = 40kバイト
- サンプリング周波数8kHz、量子化ビット数8ビットで5秒間:
- 例:
- 44.1kHz、16ビット、ステレオ(2チャネル)で1秒:
- 44.1×10³×16×2 ÷ 8 = 176.4kバイト
- 44.1kHz、16ビット、ステレオ(2チャネル)で1秒:
- 標本化定理:
- 元の信号に含まれる周波数成分が、サンプリング周波数の1/2未満なら、標本点の値だけで元の信号を完全に復元できる(逆にいえば、最高周波数の2倍より大きい周波数でサンプリングすればよい)
- PCMの改良方式
- DPCM(差分PCM):
- 直前の標本との差分を量子化して、データ量を減らす
- ADPCM(適応的差分PCM):
- DPCMをさらに改良し、差分を表すビット数を変動幅に応じて変える。主に音声用で、PCMの約1/4に圧縮できる
- DPCM(差分PCM):
混同しやすいペア
- 情報量(1つの事象の大きさ。−log₂P)/平均情報量(全事象の平均。あいまいさ)
- 通信路符号化(正しく伝える:パリティ、CRC、ハミング)/情報源符号化(短くする:ハフマン、ランレングス)
- ハフマン符号化(出現率で符号の長さを変える)/ランレングス符号化(連続部分を個数でまとめる)
- 標本化(時間で切る)/量子化(値をデジタルにする)/符号化(2進数にする)
- サンプリング周波数(1秒の回数)/サンプリング周期(間隔。周波数の逆数)
- DPCM(差分を量子化)/ADPCM(差分のビット数も変える)