情報理論は AP 科目Aで 1〜2 問、科目B問5 (NW) でも符号化の知識が問われます。情報量・エントロピー・ハフマン符号・誤り訂正の4本柱を押さえましょう。
鳴海 理央
情報量 は『その事象がどれくらい意外か』を表す量で、−log₂ p(x) ビットで計算します。
確率が低い事象ほど情報量が大きい、という直感です。
砂原 ニコ
うっ、log…苦手だぁ…
緒方 ナオミ 先生
log₂ は『2を何乗するとその数になるか』ということね。
log₂ 8 = 3、log₂ 16 = 4。
これだけ押さえれば AP は十分解けるわよ。
藤咲 まりあ
エントロピー って何ですかぁ?
ファイル圧縮のときに聞いたような気がするんですけどぉ…
鳴海 理央
情報源の平均情報量です。
Σ −p(x) log₂ p(x) で計算。
圧縮の理論的下限を示す重要量で、ハフマン符号 のような可変長符号化はエントロピーに迫る圧縮を実現します。
緒方 ナオミ 先生
ハフマン符号は、出現頻度の高い文字に短いビット列を割り当てる方式。
誤り検出符号 と並んで AP 頻出よ。
砂原 ニコ
誤り訂正って、要はデータが化けても直せるってこと?
鳴海 理央
はい。
ハミング距離 という『2つのビット列で異なるビット数』が大きいほど、訂正能力が高くなります。
確認クイズ
ある情報源が4種類の記号を等確率で出す。1記号あたりの平均情報量 (エントロピー) は何ビットか。
- 1ビット
- 2ビット
- 3ビット
- 4ビット
こたえを見る
正解: 2. 2ビット
等確率の場合エントロピーは log₂ N。N=4 なら log₂ 4 = 2 ビット。各記号を 00/01/10/11 の 2ビットで表せばちょうど無駄なく符号化できる、という直感とも一致します。