有噪聲的通道可能改變傳送的字。冗餘只有在合法字之間相距足夠遠時才有用;否則同一個接收字可能來自兩個不同訊息。我們先精確描述這種距離,再用線性代數定位單個錯誤。
定義
定義 1.1.1
(漢明距離、重量與最小距離)
對 ,漢明(Hamming)距離 是它們不同的座標數,重量 是非零座標數。因此 。二元碼 是 的非空子集;至少有兩個碼字時,其最小距離定義為
距離滿足三角不等式:在 不同的每個座標, 或 必有一對不同。計算座標便得 。
定理 1.1.2
(糾錯半徑)
對非負整數 ,至少含兩個碼字的碼能以唯一最近鄰解碼糾正所有至多 位錯誤,當且僅當 。
證明
(球互不相交,相交時取中間的字)
設 ,傳送碼字 ,收到 且 。對任何其他碼字 ,三角不等式給出
所以 是距 最近的唯一碼字。反過來,若兩碼字在 個座標不同,將第一個碼字其中 個不同座標改為第二個的值,得到的字 與兩者距離分別為 和 ,均不超過 。 可由任一碼字經至多 位錯誤得到,而解碼器只輸出一個字,所以沒有解碼器能對這兩種傳送情況都保證正確。
證明透視
因子二從哪裏來
正方向只用一次三角不等式,以傳送字作中間點:從至少 的間隔中扣去 位錯誤,剩下至少 ,仍然勝過 。反方向需要一個同時距兩個碼字都不超過 的接收字。關鍵一步是改動 個不同座標中的 個,得到距離 與 。兩者都不超過 當且僅當 ,而這樣的 存在當且僅當 ;平均分配 總在這個範圍內。「至少兩個碼字」的假設只是為了令 有定義;只有一個字的碼無需解碼。
對非負整數 ,偵錯的門檻不同:恰當條件是 ,此時所有非零的至多 位錯誤都能被發現。發現接收字不合法不等於能找回原字。例如重複碼 距離為三,可偵測兩位錯誤並糾正一位錯誤,卻不能保證糾正兩位錯誤。
定理/命題
定義 1.1.3
(線性碼、生成矩陣與校驗矩陣、伴隨式)
二元線性碼是子空間 ; 碼維數為 ,故有 個碼字。生成矩陣 的行構成 的基底,行訊息 編碼為 。校驗矩陣 滿足 。接收字 的伴隨式是 。
非零線性碼的最小距離等於非零碼字的最小重量:不同碼字之差恰好遍歷非零碼字,因為每個非零碼字也可寫成它與零之差。若接收字為 ,其伴隨式為 ,與傳送碼字無關。於是可用常見錯誤圖樣建表,將伴隨式對應到修正方式。但不同錯誤圖樣可以具有相同伴隨式,單憑它不能證明實際發生了哪個錯誤。
考慮二元 碼,其校驗矩陣的列依次為七個不同的非零二元三維向量:
前三列為單位矩陣,故秩為三,核的維數為四。沒有重量一的非零核向量,因為沒有零列;也沒有重量二的,因為列彼此不同。第一、二、四列之和為零,因此 是重量為三的碼字。最小距離恰為三,能糾正一位錯誤。
例題 1.1.4
(在七位碼中糾正一位錯誤)
若收到 ,其伴隨式為第 1、4 列之和 ,即第 2 列。單錯誤規則翻轉第 2 位,得到 。若實際發生兩位錯誤,這個規則可能輸出其他碼字;糾錯半徑定理只保證至多一位錯誤時糾正成功。
球填充與參數限制
二元空間中半徑為 的球有 個字:只需選擇翻轉的位置。這些球互不相交,便限制了任何糾錯碼的大小。
定理 1.1.5
(漢明界)
若長度為 的二元碼 能糾正所有至多 位錯誤,則
證明
(計數「碼字及其球中一個字」的配對)
把每對「碼字及其半徑 球中的一個字」對應到後者。這些球互不相交:若一個字距兩個碼字都不超過 ,它可由其中任一個傳送而來,便不能對兩者都正確解碼。因此不同的對不能對應到同一接收字。配對共有 個,它們單射到 個可能的接收字。
上述例子滿足 ,故半徑一的球恰好劃分整個空間。這等式是計數結論,不表示實際錯誤一定不超過一位。
快速檢查
(長度為五、有八個碼字的二元碼能否糾正所有單錯誤?)
以 套用漢明界。
解答 · 答案
不能。漢明界要求 ,但 。
練習
快速檢查
(對上面的七位碼,假設至多發生一位錯誤,解碼 。)
計算伴隨式,並與 的各列比較。
解答 · 答案
伴隨式是第 3 列 。翻轉第 3 位得到 ,它是合法碼字;由假設及最小距離三,它是距接收字至多一的唯一可能傳送字。
伴隨式表的局限
反例模式
伴隨式不能確定所有錯誤
兩個錯誤向量 的伴隨式相同,當且僅當 ,等價於 。因此僅憑伴隨式,無法區分同一個陪集中的錯誤。對七位碼,錯誤 與 的伴隨式相同。若傳送零碼字後發生前一種錯誤,單錯誤解碼器反而翻轉第二位,輸出 。這雖是合法碼字,卻不是傳送字。這是兩個錯誤導致解碼失敗的具體例子。
若 校驗矩陣滿秩,線性映射 滿射,故有 個伴隨式。每個伴隨式類有 個向量:若 具有該伴隨式,則類中每個向量都可唯一寫成 ,其中 。每類的最小重量代表稱為陪集首領。減去一個陪集首領就是最近碼字解碼: 是碼字當且僅當 與 伴隨式相同,而它與 的距離為 的重量。若最小重量代表不止一個,可以規定如何選擇,但不能因此聲稱唯一解碼。
快速檢查
(為甚麼七位例子中兩個重量為一的不同錯誤不能具有相同的非零伴隨式?)
重量一的向量的伴隨式是甚麼?
解答 · 答案
重量一的向量的伴隨式等於 中相應的列。七列互不相同且均非零,所以單錯誤的位置可由伴隨式確定。這個結論不適用於重量至少為二的錯誤。
例題詳解
定理 1.1.6
(由相關的列讀出最小距離)
對含非零碼字的二元線性碼 ,最小距離等於和為零的最少列數。即使兩列相等,也要按列所在位置分別計數。
證明
(乘以一個字就是選取列)
恰好把 的非零座標所對應的列相加。因此 等價於這些列之和為零,選中的列數正是 的重量。線性碼的最小距離是非零碼字的最小重量,對非零 取最小值即得結論。
這個判別法把搜尋碼字轉化為檢查列的線性關係。零列給出重量一的碼字;兩條相等的列給出重量二的碼字。反過來,若少於 條的任意列都線性無關,則沒有重量小於 的非零碼字。但若要斷言最小距離恰為 ,還須展示 條線性相關的列。七位矩陣的前三列線性無關,但第一、二、四列之和為零。
概念視角組合
重量為三的碼字就是 Fano 平面的直線
把 的七列看作 Fano 平面的七個點;其直線是 中由不同非零向量組成的三元組 。由上述定理,重量為三的碼字恰好是三個和為零的不同列,也就是一條直線。每條直線包含 個點對中的三個,而每個點對恰在一條直線上,所以共有 條直線,即恰有 個重量為三的碼字。碼字 對應直線 。
常見錯誤
(只檢查一組列而非全部)
不能僅憑七位矩陣前三列線性無關就斷言距離為四:必須檢查所有三列組合才能排除重量三,而第 1、2、4 列正是一組線性相關的三列。
例題 1.1.7
(單一的整體校驗位)
考慮校驗矩陣 ,其核由偶重量的二元四維向量組成。唯一一行非零,故核的維數為三;沒有零列,而任意兩列之和為零,所以距離為二。例如 與 的距離為二。此碼能偵測任何單錯誤,卻不能唯一糾正所有單錯誤。收到 時,既可能傳送 並翻轉第一位,也可能傳送 並翻轉第二位。
此例也說明校驗與定位不同。單位元伴隨式顯示接收字是否為奇重量;非零伴隨式表明發生了奇數次翻轉,卻不指出四個位置中的哪一個被翻轉。偶數次翻轉可能給出零伴隨式,因此接收字通過校驗並不能證明沒有錯誤。
仔細計數解碼球
碼字 的半徑 球由所有與它相差至多 個座標的字組成。當 時,恰有 個字與它距離為 ,因為每個二元座標只有一個可替換的值。對 求和便得漢明界中的球大小。若 ,球就是整個空間,求和可以在 處停止。
漢明界取等號意味著這些球覆蓋空間,但並不意味著任意高重量錯誤都能糾正。七位例子中的每個接收字都恰屬於一個半徑一的球;由兩位錯誤產生的字雖然也在某個球內,其球心卻可能不是傳送字。
快速檢查
(某二元線性碼校驗矩陣的列依次為 。求維數及最小距離。)
先求 的秩,再找和為零的最少列數。
解答 · 答案
前兩列說明矩陣秩為二,故核的維數為 。沒有零列,排除重量一;第三、四列相等,故 是重量二的碼字。因此最小距離為二。結論同時需要下界和達到下界的例子。
從生成矩陣構造校驗矩陣
若二元生成矩陣為系統形式 ,則可以取
確實,由於特徵為二,,故每個生成的碼字均在 中。單位矩陣塊使 的秩為 ,由秩—零度定理其核維數為 。 包含 ,所以其行空間維數也為 。兩個同維空間之間已有包含關係,故它們相等。這裏的加號依賴特徵二;一般域上應取 。
例題 1.1.8
( 碼的校驗矩陣)
令 。此處 ,故 。其核是偶重量二元三維向量。生成矩陣兩行線性無關,四個碼字為 ;非零碼字重量均為二,因此最小距離為二。一個校驗位增加了冗餘,能偵測單錯誤,但依糾錯半徑定理不能糾正所有單錯誤。
常見錯誤
常見錯誤
(一對距離為三的碼字不證明距離為三)
最小距離是整個碼的性質,不是某一對碼字的性質。找到距離三的一對只能證明最小距離至多為三;要證明恰為三,還須排除所有更小距離。對線性碼可改查非零碼字的重量,但這個簡化依賴減法封閉,對任意子集不成立。
常見錯誤
(伴隨式為零不等於沒有錯誤)
非零伴隨式說明接收字不是碼字;零伴隨式只說明它屬於碼。未被發現的錯誤可能把一個碼字變成另一個碼字。事實上,給傳送字加上任意非零碼字仍得到碼字,因此伴隨式為零。此類事件有多可能,要看此處尚未指定的通道模型。