引言
二元 Hamming 碼 [7,4,3] 能糾正任何一位元翻轉。它的最小距離為 3,因此無法可靠地分辨一次翻轉與兩次翻轉。兩位元翻轉所得的伴隨式與某個單位元翻轉的伴隨式形式相同;若解碼器嘗試「糾正」,反而會令字變得更錯。
加入一個整體奇偶校驗位後,可以解決這個問題,得到擴展 Hamming 碼 [8,4,4]。只要明確假設最多有兩個位元翻轉,解碼器便能做到三件事:
- 糾正任何單位元翻轉;
- 識別任何雙位元翻轉,並標示為不可糾正;
- 絕不混淆單位元翻轉與雙位元翻轉。
這稱為 SECDED,即單錯糾正、雙錯檢測。本節從構造一直推導到解碼,也會精確說明解碼器不保證甚麼。每個實際的單位元錯誤都會被糾正,每個實際的雙位元錯誤都會被標示;「最多兩位元翻轉」的假設則讓我們從伴隨式推知是哪一種情況。沒有這個假設,同一解碼器仍可能輸出一個有效但錯誤的碼字。
以下所有運算均在 F2 中進行,故 1+1=0。字一律寫成行向量,由左至右標為位置 1,…,8。
奇偶校驗矩陣
以 F23 中的向量 hi 標記每個位置 i:
h1=(1,0,0),h2=(0,1,0),h3=(0,0,1),h4=(1,1,0),
h5=(1,0,1),h6=(0,1,1),h7=(1,1,1),h8=(0,0,0).
前七個標記恰好是 F23 的七個非零向量,第八個是零向量,故八個標記互不相同。這一事實是以下大部分推導的關鍵。
定義 1.2.1
(擴展 Hamming 碼的奇偶校驗矩陣)
令 H 為 F2 上的 4×8 矩陣,定義如下:
- 第 i 列的首三項是寫成列向量的 hi;
- 每一列的第四項都是 1。
明確寫出來是
H=10010101001111011011011111110001=(H7101).這裏 H7 是列向量依次為 h1,…,h7 的 3×7 Hamming 奇偶校驗矩陣,1 是長度為 7 的全一行。擴展 Hamming 碼定義為
C={x∈F28:HxT=0}.
各行校驗的位置值得記下:第一行校驗 {1,4,5,7},第二行校驗 {2,4,6,7},第三行校驗 {3,5,6,7},第四行校驗全部八個位置。
矩陣 H 的秩為 4。因此 C 是長度為 8、維數 k=4 的線性碼,共有 24=16 個碼字。
考慮 H 的第 1,2,3,8 列:
1001,0101,0011,0001.把它們並排得到一個對角項全為 1 的下三角 4×4 矩陣,行列式是 1=0,所以這四列線性無關。H 的秩至少為 4,而它只有四行,秩也不可能大於 4。由秩與核維數定理,dimkerH=8−4=4。
四個校驗的意義
寫 x=(x1,…,x8) 和 x1:7=(x1,…,x7)。條件 HxT=0 分成兩部分:
H7x1:7T=0,x1+x2+⋯+x8=0.
由於第八列的首三項 h8=0,首三行只涉及前七個位置,恰好表示 x1:7 是 [7,4,3] Hamming 碼字。第四行則表示整個字的重量為偶數。
因此,給定 Hamming 碼字 y∈F27,恰有一個位元 x8 令 (y,x8)∈C,即
x8=y1+⋯+y7.
y 的重量為偶數時此位元為 0,重量為奇數時為 1。所以 C 恰好是 Hamming 碼的奇偶擴展。這與維數計算一致:Hamming 碼有 16 個碼字,每個均有唯一的擴展。
概念視角代數
校驗矩陣同時生成此碼
H 的每一行重量都是偶數,任意兩行共有的位置數也是偶數:第 1 至 3 行兩兩共有兩個位置,各自與第 4 行共有四個。因此每一行都通過全部四個校驗,屬於 C。由於 H 的秩為 4=dimC,它的行組成一組基底,所以 C 等於自身的對偶碼。此外 wt(x+y)=wtx+wty−2∣x∩y∣,而正交的字共有偶數個 1,所以可被四整除的重量在相加後仍可被四整除。由行重量 4,4,4,8 出發,每個碼字的重量都是 0、4 或 8,再次得到 d≥4。
最小距離為四
化簡。 C 是線性的。碼字 a,b 的距離等於 a+b 的重量,而 a+b 仍是碼字。因此最小距離等於非零碼字的最小重量。
關鍵等式。 若 x 的支集為 S,則 HxT 等於 S 中各位置所對應的列之和。因此
HxT=(i∈S∑hi, ∣S∣mod2).排除奇數重量。 若 ∣S∣ 是奇數,最後一項為 1,故 x∈/C。這一步同時排除重量 1 和 3,作用來自全一行。
排除重量二。 若 S={i,j} 且 i=j,首三項是 hi+hj。在 F23 中,hi+hj=0 當且僅當 hi=hj;標記互不相同,所以 hi+hj=0,x∈/C。這是不同列標記的作用。j=8 亦包括在內:此時 hi+h8=hi,對 i≤7 非零。
達到重量四。 取 x=11010001,其支集為 {1,2,4,8}。因為
h1+h2+h4+h8=(1,0,0)+(0,1,0)+(1,1,0)+(0,0,0)=(0,0,0),而 ∣S∣=4 是偶數,所以 HxT=0;這是一個重量為 4 的碼字。
證明透視
矩陣每部分各司一職
關鍵一步是那條等式:它把伴隨式拆成支集上標記之和與支集大小的奇偶。拆開之後,H 的每部分只做一件事。奇偶校驗行一步排除所有奇數重量;八個標記互不相同(包括零標記 h8)則排除重量二。單靠任何一部分都不能得到距離 4:單用 Hamming 矩陣 H7 仍容許重量 3 的字 1101000,單用奇偶校驗行則容許重量 2 的字 11000000。最後一步不可省略:排除重量一至三只證明 d≥4,明確的碼字 11010001 才證明 d≤4,論證至此完成。
下文的解碼器讀取的,正是伴隨式這種「標記部分加奇偶部分」的拆分。
伴隨式與檢測
對收到的字 r∈F28,其伴隨式為
HrT=(u,z),u=H7r1:7T∈F23,z=r1+⋯+r8∈F2.
假設傳送的是 c∈C,收到 r=c+e,其中 e 為錯誤模式。則 HrT=HcT+HeT=HeT。伴隨式只取決於錯誤,而不取決於傳送的碼字。 由關鍵等式,支集為 S 的錯誤滿足
u=i∈S∑hi,z=∣S∣mod2.
定理 1.2.5
(距離 d 可檢測至多 d−1 個錯誤)
設 C 是最小距離為 d 的線性碼,且 1≤wt(e)≤d−1。對每個 c∈C,c+e 都不是碼字。
假設 c+e∈C。由線性性,e=(c+e)+c∈C。但 e 非零且重量小於 d,與 d 的定義矛盾。
本碼的 d=4,故重量 1、2 或 3 的每個錯誤都產生非零伴隨式。因此「HrT=0 嗎?」這個碼字成員測試對所有這些錯誤都不通過。
這是嘗試糾正之前的檢測結論,並不說明糾錯解碼器之後會如何處理該字。
SECDED 解碼器及其假設
定理 1.2.6
(最多兩位元翻轉的假設下的精確分類)
假設 r=c+e,其中 c∈C 且 wt(e)≤2。伴隨式 (u,z) 決定錯誤重量,以下規則涵蓋所有情況:
- u=0, z=0。 沒有錯誤,r=c。
- z=1。 恰有一位元翻轉;其位置是滿足 hi=u 的唯一 i∈{1,…,8}。特別地,u=0 表示奇偶校驗位,即位置 8。翻轉 ri 可恢復 c。
- z=0, u=0。 恰有兩位元翻轉。解碼器須標示該字不可糾正,不可嘗試識別這一對位置。
逐一考慮可能的錯誤重量:
- 重量 0: 伴隨式為 (0,0)。
- 重量 1,位置 i: 伴隨式為 (hi,1)。八個標記互不相同,而 ∣F23∣=8,所以每個 u∈F23 恰好標記一個位置,u 決定 i。
- 重量 2,不同位置 i,j: 伴隨式為 (hi+hj,0)。上文已證 hi+hj=0,故 u=0。
三個結果集合 {(0,0)}、{z=1} 及 {z=0,u=0} 兩兩不相交。因此在該假設下,觀察到的情況確定 e 的重量。
為何無法識別該對位置。 有 (28)=28 種雙位置錯誤,卻只有 7 個非零 u。每個非零 u 恰好是 4 對標記的和:對每個位置 i,配對位置 j 由 hj=hi+u 唯一決定,得 8 個有序對,即 4 個無序對。因此規則 3 總是面對四重歧義。
若解碼器只讀 u,並像 [7,4,3] Hamming 解碼器那樣翻轉標記為 u 的位置,就會把雙錯變成三錯。從 c=00000000 出發翻轉位置 1 和 2,收到 11000000,其 u=110=h4。翻轉位置 4 得 11010000,其前七位是 Hamming 碼字 1101000,於是數據部分被「確定地」改錯。規則 3 正是為阻止這種情況:當 z=0 且 u=0 時,不翻轉任何位置。
要糾正所有 t 位錯誤,需要 d≥2t+1;所以 d=4 只給出 t=1,而非 t=2。具體來說,11100010 是碼字(支集 {1,2,3,7},標記之和為零,大小為偶數),而收到的字 11000000 與 00000000 和 11100010 的距離都是 2。多出的一個單位距離換來的是檢測第二個錯誤,而不是糾正它。
解碼步驟示例
三個例子均以 c=00000000 為傳送碼字。
收到的字為 r=00001000。逐行計算:
- 第一行校驗 {1,4,5,7},其中有一個 1,故所得位元為 1。
- 第二行校驗 {2,4,6,7},其中沒有 1,所得位元為 0。
- 第三行校驗 {3,5,6,7},其中有一個 1,所得位元為 1。
- 第四行總共數到一個 1,所得位元為 1。
伴隨式是 (u,z)=(101,1)。因 z=1,使用規則 2,且 u=101=h5。解碼器翻轉位置 5,輸出正確的 00000000。
例題 1.2.8
(位置 1 和 2 的雙位元翻轉)
收到 r=11000000。第一行給出 1(位置 1),第二行給出 1(位置 2),第三行給出 0,第四行數到兩個 1,故給出 0。
伴隨式是 (110,0)。由於 z=0 且 u=0,使用規則 3,解碼器將該字標示為不可糾正。
比較位置 3 和 7 的錯誤,其收到的字為 r′=00100010。它的 u=h3+h7=(0,0,1)+(1,1,1)=(1,1,0),而 z=0;因此 r′ 產生相同的伴隨式 (110,0)。
事實上,產生 u=110 的四對位置是 {1,2}、{3,7}、{4,8} 和 {5,6}。單靠伴隨式無法選出其中一對。
例題 1.2.9
(位置 1、2 和 4 的三位元翻轉)
收到 r=11010000。第一行看到位置 1 和 4,故給出 0;第二行看到位置 2 和 4,故給出 0;第三行給出 0。第四行數到三個 1,故給出 1。
伴隨式為 (000,1),非零,因此錯誤被檢測出來:r∈/C。
然而,按規則操作的解碼器讀到 z=1 和 u=0=h8,便翻轉位置 8 並輸出 11010001。這確是一個非零碼字,卻不是傳送的碼字;這稱為誤糾正。
下面的互動圖讓你翻轉所選碼字的任意位元,並顯示伴隨式 (u, z)、所用規則與解碼器輸出,可見單位元翻轉被糾正、雙位元翻轉被標示、三位元翻轉被誤糾。
探索MATH4260 · [8,4,4]
在 [8,4,4] 碼中加入錯誤並讀出伴隨式
先選定傳送的碼字 c,再在位置 1 至 8 切換錯誤位元。圖中會形成 r = c + e,用 H 的四行算出伴隨式 (u, z),套用三條 SECDED 規則,並把解碼器輸出與 c 比較。
按位置列出的字 | 位置 1 | 位置 2 | 位置 3 | 位置 4 | 位置 5 | 位置 6 | 位置 7 | 位置 8 |
|---|
| 傳送 c | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
|---|
| 錯誤 e | 0 | 0 | 0 | 0 | 1* | 0 | 0 | 0 |
|---|
| 接收 r | 0 | 0 | 0 | 0 | 1* | 0 | 0 | 0 |
|---|
| 解碼器輸出 | 0 | 0 | 0 | 0 | 0* | 0 | 0 | 0 |
|---|
H 各行的伴隨式| 行 | 校驗的位置 | 其中 r = 1 的位置 | 該行之和 |
|---|
| 1 | {1,4,5,7} | {5} | 1 |
|---|
| 2 | {2,4,6,7} | 無 | 0 |
|---|
| 3 | {3,5,6,7} | {5} | 1 |
|---|
| 4 | {1,2,3,4,5,6,7,8} | {5} | 1 |
|---|
伴隨式 (u, z) = (101, 1). 規則 2:z = 1,假設有一位元翻轉,位置 i 滿足 h_i = u;此處 i = 5。
- 錯誤重量 wt(e)
- 1
- 假設 wt(e) ≤ 2 成立
- 是
- 伴隨式 (u, z)
- (101, 1)
- 結果
- 正確
- 接收 r
- 00001000
- 解碼器輸出
- 00000000
結果: 正確. 假設內的單一翻轉:規則 2 翻轉位置 5,恢復了 c。
為何整體奇偶校驗位能區分各種情況
c + e 的伴隨式只取決於 e:u 是翻轉位置標記 h_i 之和,z 是翻轉個數的奇偶性。
在 wt(e) ≤ 2 的假設下,z = 1 表示恰有一位元翻轉,而八個標記互不相同,所以 u 指出其位置;z = 0 且 u ≠ 0 表示兩位元翻轉,因為 i ≠ j 時 h_i + h_j ≠ 0。
超出假設時,三位元翻轉同樣有 z = 1,規則 2 會再改動一個位置,輸出 c 加上一個重量為 4 的碼字,是有效但錯誤的碼字。
本圖採用本節固定的碼及其 H。確定性規則會套用於任何重量的錯誤集合;完整的分類只在 wt(e) ≤ 2 下成立。圖中沒有為任何錯誤圖樣的出現機率建模。
超出假設時
反例模式
有效輸出不一定正確
容易相信的說法。「SECDED 糾正每個單錯並檢測每個雙錯,所以只要它輸出碼字而沒有發出警示,訊息就是正確的。」
反例。 第三個示例推翻了這說法。三位元翻轉產生 (000,1),與位置 8 的單位元翻轉之伴隨式完全相同。解碼器沒有警示,輸出有效碼字 11010001,但訊息錯了。
更嚴重的失敗。 錯誤 e=11010001 本身就是碼字,因此 HeT=0,r=e 通過測試,被視為無錯。解碼器輸出錯誤碼字,完全沒有警告。
第三個示例並非偶發;以下定理顯示每個三位元錯誤都會發生同樣情況。
設 wt(e)=3。則 c+e 的伴隨式有 z=1。按上述規則運作的解碼器會翻轉一個位置,輸出一個不同於 c 的碼字。
重量為奇數,故 z=1。解碼器翻轉滿足 hi=u 的位置 i,翻轉後伴隨式變成
(u+hi, 1+1)=(0,0),因此輸出是碼字 c+e+ei,從而 e+ei∈C。此外,重量 3 的向量不可能等於重量 1 的向量,故 e+ei=0,輸出不同於 c。由於 C 沒有重量小於 4 的非零碼字,而 e+ei 的重量至多為 4,它的重量恰為 4。
因此精確保證如下:
- 沒有任何錯誤數量假設時: 糾正前的成員測試可檢測重量 1 至 3 的每個錯誤。每個單位元錯誤都會被糾正,但單憑伴隨式無法確定實際錯誤重量。某些重量 4 的錯誤,例如本身就是碼字的 11010001,完全不能被檢測。
- 在 wt(e)≤2 的假設下: 單位元翻轉被糾正,雙位元翻轉被標示;沒有任何特定雙錯模式可被識別出來。
只說「檢測雙錯、糾正單錯」卻不交代假設,容易導致錯誤推論。在容許三位元翻轉的模型中,糾錯規則會把每個可檢測的三錯轉成沒有警示的錯誤答案。本節不對實際硬件中各錯誤模式的概率作任何聲稱,也不對刻意選擇錯誤的對手所構成的安全性作聲稱。
快速檢查
(在最多兩位元翻轉的假設下,伴隨式為 (011,1)。解碼器會怎樣做?)
解答 · 答案
因 z=1,恰有一位元翻轉。標記 u=011 等於 h6,故解碼器翻轉位置 6。
練習
快速檢查
(字 1101000 是 [7,4,3] Hamming 碼字。求它的擴展碼字,並用 H 驗證。)
解答 · 引導解答
位元為 y=(1,1,0,1,0,0,0)。先驗證 y 是 Hamming 碼字:其支集為 {1,2,4},而 h1+h2+h4=(0,0,0),符合要求。
y 的重量是奇數 3,故奇偶校驗位 x8=1。擴展字為 x=11010001。
用 H 驗證:
- 第一行校驗 {1,4,5,7}。位置 1 和 4 是 1,故和為 0。
- 第二行校驗 {2,4,6,7}。位置 2 和 4 是 1,故和為 0。
- 第三行校驗 {3,5,6,7}。這些位置都不是 1,故和為 0。
- 第四行總共數到四個 1,故和為 0。
因此 HxT=0,x∈C。
快速檢查
(傳送碼字 c=11010001,只有奇偶校驗位翻轉。計算伴隨式,並在最多兩位元翻轉的假設下解碼。)
解答 · 引導解答
收到 r=11010000。由於 e=e8,伴隨式為 (h8,1)=(000,1)。逐行檢查:
- 第一行:位置 1 和 4 是 1,所得位元為 0。
- 第二行:位置 2 和 4 是 1,所得位元為 0。
- 第三行:沒有 1,所得位元為 0。
- 第四行:三個 1,所得位元為 1。
因 u=0,使用規則 2。解碼器翻轉位置 8,正確恢復 11010001。
這個收到的字與三錯示例中的完全相同。同一個 r 既可由 11010001 經一次翻轉產生,也可由 00000000 經三次翻轉產生;只有上述假設才能選定第一種解釋。
快速檢查
(從 00000000 出發,證明位置 {1,2} 與位置 {3,7} 的錯誤產生相同伴隨式,並解釋解碼器必須怎樣做。)
解答 · 引導解答
對位置對 {1,2}:h1+h2=(1,0,0)+(0,1,0)=(1,1,0),且 z=0。
對位置對 {3,7}:h3+h7=(0,0,1)+(1,1,1)=(1,1,0),且 z=0。
兩者都給出伴隨式 (110,0);位置對 {4,8} 和 {5,6} 亦然。
因 z=0 且 u=0,使用規則 3。在該假設下,解碼器知道恰有兩位元翻轉,卻不知道是哪兩個,故須標示不可糾正。翻轉與伴隨式相容的四個候選位置對中的任何一對,在四種情況中有三種會得到錯誤碼字。
快速檢查
(從 00000000 出發,翻轉位置 1,2,4,8。接收端觀察到甚麼?)
解答 · 引導解答
收到 r=11010001。第一行看到位置 {1,4},給出 0;第二行看到 {2,4},給出 0;第三行沒有看到 1,給出 0;第四行數到四個 1,給出 0。
伴隨式為 (000,0),接收端接受 11010001,視其為無錯。
這個錯誤無法檢測,因為它本身是非零碼字。檢測定理只涵蓋重量至多 d−1=3,故在此不提供保護。
快速檢查
(在最多兩位元翻轉的假設下,解釋解碼器為何能糾正單錯並標示雙錯。若該假設不成立,實際發生三位元翻轉,解釋同一規則為何會誤糾正。)
解答 · 引導解答
單錯。 位置 i 的單次翻轉給出伴隨式 (hi,1)。八個標記互不相同並覆蓋整個 F23,所以 u 指出唯一位置。翻轉該位置便恢復 c。
雙錯。 位置 {i,j} 的雙次翻轉給出 (hi+hj,0)。由於 hi=hj,u 非零,故伴隨式既不是 (0,0),也不是 z=1 的形式。因此觸發規則 3,解碼器標示該字。無法恢復該對位置,因為每個非零 u 都來自四個不同的對。
三錯。 三次翻轉的重量為奇數,故 z=1,與單次翻轉無法區分。解碼器翻轉標記為 u 的位置,得到碼字 c+e+ei。其中 e+ei 是重量為 4 的非零碼字,因此輸出錯誤。例如位置 {1,2,4} 的錯誤給出 (000,1),解碼器輸出 11010001,而非 00000000。
這個保證依賴上述假設。沒有該假設時,z=1 的伴隨式不能證明只有一位元翻轉。