情報理論と符号化

このページでは、情報量と平均情報量(エントロピー)の計算、ハフマン符号化とランレングス符号化による圧縮、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ビット
  • 性質:
    • 生起確率が大きい(よく起こる)ほど、情報量は小さい
    • 生起確率が小さい(めずらしい)ほど、情報量は大きい
  • 「何ビット必要か」の尺度としても使える
    • 例:
      • 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バイト
  • 例:
    • 44.1kHz、16ビット、ステレオ(2チャネル)で1秒:
      • 44.1×10³×16×2 ÷ 8 = 176.4kバイト
  • 標本化定理:
    • 元の信号に含まれる周波数成分が、サンプリング周波数の1/2未満なら、標本点の値だけで元の信号を完全に復元できる(逆にいえば、最高周波数の2倍より大きい周波数でサンプリングすればよい)
  • PCMの改良方式
    • DPCM(差分PCM):
      • 直前の標本との差分を量子化して、データ量を減らす
    • ADPCM(適応的差分PCM):
      • DPCMをさらに改良し、差分を表すビット数を変動幅に応じて変える。主に音声用で、PCMの約1/4に圧縮できる

混同しやすいペア

  • 情報量(1つの事象の大きさ。−log₂P)/平均情報量(全事象の平均。あいまいさ)
  • 通信路符号化(正しく伝える:パリティ、CRC、ハミング)/情報源符号化(短くする:ハフマン、ランレングス)
  • ハフマン符号化(出現率で符号の長さを変える)/ランレングス符号化(連続部分を個数でまとめる)
  • 標本化(時間で切る)/量子化(値をデジタルにする)/符号化(2進数にする)
  • サンプリング周波数(1秒の回数)/サンプリング周期(間隔。周波数の逆数)
  • DPCM(差分を量子化)/ADPCM(差分のビット数も変える)

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました