← 情報理論 一覧

🎓 第3章：情報源符号化

第3章 情報源符号化

「どこまで圧縮できるか」に答える章です。第1章のエントロピー・AEP（漸近等分割性とAEP）が、ここで 平均符号長の理論限界 として具体化します。一意に復号できる符号は Kraft 不等式を満たし、その最小の平均長がエントロピー——これがシャノンの情報源符号化定理。実際に最適符号を作るハフマン法、整数長の無駄を消す算術符号、確率を知らなくても圧縮できるユニバーサル符号（gzip の理論）まで、実装して動かしながら確かめます。

トピック一覧

1. 無歪み符号化とKraft不等式 — 標準
2. シャノンの情報源符号化定理 — 発展
3. ハフマン符号 — 標準
4. 算術符号とユニバーサル符号 — 発展

この章の要点

• Kraft 不等式 $\sum_i 2^{-l_i}\le 1$：一意復号可能な符号の符号長が満たす必要十分条件。シャノン符号長 $l_i=\lceil-\log_2 p_i\rceil$ は常に満たす。
• 情報源符号化定理：一意復号可能な符号の平均長 $L$ は $L\ge H$。ブロック化で $L/k\to H$ に収束（実証済み）。
• ハフマン符号：与えられた確率に対する最適接頭符号。$H\le L_{\text{Huffman}}< H+1$。
• 算術符号・ユニバーサル符号：系列全体を1つの数に符号化し整数丸めの無駄を償却。LZ は確率未知でも漸近最適。

関連章

• 第1章 情報量とエントロピー — AEP が圧縮限界の正体
• 第6章 連続情報量とレート歪み — 歪みを許す圧縮（非可逆）
• セキュリティ：暗号の実務／ネットワーク：実際の通信

上位ハブ

• 情報理論 全体目次