動機
碼以可能訊息的數量換取碼字之間的分離度。球填充解釋了為甚麼可靠的糾錯需要消耗空間。用更大的球進行覆蓋則解釋了為甚麼相當大的分離集合是存在的。當所要求的相對距離很大時,對碼字對進行計數提供了另一類障礙。
這些論證回答的是不同的問題。上界限制每一個碼。下界存在性保證至少有一個碼,而往往沒有可用的解碼器。顯式構造可能優於該下界保證,而並不與之矛盾。我們將始終保持這些方向清晰可辨,包括從有限碼長過渡到漸近碼率的時候。
計數論證起初只需要有限字母表。線性存在性證明還需要有限域,但它不會假設非零碼字相互獨立、隨機矩陣滿秩,也不會假設存在有效的搜尋算法。
定義
定義 1.3.1
(碼、球與碼率)
設字母表有 個符號。長度為 的碼是其 重笛卡兒(Cartesian)冪的一個子集 ,其大小為 。當 時,其最小 Hamming 距離 是不同碼字之間距離的最小值。我們把有限參數的陳述限制在整數 以及距離至少為 的碼上。
記
這是半徑為 的球中的字的個數:選出被改變的位置,並在每個位置從 個替換符號中選一個。每個球心對應的球大小相同。碼率為 。對於 上維數為 的線性碼,這變為 。
定義 1.3.2
( 元熵函數)
對 ,定義
端點處的值由連續性給出。其導數為 ,因此它在 上遞增,並在右端點達到 1。這一單調性限制在體積估計中很重要。
定理/命題
定理 1.3.3
(有限的填充與覆蓋界)
每個長度為 、距離至少為 的碼都滿足
存在距離至少為 的碼,使得 。第一個不等式是 Hamming 界,第二個是 Singleton 界,存在性陳述則是 Gilbert 覆蓋論證。
定理 1.3.4
(一個線性存在性保證)
當 為質數冪時,令 。對任意滿足 的整數 ,存在 上維數至少為 、距離至少為 的線性碼。當 時該和為零,允許取 。
定理 1.3.5
(Plotkin 的碼字對計數界)
令 。若 ,則每個這樣的碼都滿足
整數形式的碼大小可以由右端的向下取整來界定。該假設是嚴格的:在等號處,所示分母為零,此論證不給出有限的大小界。
證明思路或證明
不相交的小球與覆蓋的大球
證明
(不相交的球、打孔與極大碼)
令 。若某個字同時屬於兩個不同碼字的半徑 的球,則由三角不等式,這兩個碼字的距離至多為 。因此這些球兩兩不相交,其總大小不能超過 ,這就證明了 Hamming 界。這一計數證明的是一種限制;它並不實現解碼器。
對於 Singleton 界,刪去任意 個座標位置。若兩個碼字在其餘座標上相同,則它們至多在被刪去的位置上不同,這與距離至少為 矛盾。因此這一刪去座標的映射(打孔映射)是單射,取值於其餘的 個字。這一論證不要求線性性。
對於存在性,從沒有任何字開始,反覆添加一個與每個已選字的距離都至少為 的字,直到無法再添加為止。有限性保證過程終止。所得的碼在包含關係下是極大的。於是環境空間中的每個字都必須落在某個已選碼字的距離 之內,否則它還可以被添加。這些球覆蓋整個環境空間;允許重疊。它們的總大小至少等於其並集的大小,從而 。
證明透視
同一個並集比較指向兩個方向
對於不相交的小球,大小之和等於並集,且至多為環境空間的大小。對於較大的覆蓋球,大小之和至少等於並集,而並集就是整個環境空間。存在性證明依賴於在包含關係下的極大性,而不是找到可能的最大碼。枚舉整個環境空間一般需要關於碼長呈指數級多的步驟。
隨機校驗排除射影意義下的低權方向
證明
(對低權方向用並集界)
現在使用 。選取 矩陣 ,各元獨立均勻取值。對每個固定的非零向量 ,某一行與 的點積在 中是均勻分佈的:選取 的一個非零座標,對該行的其餘元素取條件,並利用剩餘元素上的雙射。各行獨立,故 。
的非零純量倍數具有完全相同的為零事件。權小於 的非零向量分成若干一維子空間,每個子空間含 個具有相同權的非零向量。這樣的方向恰有 個。在每個方向中選取一個代表。並集界表明,某個方向被 映為零的概率至多為 。因此至少存在一個不使任何方向被映為零的 ,其核中沒有權小於 的非零向量。
核是維數為 的線性碼。這裏沒有使用滿秩假設。不同代表所對應的事件不必獨立;並集界並不需要獨立性。此外 ,故總存在某個允許的 ,儘管較弱的選擇可能只保證零維碼。對於僅含一個字的線性碼,距離陳述直接意味著不存在權小於 的非零字。
成功的存在性論證仍留下算法任務
假設我們真的抽取一個矩陣。檢驗其秩很容易,可透過消元完成,但這並不檢驗距離條件。若要直接驗證並集界所用的性質,我們需要檢查沒有低權射影代表落在其核中。它們的數目正是 所計數的量,可隨碼長指數增長。因此該證明給出了存在好矩陣的正概率,但沒有給出可以低成本驗證所觀察到的矩陣為好矩陣的證書。
重複試驗並不能消除這一區別。若對 作更強的選擇,使並集界的失敗概率估計至多為二分之一,則獨立抽取的若干矩陣中至少有一個是好的這一事件就很可能發生。辨識哪個樣本具有所需的最小距離仍將是一個額外的計算問題。有效的編碼器也不能解決這一問題:一旦求得核的一組基底,編碼就只是線性組合,而最近碼字解碼提出的是另一類搜尋問題。
這裏有一個有用的結構單調性。好線性核的任何子碼都保持同樣的距離下界保證,因為去掉字不會引入新的低權非零字。若其維數超過所需的訊息維數,可以選取由較小一組基底所生成的子空間。這一觀察使存在性證明能夠提供方便的碼率,而不必假裝所有冗餘校驗都是獨立的,或某個特定維數被恰好強制。
概念視角代數
線性碼的 Singleton 界就是秩的計數
對 上的線性 碼,設校驗矩陣 的秩為 。一個權為 的非零碼字就是 的 列之間的非平凡線性相關。距離至少為 因此表示任何 列都線性無關,於是 。這再次給出 ,但現在讀作關於列秩的陳述,而不是關於刪除座標。
統計所有座標上的不一致
證明
(逐個座標統計不一致)
對固定的座標,令 為攜帶符號 的碼字個數。在該座標上不一致的無序對數為
因為 ,且 Cauchy–Schwarz 不等式給出 。對 個座標求和。另一方面, 個不同的對中,每一對至少在 個座標上不一致。因此 。約去正數 並整理,得 。只有當 時,除法才是合理的。
證明透視
同一數量的兩種計數
證明把同一數量數了兩次:由一對碼字及它們不一致的一個座標組成的組合。上界計數只用到每個座標上各符號的頻數之和為 ;Cauchy–Schwarz 不等式說明符號平均分佈時不一致的對數最多。下界計數只用到距離。比較式 右邊是 ,左邊卻是 ,正是這個量級為 的差距給出 的上界。當 時,不等式對所有 都成立,推不出任何結論。在精確的例子中兩種計數都取等號:每個座標都平均分佈,每對碼字的距離都恰為四。
把球的大小轉換為熵指數
對 ,令 。項 是參數為 的二項概率分佈的最大項之一,這可由相鄰項之比看出。在它的 項中,某個最大項的概率至少為 。因此
對於反向估計,另設 。對 ,比值 至多為其在 處的值。把每個體積求和項表示為其二項概率乘以這一比值再乘以 ,然後利用概率之和至多為一,得 。在 時,兩個有用的估計都可由體積為一直接得出。
固定 與目標相對距離 。令 。覆蓋估計與體積上界給出碼率至少為 的碼。線性界也是如此:取使 的最小 ,則 ,除去本來就平凡的零和情形。於是對一列線性碼有 。
反之,對任何相對最小距離趨於 的碼,Hamming 不等式中的球下界給出 。 項隨碼長趨於零;它們並不允許丟掉有限長度下的取整,也不允許聲稱任一邊界是精確的最優碼率。若固定的相對距離嚴格大於 ,Plotkin 界給出有界的碼大小,從而碼率趨於零。等號情形 需要進一步論證,不能靠除以零得到。
例題詳解
例題 1.3.6
(界可能留下真實的間隙)
對二元長度 7、距離 3, 且 ,故 Hamming 界給出 。覆蓋存在性界使用 ,保證 。線性論證中 ,故 保證維數至少為二,即至少四個字。二元 Hamming 碼有十六個字,達到上界。它的存在改進了這兩個下界保證;並不使它們失效。
例題 1.3.7
(高距離下緊的碼字對計數)
在 的七個非零向量上,對全部八個二元線性型求值。非零線性型在其中四個向量上取一,故所得線性碼長度為七,有八個字,距離為四。Plotkin 界給出 ,且可以達到。這裏碼字對證明中的座標平衡是精確的:每個非零求值點在全部碼字上看到四個零值和四個一值。
例題 1.3.8
(漸近保證不等於構造速度)
在二元相對距離 時,熵約為 。所證明的存在性論證給出碼率至少趨近 的線性碼。Hamming 漸近上界約為 。這些是帶有間隙的下限與上限約束,而不是對一個已被確定的最優值的兩個估計。隨機校驗證明本身並不提供對每個候選矩陣的多項式時間驗證器,也不提供有效解碼器。
反例與常見錯誤
反例模式
極大性弱於最大性
對二元長度三且所需距離為二, 是極大的:其餘每個字都在它某個成員的距離一之內。但 有四個字且距離要求相同。因此貪心論證可能停在比最優碼更小的碼上。其覆蓋證明仍適用於這個較小的碼。
常見錯誤
(線性保證需要域)
線性存在性定理要求有域;合數大小、以模運算定義的字母表並不是域,均勻點積這一步便會失效。以模 整數為例,乘積 只取值 與 ,所以若向量 唯一的非零元素是 ,均勻隨機行與 的點積並不均勻分佈。
常見錯誤
(在 Hamming 界中誤用覆蓋半徑)
Hamming 上界用的是半徑 的球;半徑 屬於存在性界,那裏不等式方向相反。兩者混用會得出錯誤的限制。對二元長度七、距離三,若用 ,便得 ,但二元 Hamming 碼有十六個字,距離為三。
距離保證只能透過不相交的球來控制最壞情形下的糾錯。它並不會把極大填充構造變成快速的最近碼字過程。
練習
快速檢查
(對三元、長度為四、距離為三的碼,計算 Hamming 與 Singleton 上界。)
解答 · 答案
糾錯半徑為一,球的大小為 。Hamming 界給出 。Singleton 界給出 。兩個上界相等並不是存在性證明,儘管長度為四的三元 Hamming 碼(有九個字、距離為三)確實達到這些參數。
快速檢查
(解釋為甚麼半徑 的球覆蓋並不與半徑 的不相交球相矛盾。)
解答 · 答案
不相交球的半徑,其兩倍嚴格小於 。覆蓋半徑 一般更大;該半徑的球可能大量重疊。極大性保證它們的並集覆蓋所有的字,而該比較中並沒有用到不相交性。
快速檢查
(在隨機校驗證明中,為甚麼應當把非零純量倍數歸為一組,又為甚麼不需要兩兩獨立?)
解答 · 答案
非零純量倍數具有相同的核成員事件,所以把整個方向只計一次可改進充分界。對任意有限個事件,無論相互依賴如何,並集的概率至多為各概率之和。只需要用於計算單個向量概率的行獨立性。
快速檢查
(對二元長度十、距離六應用 Plotkin 界。若距離為五,哪裏會失效?)
解答 · 答案
此處 ,正的分母為 ,得 。距離為五時分母為零;整理後的不等式只寫成 ,不界定任何大小。代入所示分式是無效的。
快速檢查
(下界 是否斷言每個足夠大的具有該距離的碼都有該碼率?)
解答 · 答案
該論證構造或證明了至少存在一列適當的碼。較小的子集保持距離,但碼率可以低得多。因此不能把存在性下界讀作對具有相同最小分離度的每個碼的碼率下界。