能容納多少個碼字?
最小距離要求使碼字互相分離,但能選多少個並不顯然。我們以構造證明下界,並以互不相交的球裝箱證明上界;兩界不一定相等。
定義 13.1.1
(漢明距離與球體積)
設 是有 個符號的字母表,、,三者都是整數。兩個長度為 的字的漢明(Hamming)距離是不同座標的數目。碼是一組字;它不必線性, 也不必是質數冪。記
這是與固定字距離至多 的字的數目:選 個座標,每個座標有 個替代值。此數目與中心無關。
貪心存在性下界
定理 13.1.2
(貪心覆蓋界)
存在碼 ,任意兩個不同碼字距離至少為 ,且
這是有限情況下的貪心 Gilbert–Varshamov 界。
證明
(貪心選取直至覆蓋整個空間)
開始時所有字都可選。任選一個可選字加入 ,然後移除與它距離至多 的所有字。重複至沒有可選字為止。每次至少移除所選字,有限的可選集合因此令過程終止。每個後選的字都在先前所選字的半徑 球外,所以所選字兩兩距離至少為 。
終止時,所選字周圍半徑 的球覆蓋全部 個字。球可以重疊,所以並集大小至多是各球大小之和。因此 ,得到上述向上取整的界。因為 ,球小於整個空間,該界至少給出兩個碼字。
證明透視
覆蓋不是裝箱
有限性只用於終止:每一輪至少從有限集合中移除所選字。間距來自移除規則,因為與所選字距離至多 的字在下一次選取前都已刪去。關鍵一步是倒過來讀停止條件:既然沒有可選字,所選字周圍半徑 的球便覆蓋整個 。
論證以並集界收結,而並集界容許重疊;正因如此,不等式的方向恰好給出 的下界。這裏的半徑是 ,不是糾錯半徑,各球也不必互不相交。下面的裝箱界用的是相反的計數方式。
裝箱上界
定理 13.1.3
(漢明裝箱界)
令 。任意兩個不同碼字距離至少為 的每個碼 都滿足
證明
(半徑 t 的不相交球)
碼字周圍半徑 的球互不相交:若有共同字,由三角不等式可知兩個不同碼字的距離至多為 。所有球都位於 ,所以 。因為 是整數,可以取向下取整。
兩個界分別使用半徑 和 ,主張也不同:第一個構造某個具有最小數量保證的碼;第二個限制所有具有指定間距的碼。一般而言,這些界未必能確定可能的最大碼;如果兩界相等,則可以確定。
例題 13.1.4
(五個二元位置,距離三)
對 、、,貪心球體積為 ,定理保證至少 個字。裝箱半徑為 ,,因此所有這樣的碼至多有 個字。
四個字 構成最小距離為三的具體碼:其非零字的重量是 ,後三個字兩兩之差的重量為 。此構造改進了本例的下界,但本身不能排除五字碼的存在。
反例模式
極大不等於最大
貪心算法在包含關係意義下的極大碼處停止:不能再加入任何字而保持距離要求。這性質本身不證明其碼字數是所有碼中最多的。在二元 的例子中,先選 再選 ,每個字已在其中一個字距離二以內:任何字的重量不是至多二,就是至少三。這個極大碼有兩個字,而上面的四字碼更大。覆蓋論證保證一個數量下界,沒有聲稱最優。
例題 13.1.5
(兩界相遇的三元碼)
取 、、。貪心體積為 ,所以存在至少 個字的碼。裝箱半徑為 ,,所以每個碼至多有 個字。碼 中兩兩距離都是三,因此達到上界:長度三、最小距離三的最大三元碼恰有三個字。這裏字母表 只作為符號集合使用,不需要域結構。
例題 13.1.6
(距離等於長度)
在極端情況 ,取 、、。半徑 的球只漏掉中心的補字,所以 ,貪心界給出至少 個字。取 ,,裝箱界給出至多 個字。重複碼 同時達到兩界,所以是最優的;事實上,兩個距離為五的二元字互為補字,第三個字不可能同時是兩者的補字。
常見錯誤
(把兩個半徑互換)
貪心界除以半徑 的球,裝箱界除以半徑 的球。若在貪心界中用半徑 ,對二元 、 便會聲稱存在至少 個字的碼,與裝箱上界 矛盾。不相交只在半徑 成立;覆蓋只在半徑 得到保證。
定理沒有提供甚麼
算法可能需要檢查指數大小的 個字。此存在性證明沒有給出有效率的編碼器或譯碼器、線性碼,亦沒有給出特定通道的錯誤概率。裝箱論證確實給出至多 個符號受損時的唯一性,但要有效率地找出最近碼字仍需額外工作。
習題
快速檢查
(計算 和 的貪心下界。)
距離一以內只有中心及其 個鄰字。
解答 · 答案
,故貪心碼至少有 個字。
快速檢查
(對二元 ,為何裝箱半徑是一,而貪心覆蓋半徑是二?)
比較不相交所用的半徑與算法移除的半徑。
解答 · 答案
中心距離至少三時,半徑一的球互不相交;貪心過程排除距離至多 的字,確保所選中心有要求的間距。
快速檢查
(驗證 的最小距離為三。)
計算全部六個兩兩距離。
解答 · 答案
非零字重量為 ,三個非零字兩兩距離為 ,故最小值為三。
快速檢查
(極大的貪心碼是否必然具有最多碼字?證明實際上確立甚麼?)
比較包含關係意義下的極大與數量上的最大。
解答 · 答案
證明沒有確立這點;它確立包含關係意義下的極大性、兩兩距離至少 和上述數量下界。
延伸閱讀
卡內基梅隆大學編碼理論課程資料 列出 Gilbert–Varshamov 界及基本碼界的講義。