海明碼
海明碼
海明碼是最為常見的糾錯碼，實(shí)現(xiàn)原理就是加入校驗(yàn)位形成海明碼。然后根據(jù)檢驗(yàn)位檢驗(yàn)錯誤、糾正錯誤。
海明碼分為五個步驟
- 確定校驗(yàn)位的位數(shù)
如果有 n 位的有效信息位數(shù)，k 位的校驗(yàn)位的位數(shù)，則信息位 n 和校驗(yàn)位 k 需要滿足
\(n + k \leq 2^k -1\) （這里只能檢測一位錯誤，減去 1 是沒有發(fā)生錯誤的情況，而剩下 \(2^k - 1\) 則是對應(yīng) n + k 位中哪一位出錯的情況）
例： 有效信息位為 4 位 那么需要的校驗(yàn)位需要滿足 \(4 + k \leq 2^k - 1\) 則 k 最小位 3 位 - 確定校驗(yàn)位位置
規(guī)定中校驗(yàn)位 Pi 在海明位號為 2^(i-1) 的位置上,上面提到校驗(yàn)位有 3 位：P1 位置為 1，P2位置為 2，P3位置為 4；
對應(yīng)為
D4 D3 D2 P3 D1 P2 P1 => 111 110 101 100 011 010 001 - 分組求校驗(yàn)值
P1(##1): D1 D2 D4
P2(#1#): D1 D3 D4
P3(1##): D2 D3 D4
利用偶檢驗(yàn)（默認(rèn)是偶檢驗(yàn)，也就是直接數(shù)據(jù)位異或操作）
P1 為 P1 分組中奇偶檢驗(yàn)的偶校驗(yàn)的值，P1 為校驗(yàn)位，D1 D2 D4 為數(shù)據(jù)位 => P1 = D1 ? D2 ? D4
P2，P3同理 - 校驗(yàn)
校驗(yàn)值為分組中所有數(shù)據(jù)異或
S1 = P1 ? D1 ? D2 ? D4
S2 = P2 ? D1 ? D3 ? D4
S3 = P3 ? D2 ? D3 ? D4
拼接 S3S2S1，如果 S3S2S1 = 000 則說明沒有錯誤，如果 = 001 則說明第一位出現(xiàn)了錯誤，也就是 P1 出現(xiàn)錯誤
碼距
兩個相同長度的字符串中，把其中一個字符串替換成另一個字符串需要的操作次數(shù)
如： 10000 和 10001 的碼距為 1，只需要把末尾的 0 換成 1 即可
而： 00000 和 11111 的碼距為 5，需要把五個 0 換成 1
編碼的海明距是指該種編碼中最小的存在的碼距
對此引出如下結(jié)論
1）海明碼“糾錯” d 位，需要的編碼碼距最小為 2d + 1
2）海明碼“檢錯” d 位，需要的編碼碼距最小為 d + 1
對于 1）
因?yàn)橹挥挟?dāng)碼距大于 2d + 1 時，才存在一個碼距最接近的值與之對應(yīng)
例：編碼為 A（100000） B（111111） 如果 A 發(fā)生了兩位錯誤變成了 100011 則此時這段與 A 的碼距為 2，與 B 的碼距為 3，所以能推斷是 A 發(fā)生了錯誤，并對其進(jìn)行糾正，相反如果編碼為 A（10000） B(11111) ,此時 A 發(fā)生了兩位錯誤變成了 10011，此時這段字符串與 A 的碼距為 2，與 B 的碼距也為 2，無法判斷是 A 發(fā)生了錯誤還是 B 發(fā)生了錯誤，所以說需要碼距大于 2d + 1
對于 2）
在編碼碼距為 d + 1 中只改變了 d 位的數(shù)據(jù)是不可能變?yōu)榱硪粋€合法值的，所以最小為 d + 1 位
更詳細(xì)的可以看一下 NR-LDPC編碼(一)：糾錯編碼基本原理 - 知乎 (zhihu.com)
浙公網(wǎng)安備 33010602011771號