動機
信源產生某些符號的頻率可能遠高於其他符號。為常見符號使用較短描述可以降低平均長度,但接收者仍須知道每個描述在哪裏結束。前綴碼保證明確的邊界。在這裏討論的有限情形中,熵與單個符號的最優平均長度之差小於一位元。
定義
定義 3.1.1
(二元熵)
設信源產生 個符號之一,概率為 且 。概率為零的符號可從有限列表中省略。其二元熵為
定義 3.1.2
(前綴碼)
二元碼給每個符號分配不同的有限二進制字。第 個字的長度為 ,平均長度為 。若任何碼字都不是另一個不同碼字的前綴,稱碼為前綴碼。只在碼中只有一個字時容許空字。非空字的前綴碼可從左到右解碼:一旦識別出碼字就停止,前綴條件保證它不會只是更長碼字的開頭。若唯一的碼字為空字,接收者必須另行知道傳送了多少個符號。
定理/命題
定理 3.1.3
(Kraft 不等式)
有限二元前綴碼的長度滿足 。反之,任何滿足此不等式的有限個非負整數長度都能由某個二元前綴碼實現。
定理 3.1.4
(熵與平均長度)
任何有限二元前綴碼的平均長度 滿足 。並且存在前綴碼滿足 。
證明思路
證明
(Kraft 不等式的二進區間證明)
長度為 的二元字對應 中長度為 的二進區間:它的位元確定 等分區間之一。若有限碼是前綴碼,這些區間兩兩不交,長度之和至多為一,得到必要不等式。
反過來,將給定長度按非遞減次序排列。從零開始依次放置長度為 的區間。放置第 個區間之前,前面長度的總和是 的整數倍,因為此前的區間都對應更粗或相同的二進劃分。因此新區間本身是要求深度的二進區間。Kraft 不等式保證所有區間都在 中。它們的二元標記構成前綴碼:一個二進區間包含另一個,當且僅當其標記是後者標記的前綴。空字對應整個區間,所以只能是唯一的碼字。
證明
(散度與向上取整的長度)
為證明熵下界,先使用 時的 。對 求導可知它在 取得最小值。若 是等長的正概率向量,則
證明:對 應用不等式,乘以 並求和,得到 。
對前綴碼長度令 、。則 是正概率向量,且
為證明上界,取 。於是 ,Kraft 不等式保證存在這些長度的前綴碼。又因 ,乘以 求和即得 。下界也適用於該碼。這是單符號結論,不聲稱每個碼都達到熵,也不聲稱某個具體信源模型已得到驗證。
證明透視
前綴條件貢獻了甚麼
下界只透過 Kraft 不等式 用到前綴條件;此後論證只涉及兩個概率向量。不明顯的一步是把二進權重歸一化為 ,使散度不等式可以應用。歸一化的代價恰為 ,由於 它非負;每個 都為正,則保證每個對數有限。
上界的方向相反。向上取整的長度 滿足 ,所以其 Kraft 和至多為 ,而產生碼的是 Kraft 定理的逆向部分;嚴格不等式來自 。若沒有前綴條件, 可以超過一, 變為負數,這正是常見錯誤中的反例逃出該界的方式。
為甚麼均勻分佈的熵最大
定理 3.1.5
(均勻分佈使熵最大)
對 個正概率,。上界恰由均勻分佈達到。
證明
(與均勻分佈比較)
對 個正概率,將 與均勻分佈 比較。散度不等式給出
因此 。下界是因為 ,每項 非負。上界恰在均勻分佈時取等號: 只有在 時取等號,所以每個 都必須為一。若 ,唯一概率為一,熵為零。
分塊編碼與獨立性的作用
定理 3.1.6
(分塊編碼趨近熵)
若 個信源符號獨立同分佈,分佈為 ,則長度為 的塊的熵為 ,並且存在塊的前綴碼,其平均長度 滿足 。
證明
(塊熵與每符號碼率)
假設 個信源符號獨立同分佈,各符號概率為 。把每個長度為 的序列看成擴充字母表中的一個符號,它的概率是各座標概率的乘積。塊熵為
最後一個等式可將對數展開成 項;每一項對其他座標的概率求和均為一,留下 。乘積公式依賴獨立性。如果重複符號完全相關,塊熵可以遠小於 。
對有限塊字母表應用前述構造,其平均碼長 滿足
因此每個原始符號的平均位元數隨塊長增長而趨近熵。這是對每個有限塊長的碼的存在性結論,不是計算成本、記憶體、延遲或模型錯誤時性能的界。所有概率均為正時,塊字母表有 個可能序列,直接查表可能增長很快。
前綴碼作為樹
概念視角組合
以數葉子理解 Kraft 不等式
有限二元前綴碼可畫成有根二叉樹:從根開始,0 走左邊,1 走右邊。碼字標記選定節點,前綴性說明任何選定節點都不是另一個的祖先。刪去未使用的後代後,可把碼字視為葉。取深度 ,長度為 的碼字有 個後代。這些後代集合互不相交,且均在深度 的 個節點中。兩邊除以 便再次得到 Kraft 不等式。
樹的圖像還說明 的情形:深度 的一些葉沒有使用。並非每個內部節點都需要兩個被使用的子節點。添加未使用的字以補全樹會改變訊息字母表,編碼原有符號並不需要這樣做。
等號與約定
定理 3.1.7
(熵界的等號情形)
單符號前綴碼滿足 ,當且僅當對每個符號都有 。
證明
(兩項鬆弛都必須為零)
下界證明把可能的差距分成兩部分:
右邊兩項都非負,所以取等號必須有 且 。由 的等號條件,後者意味著所有 。合起來得到每個符號的 。反過來,若每個概率都等於其碼長對應的二進權重,直接代入即得 。因此逐個編碼信源符號的前綴碼達到下界,當且僅當概率與一個填滿容量的前綴長度列表的二進權重一致。
只有一個符號時,本節容許長度零的空字,得到 、。某些通訊情境要求至少一位元或另加終止標記;那是附加編碼約束,可改變容許的碼和最優平均長度。數學上的零長度不意味著真實協議無需訊框定界,也不意味著接收者無需知道傳送符號的數量。
對於非空碼字的前綴碼,從左到右讀到一個碼字就能確定其終點,再讀下一個,因而可唯一解碼。若唯一的碼字為空字,則需要另行知道字數才能確定序列,因為沒有位元標記其重複次數。這裏的熵和 Kraft 結論不需要證明針對所有唯一可解碼的更一般定理。非前綴碼仍可能以更複雜方式唯一解碼,所以僅憑它不是前綴碼,不能證明每種拼接都有歧義。
本模型只計算碼字的位元數,不計算傳送不斷變化的字典、同步分塊或偵測傳輸錯誤的成本。
例題詳解
例題 3.1.8
(概率不相等)
概率為 時,前綴字 的長度為 ,平均長度為 。熵同樣是 。這裏每個字長都等於 ,因此達到下界。
例題 3.1.9
(資訊量不是整數)
三個符號等概率時,。碼 的平均長度為 。每個字的長度必須是整數,不能分別賦予 位元,儘管平均長度可以不是整數。這與上下兩個界都一致:。
例題 3.1.10
(不可能的長度列表)
三個長度均為一的二元碼字的 Kraft 和為 ,故不存在這樣的前綴碼;事實上長度一的二元字只有兩個。定理的反方向說明,當 Kraft 和至多為一時,可以構造具有指定整數長度的前綴碼。
例題 3.1.11
(有偏的二元信源)
兩個符號的概率為 時,熵為
它小於公平二元信源的一位元。對兩個單獨符號的前綴碼,每個碼字仍至少需要一位元:碼有兩個字時任何一個都不能是空字。所以單符號碼 的平均長度是 1,而非 。整數碼長未必能達到熵下界。
例題 3.1.12
(獨立與完全相關的位元對)
兩個獨立公平位元有四個等概率的兩位塊。分別使用 作為碼字,平均塊長度為 2,每個原始符號平均 1 位元,等於單符號熵。若兩位完全相關,只可能出現各佔一半的 ,其塊熵為 1 而非 2。邊緣概率不能單獨決定聯合熵。
常見錯誤
常見錯誤
(互不相同的碼字不一定是前綴碼)
平均長度小不保證即時解碼。字 和 雖然不同,卻不是前綴碼:讀到第一個零時不能立即知道它是完整碼字還是第二個碼字的開頭。前綴性是即時解碼的充分條件;這裏的熵定理針對前綴碼,並未對任意不同字列表作斷言。
去掉前綴條件不只是使解碼變得複雜;它甚至可以破壞熵界本身。
反例模式
只要求碼字互不相同並不保證熵界
斷言:每個給符號分配互不相同的二元字的碼都滿足 。對 使用互不相同的字 。則
該碼不是前綴碼,因為 是 的前綴,其 Kraft 和為 。它也不能解碼:字串 可以是一個第三符號,也可以是兩個第一符號。修正後的命題就是上面證明的定理:前綴碼滿足 。
常見錯誤
(界 只針對平均長度)
熵依賴概率,而不只依賴可能符號數。 是構造所得碼的平均長度上界,不是每個碼字長度的上界。概率必須構成分佈;這裏省略 的項以避免寫 ,需要時也可使用通常的極限約定。
總結
Kraft 不等式把前綴條件轉化為二叉樹的容量限制,並刻畫哪些有限長度列表可以實現。熵下界來自散度非負;把資訊量向上取整,可構造平均長度比熵多不到一位元的碼。
練習
快速檢查
(二元前綴碼能否有長度 ?)
計算 Kraft 和。
解答 · 答案
不能,Kraft 和為 。
快速檢查
(兩個等概率符號的熵是多少?給出最優前綴碼。)
以 應用均勻分佈使熵最大的定理。
解答 · 答案
熵為 1 位元。碼字 長度均為 1,平均為 1,達到熵下界。
快速檢查
(某前綴碼長度為 。求 Kraft 和並構造一個這樣的碼。)
先放兩個短字,再把一個未用的長度二的字分拆。
解答 · 答案
和為 。例如 ,其中沒有一個字是另一個的前綴。未使用容量不會妨礙解碼。
快速檢查
(信源把同一個公平位元重複兩次,因此兩位塊只可能是各佔一半的 。求塊熵,並與兩個邊緣熵之和比較。)
數一數實際會出現的結果。
解答
塊有兩個等概率結果,熵為 1 位元。每一位單獨的熵都是 1,但兩位相關,兩個邊緣熵之和為 2。獨立符號的乘積分佈證明不能應用。
快速檢查
(長度為 的二元前綴碼,按此順序對應概率 時,能否恰好達到熵?)
計算 並與 比較。
解答
平均長度為 ,而信源熵為 ,因此沒有達到下界。其 Kraft 和為 ,也顯示樹容量未填滿。長度 的碼對該分佈可以達到熵。
快速檢查
(信源只有一個概率為一的符號。按本節約定,它的熵和最優平均長度是多少?)
使用空字的約定。
解答 · 答案
熵為 。分配空字得到平均長度零,達到下界。實際系統的訊息數量或定界要求可能在模型之外增加成本。