5.1 變長碼與 Kraft 不等式#

導言：把熵變成演算法#

第 3 章證明了壓縮的理論極限：平均碼長 \(\bar{L} \ge H(X)\) 。但定理沒有告訴我們如何構造達到極限的碼。本章的任務是把存在性變成演算法。第一步是回答一個基礎問題：什麼樣的碼長組合是可實現的？ 答案是 Kraft 不等式——1949 年 Leon Kraft 在 MIT 學位論文中證明的結果，是信源編碼的基石。

變長碼的定義與三種品質#

設信源字母集 \(\mathcal{X} = \{x_1, \dots, x_M\}\) ，每個符號 \(x_i\) 對應碼字 \(c_i \in \{0,1\}^{l_i}\) ，碼長 \(l_i\) 。平均碼長：

好的變長碼需要滿足（依序加強）：

1. 非奇異（nonsingular）：不同符號對應不同碼字。
2. 唯一可解碼（uniquely decodable）：任何碼字串接序列只有一種切分方式（1.1 節 Morse 碼的問題）。
3. 即時可解碼（instantaneous，前綴碼）：任何碼字都不是其他碼字的前綴——讀完一個碼字立刻可解，無需看未來。

三者是嚴格的包含關係：

flowchart LR
    A[非奇異] --> B[唯一可解碼] --> C[前綴碼 即時可解]
    B -.->|同樣平均碼長可達| C

例題：四種碼的比較#

信源 \(\{x_1, x_2, x_3, x_4\}\) ，機率 \(\{1/2, 1/4, 1/8, 1/8\}\) ：

方案丙平均碼長 \(0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 = H(X)\) ——完美壓縮。方案乙看似更短（1.25）但不可解碼，無效。核心教訓：前綴約束不是奢侈品，是可行性的必要條件；下一小節的 Kraft 不等式把這件事變成代數。

Kraft 不等式#

定理#

存在即時可解碼的二元碼，碼長為 \(l_1, \dots, l_M\) ，若且唯若：

證明（必要性：樹的計數）#

前綴碼對應二叉樹的葉節點。長度 \(l_i\) 的葉佔據樹中 \(2^{L - l_i}\) 個深度 \(L\) 的節點（ \(L\) 取 \(\max l_i\) ，因前綴性使不同碼字的子樹互斥）。深度 \(L\) 的節點總數 \(2^L\) ，故

證明（充分性：貪婪構造）#

把碼長排序 \(l_1 \le l_2 \le \dots \le l_M\) 。按序在二叉樹上取「最左的可用深度 \(l_i\) 節點」。由 \(\sum 2^{-l_i} \le 1\) 可證每次都有可用節點（數學歸納：第 \(k\) 步已用掉的子樹權重 \(\sum_{i \le k} 2^{-l_i} \le 1 - 2^{-l_k}\) ，保證仍有多餘空間）。構造出來的碼自動是前綴碼。

Kraft 不等式的意義：它是前綴碼碼長的完整特徵——滿足不等式的任何碼長組合都存在對應前綴碼。因此，設計最佳前綴碼的問題，純粹是**在約束 \(\sum 2^{-l_i} \le 1\) 下最小化 \(\sum p_i l_i\) ** 的優化問題——這正是下一節 Huffman 演算法要解的。

推廣： \(D\) 元碼#

\(D\) 進位碼（ \(D\) 個符號）的 Kraft 不等式為 \(\sum_i D^{-l_i} \le 1\) ；證明把二叉樹換成 \(D\) 叉樹即可。三元、四元編碼（如光通訊的多階調變，8.3 節）都適用。

McMillan 不等式：唯一可解碼也一樣#

Kraft 不等式對前綴碼是「充要」，對唯一可解碼（較弱條件）是「必要」的——McMillan（1956）證明：**任何唯一可解碼碼的碼長也滿足 \(\sum 2^{-l_i} \le 1\) **。

深遠推論：唯一可解碼碼與前綴碼的碼長集合相同。由 4.3 節隨機編碼式的論證（碼長滿足 Kraft ⇒ 存在同碼長的前綴碼），可以推出：

任何唯一可解碼碼，都存在等碼長的前綴碼；因此前綴碼在平均碼長上沒有任何劣勢。

這就是為什麼工程上只用前綴碼：即時解碼的便利是免費的。

最佳碼長與熵的關係#

下界：碼長定理#

任何前綴碼（乃至唯一可解碼碼）滿足

證明（資訊不等式的優雅應用）：定義虛擬長度 \(l_i^* = -\log_2 p_i\) ，則 \(\sum p_i l_i^* = H(X)\) 。實際碼長 \(l_i\) 需滿足 Kraft。寫

其中 \(q_i = 2^{-l_i} / \sum_j 2^{-l_j}\) 。由相對熵非負（3.3 節）得 \(\bar L - H(X) \ge \log_2 \sum_j 2^{-l_j} \ge 0\) 。✓ 等號 iff \(p_i = 2^{-l_i}\) （機率是 2 的負冪）。

上界：整數碼長定理#

取 \(l_i = \lceil \log_2 (1/p_i) \rceil\) （向上取整），則 \(2^{-l_i} \le p_i\) ，故 \(\sum 2^{-l_i} \le \sum p_i = 1\) 滿足 Kraft——此碼長組合可實現，且

熵與可實作碼長之間的距離不超過 1 bit。這是 Shannon 編碼（shannon–fano coding）的直接構造法。

例題：構造 Shannon 碼#

信源 \(p = \{0.4, 0.3, 0.2, 0.1\}\) ， \(H \approx 1.846\) bits：

\(\bar L = 0.4(2) + 0.3(2) + 0.2(3) + 0.1(4) = 2.4 < H + 1 = 2.846\) 。✓ 但離熵有 0.55 bits 差距——Huffman（5.2 節）能做得更好（ \(\bar L = 2.0\) ）。

歷史前因後果#

誰、何時、為什麼#

• 1948 Shannon：證明碼長定理（下界 \(H\) 與上界 \(H + 1\) ），以 Shannon–Fano 編碼實作。
• 1949 Kraft：MIT 碩士論文中證明 Kraft 不等式（前綴碼版）。
• 1949 Fano：獨立提出類似不等式（因此有時稱 Kraft–McMillan 或 Kraft–Fano）。
• 1956 McMillan：證明唯一可解碼碼也滿足同不等式，確認前綴碼無損失。

解決了什麼問題#

1. 可行性判準：給定想要的碼長，能否實現？一條不等式說了算。
2. 壓縮極限的落地：熵 \(H\) 不再只是抽象極限，而是與可實作碼長相差不到 1 bit 的具體目標。
3. 優化問題的成型：把「設計好碼」化為帶 Kraft 約束的線性優化，為 Huffman 演算法鋪路。

引發什麼新問題#

1. 機率非 2 的負冪時怎麼辦：整數碼長造成最多 1 bit 浪費——算術編碼（5.3 節）用小數碼長解決。
2. 符號相依：英文的條件熵遠低於單符號熵（3.2 節），需要上下文模型——通用壓縮（5.3 節）。
3. 多符號編碼：一次編 \(n\) 個符號可使 \(\bar L/n \to H\) （塊狀編碼），但碼表指數膨脹——又是算術編碼的動機。

與其他領域的關聯#

樹與圖論#

前綴碼 = 根樹的葉集合；Kraft 不等式 = 樹的質量守恆；Huffman 樹（5.2 節）是最優搜尋樹理論（Hu–Tucker）的親戚。因子圖（9.2 節）的訊息傳遞也建立在樹的精確性上。

機率與資訊不等式#

碼長定理的證明用相對熵（3.3 節）——「碼長問題 = 分佈匹配問題」的觀點貫穿率失真理論（8.2 節）：量化器設計 = 讓重建分佈匹配源分佈。

組合學#

Kraft 不等式可視為二叉樹葉數目的組合約束，與卡特蘭數、樹計數等組合結構相連； \(D\) 元推廣對應多叉樹。

小結與思考題#

Kraft 不等式 \(\sum 2^{-l_i} \le 1\) 完整刻劃可實現碼長；它連接了前綴碼（樹）、唯一可解碼碼（McMillan）與熵（碼長定理），並把壓縮設計化為優化問題。

思考題

1. 碼長 \(\{1, 2, 3, 3\}\) 滿足 Kraft 嗎？畫出對應的樹。（ \(\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1\) ，恰好滿足——「完全樹」。）
2. 碼長 \(\{2, 2, 2, 2, 2\}\) 呢？（ \(5 \times 2^{-2} = 1.25 > 1\) ，不可行。）
3. 信源 \(p = \{0.35, 0.25, 0.2, 0.1, 0.1\}\) ：構造 Shannon 碼，計算 \(\bar L\) 與 \(H\) ，兩者差距多少？
4. 證明：若 \(\sum 2^{-l_i} = 1\) （等號），碼樹必為完全樹（無空閒葉），此時任何加碼（新增符號）都必須重排。
5. 為什麼「唯一可解碼碼總可換成等碼長前綴碼」對工程重要？（提示：解碼延遲與緩衝需求。）

下一節：Huffman 演算法——把優化問題一次解到最好。

深入探討：碼的結構分析與組合練習#

一、Kraft 不等式的 D 元版與完全樹的細節#

D 元推廣： \(D\) 進位前綴碼的可行性：

完全樹（等號成立）的兩個特殊性質：

1. 無浪費：每個內部節點恰有 \(D\) 個子節點被使用。若等號不成立，存在「空閒」碼位可縮短某碼字或容納新符號。
2. 碼長閉包： \(D\) 元完全樹中， \(\sum D^{-l_i} = 1\) 且碼長集合對「分裂一個葉為 \(D\) 個深 1 層的葉」封閉——這是 Huffman 演算法（5.2 節）反覆執行的操作。

例題（三元碼）：碼長 \(\{1, 1, 2, 2, 2\}\) 在三元（ \(D=3\) ）下可行嗎？

完全樹存在：根的兩個子是長 1 葉，第三子再分三個長 2 葉。若機率分佈適合（如 \(\{0.4, 0.35, 0.1, 0.08, 0.07\}\) ），三元碼可優於二元（每符號位元更少，但物理通道需 3 態——8.3 節多階調變的理論介面）。

二、唯一可解碼碼的識別演算法：Sardinas–Patterson#

5.1 節說「唯一可解碼」是碼的重要屬性，但如何判斷一個碼是否唯一可解？Sardinas–Patterson 演算法（1953）：

1. 構造集合 \(S_1\) = 所有「碼字對的前後綴差」：若 \(c_i = c_j t\) （ \(c_j\) 是 \(c_i\) 的前綴），把剩餘 \(t\) 放入 \(S_1\) 。
2. 迭代： \(S_{k+1}\) = 碼字與 \(S_k\) 的前後綴差集。
3. 判準：若空字串出現在某 \(S_k\) ，碼非唯一可解；若所有 \(S_k\) 收斂且不含空串，碼唯一可解。

例題：碼 \(\{a: 0, b: 01, c: 011\}\) （5.1 節方案乙）：

• \(S_1\) ： \(0\) 是 \(01\) 、 \(011\) 的前綴 → \(S_1 = \{1, 11\}\) 。
• \(S_2\) ： \(1\) 與碼字無前後綴關係； \(11\) ？碼字 \(011\) 後接 \(1\) → \(S_2\) 含 \(\{\}\) ？

逐步：碼字 \(01\) + \(S_1\) 中 \(1\) 剩 \(\{\}\) ——空串出現，非唯一可解？實際上 \(\{0, 01, 011\}\) ：訊息 \(011\) 可切 \(0|11\) ？ \(11\) 不是碼字。 \(01|1\) ？ \(1\) 不是碼字。真正切法只有 \(011\) 。再驗： \(0|01\) = \(001\) 、 \(01|0\) ……需要完整演算，這正是練習的價值。Sardinas–Patterson 是 O(碼長) 的有限檢驗，工程上（自訂碼表的系統）用它驗證碼表合法性。

三、碼長定理的推廣：塊碼與漸近#

塊狀編碼定理：對 \(n\) 個 i.i.d. 符號做整體編碼：

每符號攤薄：

讀法： \(n = 10\) 時差距 < 0.1 bits； \(n = 100\) 時 < 0.01。但碼表大小 \(2^{\lceil nR \rceil}\) 指數爆炸（ \(n = 100\) 、 \(H = 4\) ：碼表 \(2^{400}\) 條目）。這個「塊狀碼近極限但不可實作」的矛盾是 5.3 節算術編碼的誕生理由：算術編碼等效於無限塊長的編碼，碼表卻是 \(O(1)\) 。

四、Shannon 碼的完整構造與效能對照#

5.1 節給了構造法，這裡做完整演算與三碼對照。信源 \(p = \{0.3, 0.25, 0.2, 0.15, 0.1\}\) ， \(H = 2.228\) bits。

Shannon 碼（碼長 \(l_i = \lceil \log_2 1/p_i \rceil\) ）：

\(\sum 2^{-l_i} = 0.8125 \le 1\) ✓（有餘量，非完全樹——Huffman 可再壓）。 \(\bar L_{\text{Shannon}} = 0.3(2)+0.25(2)+0.2(3)+0.15(3)+0.1(4) = 2.55\) 。

對照：Huffman（5.2 節演算法可驗） \(\bar L = 2.30\) ；熵 2.228。排名：Huffman(2.30) < Shannon(2.55) < 定長(3)。Shannon 碼浪費 0.32 bits/symbol，全因「向上取整」——每個符號平均浪費 0.5 bit 以內，但累積可觀。這是 5.2、5.3 節改進的起點。

五、碼長分配的對偶視角：機率匹配#

5.1 節碼長定理的證明隱藏了一個深刻觀點，值得獨立陳述：

理想碼長 \(l_i^* = -\log_2 p_i\) 使 \(\sum 2^{-l_i^*} = \sum p_i = 1\) （Kraft 恰好等號）。換句話：把「機率分佈」直接當作「碼長分佈」—— \(p_i\) 與 \(2^{-l_i}\) 是同一件事的兩種讀法。

這個對偶在多處復現：

• 算術編碼（5.3）：直接用 \(p_i\) 劃分區間，等效於小數碼長。
• 通道編碼的假設檢驗：碼字被選中的機率 vs 碼字之間的距離，是對偶的資源分配（4.3 節隨機編碼的均勻碼本 = 假設碼距盡量均勻）。
• 最大熵原理（3.1）：給定碼長（約束），最優機率 = \(2^{-l_i}\) 歸一化——熵最大的分佈就是「與碼長匹配」的分佈。

六、實務細節：碼表的傳輸與邊界情況#

設計前綴碼系統時的三個工程問題（5.2 節會遇到同類問題）：

1. 碼表開銷：解碼端需知道 \(l_i\) （或碼樹）。開銷 \(= \sum (\text{碼長描述位元})\) ，常用約 \(M \lceil \log_2 \max l_i \rceil\) 。短訊息時碼表開銷可能吃掉壓縮收益——短資料不壓縮是常見的合理決策（DEFLATE 對小檔案的處理）。
2. 零機率符號：分佈中 \(p_i = 0\) 的符號不應佔碼位（Huffman 演算法需先剔除），但系統需處理「突然出現未知符號」的 fallback（逃生碼字）。
3. 單符號信源： \(M = 1\) 時熵為 0，任何碼長 ≥ 1 都「浪費」——塊狀編碼或 escape 機制處理。

七、補充思考題#

1. 對第四節的 \(p\) ，用 Sardinas–Patterson 驗證 Shannon 碼表的前綴性（直接觀察即可，但要寫出為什麼構造法保證前綴）。
2. 求最小的 \(n\) 使塊狀碼的每符號差距 < 0.05 bits（對 \(H = 2.228\) 的信源）。
3. 證明：Kraft 和為 \(K < 1\) 時，必存在一個碼字可縮短 1 位元而不破壞前綴性（由此證明最優前綴碼必為完全樹——5.2 節引理二的預演）。
4. 三元碼 \(\{0, 1, 2\}\) 、信源 \(p = \{0.4, 0.3, 0.15, 0.1, 0.05\}\) ：構造 Shannon 三元碼，與二元 Shannon 碼的每符號位元數比較（記得換算成同單位）。