ソース→チャネル: 2段階符号化
Hammingの第10章はシャノンの通信モデルで始まります。これはすべての情報を移動させるシステムに適用されます: 電話、ラジオ、ハードドライブ、DNA複製、コンピュータメモリ。
2段階アーキテクチャ
ステージ1: ソース符号化（圧縮）。ソースメッセージをコンパクトな表現に変換します。目標: ソース固有の冗長性を除去します。モースコードはこれを行います: よくある文字は短いコードを、珍しい文字は長いコードを取得します。
ステージ2: チャネル符号化（エラー保護）。チャネルのノイズ特性に適応した制御された冗長性を追加します。ノイズの多い電話線は光ファイバーケーブルより多くの冗長性が必要です。2つのステージは独立します: 各々のタスクに対して独立して最適化します。
2つのステージ間の共通インターフェース — 標準化されたビットストリーム — は、任意のソースが任意のチャネルと組み合わせることができることを意味します。このモジュール性はシャノンの重要な建築学的洞察です。
ストレージとしての通信。 Hammingは、メッセージを空間を通じて送信すること（伝送）と時間を通じて送信すること（ストレージ）が同じモデルを使用していることに注目します。バックアップドライブは時間内のノイズの多いチャネルです。
ノイズの役割
シャノンのモデルは根本的な仮定をします: ノイズは避けられません。すべてのチャネル、すべてのストレージメディア、すべてのスイッチング回路はエラーの確率を導入します。質問は「ノイズをどのように排除するか？」ではなく、「ノイズにもかかわらず元のメッセージをどのように復元するか？」です。
これは古典物理学と対比されます。そこではノイズは後付けとして入ります（不確定性原理）。シャノンはノイズを基本的な条件として扱います — すべての理論がそれから構築されます。
現在のところ、第10章は無ノイズケースに焦点を当てます: エラーのないソース符号化。チャネル符号化問題（エラー訂正）は後の章を待ちます。
どのような時に一意にデコードできるか？
可変長符号が有用であるためには、受信者はビットストリームを明確にデコードできる必要があります。Hammingはこのテストに失敗する4シンボル符号を説明し、その後、修正を導入します: プレフィックスフリー符号。
プレフィックスフリー条件
符号はプレフィックスフリー（または瞬間的）です。コードワードが他のコードワードのプレフィックスでない場合。受信されたビットストリームが与えられると、デコード木のリーフに到達したら、シンボルが終わったことがわかります — 先読みは必要ありません。
例: {s1, s2, s3, s4}のプレフィックスフリー符号: s1 = 0、s2 = 10、s3 = 110、s4 = 111。
確認: 0は10、110、または111のプレフィックスではありません。10は110または111のプレフィックスではありません（10の後にさらなるビットが続くと100...または101...になり、どちらも110または111で始まりません）。符号は適格です。
デコード手順: 木を辿り、各受信ビットで分岐し、リーフに到達したらシンボルを出力し、ルートに戻ります。
Kraft不等式
コードワード長がl_1、l_2、...、l_nのプレフィックスフリーバイナリ符号の場合:
Σ 2^(−l_i) ≤ 1
等式は符号が完全な場合に成立します（リーフはギャップのない完全なバイナリ木をタイル張ります）。これは必要条件です: プレフィックスフリー符号がそれを違反することはできません。逆に、Kraft不等式を満たす長さのセットについて、プレフィックスフリー符号が存在します。
Kraft不等式の適用
コードワード長が与えられたら、Kraftを確認します: Σ 2^(−l_i) ≤ 1。
{s1=0、s2=10、s3=110、s4=111}の場合: 長さは1、2、3、3です。
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1。 ✓
シャノンエントロピー
可変長符号の平均コード長: L = Σ p_i · l_i。ここで、p_iはシンボルs_iの確率、l_iはそのコード長です。
Lはどの程度短くすることができますか？シャノンの答え: ソースエントロピー以下ではありません。
シャノンエントロピー: H = −Σ p_i · log₂(p_i) （単位: ビット/シンボル）
エントロピーはシンボルあたりの平均情報を測定します。高いエントロピーはシンボルがほぼ等確率であることを意味します（最大の不確実性）。低いエントロピーはいくつかのシンボルが支配的であることを意味します（高い予測可能性、より圧縮可能）。
無ノイズ符号化定理
プレフィックスフリー符号の場合、H(ソース) ≤ L ≤ H(ソース) + 1。
コードはエントロピーに勝つことはできません。Huffman符号化（次の章）は上限を達成します: L < H + 1。nシンボルのブロック符号の場合、境界は厳しくなります: H ≤ L/n < H + 1/n。
エントロピーはまた理論的圧縮限界です: 情報を失わずにソースをHビット/シンボル以下に圧縮することはできません。
エントロピーの計算
例: 確率p = [1/2、1/4、1/8、1/8]の4つのシンボル。
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75ビット/シンボル
そして、Huffman符号{0、10、110、111}はL = 1.75 = Hを正確に達成します。
エントロピーが下限である理由
無ノイズ符号化定理の下限は単なる公式ではありません — それは情報について何か深いことを反映しています: すでに最大限に予測不可能なものを圧縮することはできません。
すべてのシンボルが等確率の場合（均一分布）、nシンボルのエントロピーH = log₂(n)です。log₂(n)ビットのブロック符号はちょうどHを達成します。コードはそれ以上に良くすることはできません。
1つのシンボルが支配的な場合（たとえば、p(A) = 0.99、p(B) = 0.01）、Hは小さい — 0に近い。可変長符号は非常に短いコードをAに割り当てることができ、ストリームを非常に効率的にエンコードします。
実用的な結論: 大きな圧縮ゲインは、シンボル確率が大幅に異なる場合にのみ存在します。ソースがすでに「均一」（ランダムに見える）場合、Huffman符号化ゲインはありません。