3.5　檢錯(cuò)和糾錯(cuò)

你永遠(yuǎn)不知道什么時(shí)候就有一束迷路的宇宙射線擊中一塊內(nèi)存并破壞數(shù)據(jù)。如果能知道這種事情發(fā)生的時(shí)間而且還能修復(fù)損壞就好了。當(dāng)然，這樣的改進(jìn)是需要耗費(fèi)金錢的，而且在消費(fèi)級(jí)設(shè)備中并不常見。

我們希望在不需要存儲(chǔ)完整的第二份數(shù)據(jù)的情況下，檢測(cè)出錯(cuò)誤。但無論如何，這都行不通。因?yàn)槲覀儾恢滥膫€(gè)副本是正確的。我們可以存儲(chǔ)兩個(gè)額外的副本，并假設(shè)匹配對(duì)（如果有的話）是正確的。那些本就是為惡劣環(huán)境設(shè)計(jì)的計(jì)算機(jī)可以做到這一點(diǎn)，這些計(jì)算機(jī)中還使用了更昂貴的電路設(shè)計(jì)，確保被質(zhì)子擊中時(shí)不會(huì)使電路燒毀。例如，航天飛機(jī)有冗余的計(jì)算機(jī)和在檢測(cè)到錯(cuò)誤時(shí)發(fā)揮作用的表決系統(tǒng)。

我們可以用一種叫作奇偶校驗(yàn)的方法來測(cè)試1位錯(cuò)誤。其思想是將設(shè)置為1的位數(shù)相加，并使用額外的位來存儲(chǔ)相加結(jié)果是奇數(shù)還是偶數(shù)。我們可以通過取位的XOR來實(shí)現(xiàn)這一點(diǎn)。有兩種取位的形式：在偶校驗(yàn)中使用位和，在奇校驗(yàn)中使用位和的補(bǔ)碼。這個(gè)選擇可能看起來很奇怪，但這個(gè)術(shù)語來自1或0的數(shù)目，包括奇偶校驗(yàn)位。

圖3-31的左半部分展示了偶校驗(yàn)的計(jì)算過程，存在4個(gè)1，因此奇偶校驗(yàn)位為0。右半部分同樣展示了奇偶校驗(yàn)的檢查，輸出0表示數(shù)據(jù)是正確的，或者至少用奇偶校驗(yàn)判斷是正確的。奇偶校驗(yàn)的一個(gè)大問題是，如果有兩個(gè)位錯(cuò)誤，則看起來像是正確的，它只能捕捉奇數(shù)個(gè)錯(cuò)誤。

圖3-31　奇偶校驗(yàn)

還有更為復(fù)雜的方法，如美國(guó)數(shù)學(xué)家Richard Hamming（1915—1998）發(fā)明的漢明碼。漢明碼需要占用更多的位，允許檢測(cè)更多的錯(cuò)誤，并允許糾正一些錯(cuò)誤。包括漢明碼這一電路的檢錯(cuò)和糾錯(cuò)（Error Checking and Correcting, ECC）存儲(chǔ)芯片是可用的。ECC存儲(chǔ)芯片通常用于大數(shù)據(jù)中心，甚少用于消費(fèi)級(jí)設(shè)備。

像奇偶校驗(yàn)這樣的方法適合不斷變化的數(shù)據(jù)。也有一些成本較低的方法可以驗(yàn)證靜態(tài)塊數(shù)據(jù)，例如計(jì)算機(jī)程序。其中最簡(jiǎn)單的是校驗(yàn)和，即將每個(gè)數(shù)據(jù)位置的內(nèi)容累加為某個(gè)n位的值，并丟棄溢出位。通常在程序運(yùn)行之前，可以將校驗(yàn)和與程序進(jìn)行比較。校驗(yàn)和值越大（即n越大），得到假陽性的概率越低。

循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check, CRC）在數(shù)學(xué)上是校驗(yàn)和的一個(gè)更好的替代。哈希碼也是校檢和很好的替代。循環(huán)冗余校檢的目標(biāo)是計(jì)算出一個(gè)對(duì)數(shù)據(jù)來說足夠唯一的驗(yàn)證數(shù)字，這樣對(duì)于大多數(shù)的更改，驗(yàn)證數(shù)字將不再正確。