1.2情報理論と符号化

通信やストレージの世界では「データをできるだけ小さく」「データをできるだけ正確に」という2つの相反する要求を同時に満たす必要があります。前者に応えるのが符号化・圧縮、後者に応えるのが誤り検出・訂正の技術です。この節ではその理論的な出発点である情報量の考え方から、実務で使われる具体的な符号化方式まで一気通貫で学びます。

1.2.1情報量とエントロピー

• 情報量＝ある事象の発生確率pから log2(1/p) ビットで求まる「意外性の度合い」。発生確率が低い事象ほど情報量は大きい。
• エントロピー＝情報源が出しうる全事象の情報量を発生確率で重み付けして平均した値（H = Σ p_i・log2(1/p_i)）。情報源全体の不確実性・平均情報量を表し、この値が符号化における理論的な最短平均符号長の下限になる。

1.2.2ハフマン符号化とデータ圧縮

• ハフマン符号化＝出現頻度が高い記号に短い符号、低い記号に長い符号を割り当てることで平均符号長を最小化する可変長符号化の代表手法。「短い符号が他の符号の先頭部分と一致しない」（接頭語性、prefix-free）性質により、復号時に区切りが一意に定まる。
• 構成手順＝出現頻度が最小の2つのノードを繰り返し統合して2分木（ハフマン木）を作り、根からの経路（左0/右1）が各記号の符号になる。頻度の偏りが大きいデータほど圧縮率が高い。

1.2.3誤り検出・訂正（パリティ・CRC・ハミング符号）

• パリティビット＝データ中の1の個数を偶数（または奇数）に揃える1ビットの検査符号。単一ビット誤りは検出できるが、誤り箇所の特定や2ビット同時誤りの検出はできない（偶数個のビット誤りは見逃す）。
• CRC（巡回冗長検査）＝データを多項式とみなし、生成多項式で割った余りを検査符号として付加する方式。パリティよりバースト誤り（連続した複数ビットの誤り）の検出能力が高く、ネットワーク通信やストレージで広く使われる。
• ハミング符号＝検査ビットを複数配置し、誤り検出だけでなく誤り箇所の特定・自動訂正（1ビット誤り訂正）まで行える符号。ECCメモリなど、誤り訂正が必須の場面で使われる。

ある通信システムで4種類の記号A・B・C・Dが、それぞれ発生確率 A=0.5, B=0.25, C=0.125, D=0.125 で送信されるとします。まずエントロピーを計算すると H = 0.5×log2(2) + 0.25×log2(4) + 0.125×log2(8) + 0.125×log2(8) = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 0.5+0.5+0.375+0.375 = 1.75 ビット/記号となり、これが理論上の最短平均符号長です。ここでハフマン符号化を適用すると、最小頻度のCとD（各0.125）をまず統合して0.25のノードを作り、次にこれとB（0.25）を統合して0.5のノードを作り、最後にA（0.5）と統合して木が完成します。この木から A=0（1ビット）、B=10（2ビット）、C=110（3ビット）、D=111（3ビット） という符号が得られ、平均符号長は 0.5×1+0.25×2+0.125×3+0.125×3=1.75 ビットとなり、エントロピーの理論下限と完全に一致します（この例は頻度が2の冪乗比になっているため理論値と一致する特殊ケース）。次に伝送誤りへの対策を考えます。単純な誤り検出だけで十分なファイル転送ではCRC（バースト誤りに強い）を、誤り訂正まで必須のメモリシステムではハミング符号（1ビット誤りを自動訂正）を選ぶ、というように検出のみで足りるか・訂正まで必要かで符号化方式を使い分けるのが実務判断です。

1.2.4文字コード

• 文字コード＝文字とビット列を対応付ける規則。Unicodeは世界中の文字を単一の文字集合で扱う標準規格で、その符号化方式の一つUTF-8はASCII文字を1バイトで表現しつつ多バイト文字にも対応できる可変長エンコーディングとして広く普及している。

1.2.5この節のまとめ

• 情報量＝log2(1/p)、エントロピー＝情報量の確率加重平均（理論上の最短平均符号長）
• ハフマン符号化＝頻度が高いほど短い符号（可変長・接頭語性）を割り当てて平均符号長を最小化
• パリティ＝検出のみ、CRC＝バースト誤りに強い検出、ハミング符号＝検出＋自動訂正と使い分ける