1. 項(xiàng)目概述從“糾一檢二”說(shuō)起如果你在計(jì)算機(jī)組成原理、數(shù)據(jù)通信或者網(wǎng)絡(luò)安全的課程里摸爬滾打過(guò)大概率會(huì)碰到一個(gè)名字聽(tīng)起來(lái)有點(diǎn)詩(shī)意但學(xué)起來(lái)可能讓人頭大的概念——海明碼。我第一次接觸它的時(shí)候感覺(jué)就像在看天書(shū)一堆“校驗(yàn)位”、“奇偶校驗(yàn)”、“最小漢明距離”的術(shù)語(yǔ)砸過(guò)來(lái)只知道它能“糾錯(cuò)”但具體怎么糾為什么能糾原理是什么完全是一團(tuán)漿糊。后來(lái)在實(shí)際工作中尤其是在處理一些對(duì)數(shù)據(jù)可靠性要求極高的場(chǎng)景比如內(nèi)存條的ECC校驗(yàn)、高速通信鏈路的數(shù)據(jù)保護(hù)時(shí)我才真正體會(huì)到海明碼的精妙和實(shí)用價(jià)值。它絕不是一個(gè)停留在課本上的理論而是實(shí)實(shí)在在保障數(shù)據(jù)在傳輸和存儲(chǔ)過(guò)程中“不出錯(cuò)”的基石技術(shù)。那么標(biāo)題里的“糾一檢二”到底是什么意思這其實(shí)是海明碼能力的核心概括。“糾一”指的是糾正一位錯(cuò)誤。假設(shè)我們發(fā)送了一串二進(jìn)制數(shù)據(jù)在傳輸過(guò)程中其中某一個(gè)比特0變成1或1變成0發(fā)生了翻轉(zhuǎn)海明碼能夠不僅發(fā)現(xiàn)這個(gè)錯(cuò)誤還能精準(zhǔn)定位到是哪一個(gè)比特錯(cuò)了并把它糾正過(guò)來(lái)?！皺z二”指的是檢測(cè)兩位錯(cuò)誤。如果很不幸同時(shí)有兩個(gè)比特發(fā)生了錯(cuò)誤海明碼雖然無(wú)法確定具體是哪兩位錯(cuò)了可能的情況太多但它能明確地告訴你“數(shù)據(jù)出錯(cuò)了而且錯(cuò)誤不止一位?！?這種“能糾一位能檢兩位”的能力在有限的冗余開(kāi)銷(xiāo)下提供了非常高的可靠性保障。理解海明碼不僅僅是背下公式和步驟更是理解一種設(shè)計(jì)思想如何用最少的“額外信息”校驗(yàn)位來(lái)?yè)Q取最大的“錯(cuò)誤發(fā)現(xiàn)與糾正”能力。這背后是嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)邏輯和巧妙的編碼藝術(shù)。接下來(lái)我們就拋開(kāi)那些讓人望而生畏的數(shù)學(xué)證明用最直白的方式一步步拆解海明碼的構(gòu)造、編碼、校驗(yàn)和糾錯(cuò)全過(guò)程并分享一些我踩過(guò)的坑和實(shí)用的記憶技巧。2. 海明碼的核心思想與設(shè)計(jì)邏輯要理解海明碼必須先理解它要解決的根本問(wèn)題。在數(shù)字系統(tǒng)中數(shù)據(jù)以0和1的比特流形式存在。無(wú)論是通過(guò)網(wǎng)線(xiàn)傳輸還是在內(nèi)存中存儲(chǔ)物理世界的干擾如電磁噪聲、宇宙射線(xiàn)、器件老化都可能導(dǎo)致比特翻轉(zhuǎn)即“位錯(cuò)誤”。我們需要一種機(jī)制來(lái)對(duì)抗這種錯(cuò)誤。最樸素的想法是重復(fù)發(fā)送。比如發(fā)送“1011”我重復(fù)三遍變成“1011 1011 1011”。接收方通過(guò)“投票”來(lái)決定每一位是0還是1三中取二。這種方法能糾錯(cuò)但效率極低冗余度高達(dá)200%。海明碼的目標(biāo)就是在保證一定糾檢錯(cuò)能力的前提下極大化編碼效率即用盡可能少的校驗(yàn)位。2.1 信息位與校驗(yàn)位的關(guān)系2的冪次方魔法海明碼設(shè)計(jì)中最關(guān)鍵的一步是確定校驗(yàn)位要放在哪里以及需要多少個(gè)校驗(yàn)位。這里有一個(gè)黃金公式如果數(shù)據(jù)位信息位有m位我們需要k位校驗(yàn)位那么它們必須滿(mǎn)足2^k m k 1。這個(gè)公式怎么來(lái)的我們可以這樣理解k個(gè)校驗(yàn)位每一個(gè)校驗(yàn)位都可以代表一個(gè)“是/否”的問(wèn)題比如奇偶性。k個(gè)問(wèn)題最多可以區(qū)分2^k種不同的狀態(tài)。我們需要用這些狀態(tài)來(lái)指代一種“無(wú)錯(cuò)誤”的狀態(tài)。m k種“單個(gè)位出錯(cuò)”的狀態(tài)因?yàn)槌鲥e(cuò)位可能是任意一個(gè)信息位或校驗(yàn)位。所以需要的狀態(tài)總數(shù)是1 (m k)。為了能容納所有這些狀態(tài)必須有2^k (m k) 1。舉個(gè)例子假設(shè)我們要保護(hù)4位數(shù)據(jù)m4。那么需要多少校驗(yàn)位(k)呢k2時(shí)2^2 4而 mk1 42174 7不成立。k3時(shí)2^3 8而 mk1 43188 8成立所以保護(hù)4位數(shù)據(jù)需要3位校驗(yàn)位?？偞a長(zhǎng) n m k 7 位。這就是經(jīng)典的(7, 4) 海明碼。2.2 校驗(yàn)位的放置規(guī)則位置編號(hào)的奧秘確定了總位數(shù)7位和校驗(yàn)位數(shù)3位后下一步是決定把這3個(gè)校驗(yàn)位插在7個(gè)位置的哪里。海明碼規(guī)定校驗(yàn)位必須放在位置編號(hào)為2的冪次方的位置上即第1、2、4、8、16...位。對(duì)于我們的(7,4)碼位置編號(hào)從1到7。2的冪次方位置是1(2^0), 2(2^1), 4(2^2)。所以P1第1個(gè)校驗(yàn)位放在位置1P2放在位置2P3放在位置4。剩下的位置3, 5, 6, 7用來(lái)依次填入我們的4位原始數(shù)據(jù)D1, D2, D3, D4。最終一個(gè)7位的海明碼字結(jié)構(gòu)如下_表示待填入 位置 1 2 3 4 5 6 7 內(nèi)容 P1 P2 D1 P3 D2 D3 D4這個(gè)放置規(guī)則是后續(xù)所有奇偶校驗(yàn)計(jì)算的基礎(chǔ)務(wù)必記牢。它背后的深意是每個(gè)校驗(yàn)位的“管轄范圍”由其位置編號(hào)的二進(jìn)制表示決定這實(shí)現(xiàn)了對(duì)數(shù)據(jù)位的交叉覆蓋。2.3 奇偶校驗(yàn)與交叉覆蓋錯(cuò)誤定位的鑰匙這是海明碼最精妙的部分。每個(gè)校驗(yàn)位P1, P2, P3負(fù)責(zé)校驗(yàn)一組特定的數(shù)據(jù)位。分組規(guī)則是某個(gè)數(shù)據(jù)位的位置編號(hào)如果其二進(jìn)制表示在第i位是1那么它就歸第i個(gè)校驗(yàn)位管轄。我們以位置編號(hào)為例注意這里的位置編號(hào)是最終碼字中的位置1到7位置3(D1): 二進(jìn)制是011。第1位最低位是1第2位是1第3位是0。所以D1歸P1和P2管。位置5(D2): 二進(jìn)制是101。第1位是1第2位是0第3位是1。所以D2歸P1和P3管。位置6(D3): 二進(jìn)制是110。第1位是0第2位是1第3位是1。所以D3歸P2和P3管。位置7(D4): 二進(jìn)制是111。第1位是1第2位是1第3位是1。所以D4歸P1、P2和P3管。而校驗(yàn)位自身只出現(xiàn)在由自己負(fù)責(zé)的組里進(jìn)行奇偶計(jì)算。通常我們采用偶校驗(yàn)即讓所負(fù)責(zé)的一組數(shù)據(jù)位該校驗(yàn)位本身其中1的個(gè)數(shù)為偶數(shù)。實(shí)操心得分組記憶技巧死記硬背分組很容易亂。我常用的方法是“二進(jìn)制分解法”。拿到一個(gè)數(shù)據(jù)位的位置號(hào)立刻心算或?qū)懗鏊亩M(jìn)制從右向左分別對(duì)應(yīng)P1, P2, P3...。二進(jìn)制位為1的就是它要參與的校驗(yàn)組。比如D3在位置66的二進(jìn)制是110從右讀P1對(duì)應(yīng)位0P2對(duì)應(yīng)位1P3對(duì)應(yīng)位1所以它參與P2和P3組。這個(gè)方法百試百靈。3. 海明碼的完整編碼與解碼流程理論說(shuō)再多不如動(dòng)手算一遍。我們用一個(gè)完整的例子把編碼、傳輸、檢錯(cuò)、糾錯(cuò)的全過(guò)程走通。3.1 第一步編碼過(guò)程發(fā)送方假設(shè)我們要發(fā)送的4位原始數(shù)據(jù)是D4 D3 D2 D1 1 0 1 1。步驟1確定結(jié)構(gòu)并填入數(shù)據(jù)位根據(jù)(7,4)碼結(jié)構(gòu) 位置 1 2 3 4 5 6 7 內(nèi)容 P1 P2 D1 P3 D2 D3 D4 填入數(shù)據(jù)位后 位置 1 2 3 4 5 6 7 內(nèi)容 P1 P2 1 P3 1 0 1步驟2計(jì)算各個(gè)校驗(yàn)位采用偶校驗(yàn)計(jì)算P1 (負(fù)責(zé)位置 1, 3, 5, 7)這些位置當(dāng)前已知的值是 P1(未知), 位置3(D11), 位置5(D21), 位置7(D41)。為了使得這4個(gè)比特中1的個(gè)數(shù)為偶數(shù)P1需要滿(mǎn)足P1 ⊕ 1 ⊕ 1 ⊕ 1 0。計(jì)算1⊕10,0⊕11所以要結(jié)果為0P1必須是1因?yàn)?⊕10。所以P1 1。計(jì)算P2 (負(fù)責(zé)位置 2, 3, 6, 7)已知 P2(未知), D11, D30, D41。方程P2 ⊕ 1 ⊕ 0 ⊕ 1 0。計(jì)算1⊕01,1⊕10所以 P2 需要是0才能使結(jié)果為00⊕00。所以P2 0。計(jì)算P3 (負(fù)責(zé)位置 4, 5, 6, 7)已知 P3(未知), D21, D30, D41。方程P3 ⊕ 1 ⊕ 0 ⊕ 1 0。計(jì)算1⊕01,1⊕10所以 P3 需要是0。所以P3 0。步驟3組裝最終的海明碼字將所有計(jì)算出的校驗(yàn)位填入 位置 1 2 3 4 5 6 7 內(nèi)容 1 0 1 0 1 0 1 所以我們生成的、帶有糾錯(cuò)能力的7位海明碼字是1 0 1 0 1 0 1從左到右對(duì)應(yīng)位置1到7。3.2 第二步解碼與檢錯(cuò)糾錯(cuò)接收方現(xiàn)在這個(gè)碼字1010101在信道中傳輸。假設(shè)發(fā)生了一位錯(cuò)誤。場(chǎng)景A無(wú)錯(cuò)誤接收方收到1 0 1 0 1 0 1。 接收方重新計(jì)算三個(gè)校驗(yàn)方程同樣用偶校驗(yàn)S1 P1 ⊕ D1 ⊕ D2 ⊕ D4 1 ⊕ 1 ⊕ 1 ⊕ 1 0計(jì)算1⊕10, 0⊕11, 1⊕10S2 P2 ⊕ D1 ⊕ D3 ⊕ D4 0 ⊕ 1 ⊕ 0 ⊕ 1 0計(jì)算0⊕11, 1⊕01, 1⊕10S3 P3 ⊕ D2 ⊕ D3 ⊕ D4 0 ⊕ 1 ⊕ 0 ⊕ 1 0計(jì)算0⊕11, 1⊕01, 1⊕10 得到校驗(yàn)子S3 S2 S1 000。二進(jìn)制000對(duì)應(yīng)十進(jìn)制0。海明碼規(guī)定校驗(yàn)子為0表示沒(méi)有檢測(cè)到錯(cuò)誤。數(shù)據(jù)正確。場(chǎng)景B發(fā)生一位錯(cuò)誤例如位置5的D2從1翻轉(zhuǎn)為0接收方收到1 0 1 0 0 0 1。注意位置5的數(shù)據(jù)變成了0。 重新計(jì)算校驗(yàn)子S1 P1 ⊕ D1 ⊕ D2 ⊕ D4 1 ⊕ 1 ⊕ 0 ⊕ 1 1計(jì)算1⊕10, 0⊕00, 0⊕11S2 P2 ⊕ D1 ⊕ D3 ⊕ D4 0 ⊕ 1 ⊕ 0 ⊕ 1 0計(jì)算0⊕11, 1⊕01, 1⊕10S3 P3 ⊕ D2 ⊕ D3 ⊕ D4 0 ⊕ 0 ⊕ 0 ⊕ 1 1計(jì)算0⊕00, 0⊕00, 0⊕11 得到校驗(yàn)子S3 S2 S1 101。二進(jìn)制101對(duì)應(yīng)十進(jìn)制5。神奇的事情發(fā)生了校驗(yàn)子101十進(jìn)制5直接指出了出錯(cuò)的位置是第5位這是因?yàn)槲覀兊姆纸M規(guī)則確保了每一個(gè)位置出錯(cuò)都會(huì)產(chǎn)生一個(gè)獨(dú)一無(wú)二的校驗(yàn)子組合。接收方只需要將第5位的比特取反0變成1就完成了糾錯(cuò)恢復(fù)了原始數(shù)據(jù)。場(chǎng)景C發(fā)生兩位錯(cuò)誤例如位置3和位置6同時(shí)出錯(cuò)接收方收到1 0 0 0 1 1 1。位置3的D1從1變0位置6的D3從0變1 重新計(jì)算校驗(yàn)子S1 P1 ⊕ D1 ⊕ D2 ⊕ D4 1 ⊕ 0 ⊕ 1 ⊕ 1 11⊕01, 1⊕10, 0⊕11S2 P2 ⊕ D1 ⊕ D3 ⊕ D4 0 ⊕ 0 ⊕ 1 ⊕ 1 00⊕00, 0⊕11, 1⊕10S3 P3 ⊕ D2 ⊕ D3 ⊕ D4 0 ⊕ 1 ⊕ 1 ⊕ 1 10⊕11, 1⊕10, 0⊕11 得到校驗(yàn)子S3 S2 S1 101。二進(jìn)制101對(duì)應(yīng)十進(jìn)制5。問(wèn)題來(lái)了校驗(yàn)子結(jié)果是101和場(chǎng)景B一樣接收方會(huì)誤以為只有第5位出錯(cuò)了從而去翻轉(zhuǎn)第5位。這會(huì)導(dǎo)致“糾錯(cuò)”后引入新的錯(cuò)誤因?yàn)閷?shí)際上第5位原本是正確的。但是接收方在糾錯(cuò)前會(huì)發(fā)現(xiàn)一個(gè)關(guān)鍵現(xiàn)象校驗(yàn)子非零101≠000但按照一位錯(cuò)誤糾錯(cuò)后新的碼字可能仍然不滿(mǎn)足校驗(yàn)規(guī)則或者通過(guò)其他方式如更高層的協(xié)議發(fā)現(xiàn)數(shù)據(jù)依然不合理。更重要的是標(biāo)準(zhǔn)(7,4)海明碼本身不具備區(qū)分“一位錯(cuò)”和“兩位錯(cuò)”的能力它只能檢測(cè)到“有錯(cuò)誤”并且當(dāng)錯(cuò)誤位數(shù)大于1時(shí)其糾錯(cuò)行為是不可靠的。這就是“檢二”的含義當(dāng)發(fā)生兩位錯(cuò)誤時(shí)校驗(yàn)子幾乎不可能為0除非極特殊的錯(cuò)誤模式因此系統(tǒng)能檢測(cè)到“發(fā)生了錯(cuò)誤”。但它給出的錯(cuò)誤位置校驗(yàn)子數(shù)值是誤導(dǎo)性的如果按照一位錯(cuò)去糾反而會(huì)錯(cuò)上加錯(cuò)。所以在實(shí)際系統(tǒng)中當(dāng)海明碼校驗(yàn)失敗校驗(yàn)子非零時(shí)如果系統(tǒng)設(shè)計(jì)為“糾一檢二”模式它會(huì)先嘗試按一位錯(cuò)誤糾正。如果糾正后的數(shù)據(jù)通過(guò)了其他完整性檢查如循環(huán)冗余校驗(yàn)CRC或應(yīng)用層校驗(yàn)則認(rèn)為成功如果仍然失敗則向上層報(bào)告“檢測(cè)到不可糾正的錯(cuò)誤”即可能發(fā)生了兩位或更多錯(cuò)誤。注意事項(xiàng)校驗(yàn)子的解讀校驗(yàn)子S3S2S1是一個(gè)二進(jìn)制數(shù)其數(shù)值直接對(duì)應(yīng)出錯(cuò)比特的位置編號(hào)。這是海明碼最核心的特性也是它能“定位”錯(cuò)誤的基礎(chǔ)。一定要記住這個(gè)編號(hào)是從1開(kāi)始的最終碼字位置不是數(shù)據(jù)位的原始順序。4. 擴(kuò)展到“糾一檢二”的增強(qiáng)型海明碼標(biāo)準(zhǔn)的(7,4)海明碼最小漢明距離是3。漢明距離是指兩個(gè)等長(zhǎng)碼字之間不同比特的個(gè)數(shù)。最小漢明距離為3意味著要檢測(cè)e個(gè)錯(cuò)誤需要d_min e 1。3 21所以能檢測(cè)2位錯(cuò)誤。要糾正t個(gè)錯(cuò)誤需要d_min 2t 1。3 2*11所以能糾正1位錯(cuò)誤。但這只是理論能力。如我們剛才所見(jiàn)標(biāo)準(zhǔn)海明碼在發(fā)生兩位錯(cuò)誤時(shí)雖然能檢測(cè)到異常校驗(yàn)子非零但無(wú)法區(qū)分它是一位錯(cuò)還是兩位錯(cuò)直接糾錯(cuò)可能會(huì)失敗。為了實(shí)現(xiàn)更可靠的“糾一檢二”通常需要一個(gè)額外的、覆蓋全體的校驗(yàn)位即總體奇偶校驗(yàn)位。4.1 增加一位總體奇偶校驗(yàn)位P0我們?cè)谠械?7,4)海明碼基礎(chǔ)上在最高位或最前面增加一位校驗(yàn)位P0。P0對(duì)整個(gè)7位海明碼字進(jìn)行偶校驗(yàn)。這樣就形成了一個(gè)(8,4)碼也稱(chēng)為擴(kuò)展海明碼或SEC-DED碼Single Error Correction, Double Error Detection單錯(cuò)糾正雙錯(cuò)檢測(cè)。編碼過(guò)程先用之前的方法計(jì)算出7位海明碼C 1010101。計(jì)算這7位碼字中1的個(gè)數(shù)。1010101中有4個(gè)1偶數(shù)。為了使得包括P0在內(nèi)的所有8位中1的個(gè)數(shù)為偶數(shù)偶校驗(yàn)P0應(yīng)設(shè)為0因?yàn)?已經(jīng)是偶數(shù)。最終發(fā)送的擴(kuò)展海明碼為P0 C 0 1010101。4.2 增強(qiáng)的檢錯(cuò)糾錯(cuò)邏輯接收方收到8位碼字后進(jìn)行兩級(jí)校驗(yàn)計(jì)算總體奇偶校驗(yàn)P0相關(guān)檢查整個(gè)8位碼字中1的個(gè)數(shù)是否為偶數(shù)。計(jì)算原有的海明校驗(yàn)子S3S2S1用收到的7位海明碼部分后7位重新計(jì)算。解碼決策邏輯如下表所示總體奇偶校驗(yàn)結(jié)果海明校驗(yàn)子 (S3S2S1)結(jié)論與操作正確偶000無(wú)錯(cuò)誤。數(shù)據(jù)直接接受。正確偶非零檢測(cè)到雙位錯(cuò)誤或不可糾正錯(cuò)誤。海明校驗(yàn)子指示了一個(gè)位置但總體校驗(yàn)正確這不符合單一位錯(cuò)誤的特征一位錯(cuò)會(huì)導(dǎo)致總體校驗(yàn)出錯(cuò)。因此系統(tǒng)可以斷定發(fā)生了兩位錯(cuò)誤。請(qǐng)求重傳或報(bào)告錯(cuò)誤。錯(cuò)誤奇非零檢測(cè)到單位錯(cuò)誤。并且海明校驗(yàn)子指示了錯(cuò)誤的具體位置假設(shè)為X。接收方翻轉(zhuǎn)第X位的值注意這里的X是針對(duì)后7位海明碼部分的位置總體位P0不參與海明校驗(yàn)計(jì)算。翻轉(zhuǎn)后錯(cuò)誤被糾正。錯(cuò)誤奇000總體校驗(yàn)位P0自身發(fā)生錯(cuò)誤。因?yàn)楹Ｃ餍ｒ?yàn)子顯示內(nèi)部7位無(wú)誤但總體校驗(yàn)不對(duì)那么錯(cuò)誤只可能發(fā)生在新增的P0位上。此時(shí)數(shù)據(jù)本身是正確的可以忽略P0錯(cuò)誤直接接受后7位解碼出的數(shù)據(jù)。通過(guò)增加一位我們實(shí)現(xiàn)了明確的“糾一檢二”當(dāng)海明校驗(yàn)子非零且總體校驗(yàn)出錯(cuò)一定是一位錯(cuò)可定位并糾正。當(dāng)海明校驗(yàn)子非零但總體校驗(yàn)正確一定是兩位或偶數(shù)位錯(cuò)可檢測(cè)但不可糾正。當(dāng)海明校驗(yàn)子為零但總體校驗(yàn)出錯(cuò)只是新增的校驗(yàn)位P0錯(cuò)了數(shù)據(jù)無(wú)誤。這種SEC-DED碼被廣泛應(yīng)用于對(duì)可靠性要求極高的場(chǎng)合如服務(wù)器ECC內(nèi)存。ECC內(nèi)存就能糾正每個(gè)字通常是64位中任意一個(gè)比特的錯(cuò)誤并檢測(cè)兩個(gè)比特的錯(cuò)誤極大降低了因內(nèi)存軟錯(cuò)誤導(dǎo)致系統(tǒng)崩潰的概率。實(shí)操心得理解“距離”給標(biāo)準(zhǔn)海明碼加一位總體校驗(yàn)本質(zhì)上是將其最小漢明距離從3提升到了4。因?yàn)樾略龅腜0使得任何兩個(gè)有效碼字之間不僅后7位至少差3位現(xiàn)在連P0也可能不同總差異至少為4。距離為4根據(jù)公式d_min 2t s 1(t為糾錯(cuò)位數(shù)s為檢錯(cuò)位數(shù)且st)當(dāng)t1時(shí)可得s2。這就是它能“糾一檢二”的數(shù)學(xué)根源。理解這一點(diǎn)就能舉一反三知道如何設(shè)計(jì)其他能力的編碼。5. 常見(jiàn)問(wèn)題、應(yīng)用場(chǎng)景與實(shí)操陷阱5.1 海明碼計(jì)算中的常見(jiàn)錯(cuò)誤位置編號(hào)混亂這是新手最常犯的錯(cuò)。務(wù)必記住所有計(jì)算分組、校驗(yàn)子定位都是基于最終碼字的絕對(duì)位置編號(hào)從1開(kāi)始而不是數(shù)據(jù)位的原始順序。建議畫(huà)一個(gè)位置表格標(biāo)好1,2,3,4,5,6,7再把P1,P2,P3,D1,D2,D3,D4填進(jìn)去一目了然。校驗(yàn)方程遺漏校驗(yàn)位本身計(jì)算P1時(shí)方程是P1 ⊕ D1 ⊕ D2 ⊕ D4 0P1自己也參與運(yùn)算。很多人會(huì)忘記把待求的P1放進(jìn)方程導(dǎo)致計(jì)算錯(cuò)誤。記住偶校驗(yàn)是針對(duì)“該組所有位包括校驗(yàn)位本身”。校驗(yàn)子順序顛倒接收方計(jì)算校驗(yàn)子時(shí)順序是S3 S2 S1對(duì)應(yīng)P3, P2, P1。這個(gè)順序不能反因?yàn)樗侵苯訉?duì)應(yīng)位置編號(hào)的二進(jìn)制表示S3是最高位。如果弄反定位就會(huì)完全錯(cuò)誤。奇校驗(yàn)與偶校驗(yàn)混淆理論上奇校驗(yàn)和偶校驗(yàn)都可以但必須約定一致。通常教材和實(shí)際應(yīng)用如ECC多用偶校驗(yàn)。如果題目或協(xié)議規(guī)定用奇校驗(yàn)?zāi)敲此行ｒ?yàn)方程的結(jié)果目標(biāo)就是1而不是0。5.2 海明碼在實(shí)際中的應(yīng)用場(chǎng)景海明碼及其變種如擴(kuò)展海明碼SEC-DED是底層數(shù)據(jù)可靠性的重要保障。ECC內(nèi)存如前所述這是海明碼最廣為人知的應(yīng)用。在服務(wù)器和工作站中ECC內(nèi)存能自動(dòng)糾正單比特錯(cuò)誤檢測(cè)雙比特錯(cuò)誤防止因宇宙射線(xiàn)等引起的軟錯(cuò)誤導(dǎo)致數(shù)據(jù)損壞或系統(tǒng)宕機(jī)。高速串行通信在一些高速接口協(xié)議如PCIe、SATA的底層鏈路層會(huì)使用前向糾錯(cuò)編碼海明碼是其中一種基礎(chǔ)構(gòu)件用于保護(hù)關(guān)鍵的控制信息和元數(shù)據(jù)。閃存存儲(chǔ)NAND Flash存儲(chǔ)器存在比特翻轉(zhuǎn)的可能。在一些SSD的控制器中會(huì)對(duì)小顆粒的數(shù)據(jù)如1KB扇區(qū)內(nèi)的元數(shù)據(jù)使用海明碼進(jìn)行保護(hù)作為第一道糾錯(cuò)防線(xiàn)更復(fù)雜的錯(cuò)誤則由LDPC等強(qiáng)糾錯(cuò)碼處理。網(wǎng)絡(luò)設(shè)備與通信在一些對(duì)延遲極其敏感、無(wú)法重傳的實(shí)時(shí)通信中如某些工業(yè)總線(xiàn)、航空電子會(huì)采用海明碼進(jìn)行即時(shí)糾錯(cuò)。二維碼與條形碼一些二維碼的糾錯(cuò)等級(jí)中也采用了里德-所羅門(mén)碼等其思想與海明碼同屬糾錯(cuò)編碼范疇但更復(fù)雜。5.3 海明碼的局限性理解一個(gè)技術(shù)的邊界和它的能力同樣重要。開(kāi)銷(xiāo)固定校驗(yàn)位數(shù)量隨數(shù)據(jù)位對(duì)數(shù)增長(zhǎng)對(duì)于極長(zhǎng)的數(shù)據(jù)塊如1KB使用海明碼開(kāi)銷(xiāo)相對(duì)較大需要約10位校驗(yàn)位保護(hù)1KB不實(shí)際上需要更多因?yàn)?^101024只能保護(hù)大約1014個(gè)數(shù)據(jù)位效率約99%。對(duì)于大數(shù)據(jù)塊通常采用循環(huán)冗余校驗(yàn)CRC檢錯(cuò)重傳或使用里德-所羅門(mén)碼、LDPC碼等更高效的糾錯(cuò)碼。只能處理隨機(jī)位錯(cuò)誤海明碼對(duì)突發(fā)錯(cuò)誤一連串比特連續(xù)出錯(cuò)的抵抗能力很弱。一個(gè)長(zhǎng)度為b的突發(fā)錯(cuò)誤最多可能影響b個(gè)校驗(yàn)位很容易超出其糾檢錯(cuò)能力。對(duì)抗突發(fā)錯(cuò)誤需要采用交織等技術(shù)。無(wú)法糾正多位錯(cuò)標(biāo)準(zhǔn)版只能糾一位。擴(kuò)展版SEC-DED能檢兩位但無(wú)法糾正。對(duì)于需要糾正多位錯(cuò)誤的場(chǎng)景必須使用更強(qiáng)大的編碼。5.4 從海明碼到更高級(jí)的糾錯(cuò)碼學(xué)習(xí)海明碼是進(jìn)入糾錯(cuò)編碼世界的大門(mén)。它展示了如何通過(guò)增加冗余來(lái)實(shí)現(xiàn)可靠性。在此基礎(chǔ)上你可以進(jìn)一步探索循環(huán)冗余校驗(yàn)CRC強(qiáng)大的檢錯(cuò)碼計(jì)算簡(jiǎn)單廣泛用于網(wǎng)絡(luò)幀、存儲(chǔ)數(shù)據(jù)塊的錯(cuò)誤檢測(cè)。它不能糾錯(cuò)但檢錯(cuò)能力極強(qiáng)。里德-所羅門(mén)碼不僅能糾隨機(jī)錯(cuò)誤還能糾突發(fā)錯(cuò)誤。廣泛應(yīng)用于光盤(pán)CD/DVD、二維碼、衛(wèi)星通信、RAID 6存儲(chǔ)系統(tǒng)。低密度奇偶校驗(yàn)碼LDPC和Turbo碼現(xiàn)代通信系統(tǒng)的基石如5G、Wi-Fi、深空通信性能接近香農(nóng)極限可以實(shí)現(xiàn)極高的編碼增益在極低的信噪比下可靠通信。理解海明碼的“分組奇偶校驗(yàn)”和“交叉覆蓋”思想對(duì)你理解這些更復(fù)雜的編碼會(huì)大有裨益。它教會(huì)你的是一種用結(jié)構(gòu)和冗余來(lái)對(duì)抗噪聲的思維方式。下次當(dāng)你看到服務(wù)器配置單上的“ECC內(nèi)存”或者聽(tīng)到“前向糾錯(cuò)”這個(gè)詞時(shí)希望你能會(huì)心一笑知道那里面正運(yùn)行著由理查德·海明在1940年代提出的精妙思想。