檢錯糾錯的有關(guān)概念和實(shí)現思路

數據在計算機系統內加工、存取和傳送的過(guò)程中可能產(chǎn)生錯誤。為減少和避免這類(lèi)錯誤，一方面是精心選擇各種電路，改進(jìn)生產(chǎn)工藝與測試手段，盡量提高計算機硬件本身的可靠性；另一方面是在數據編碼上找出路，即采用帶有某種特征能力的編碼方法，通過(guò)少量的附加電路，使之能發(fā)現某些錯誤,甚至能準確地確定出錯位置,進(jìn)而提供自動(dòng)糾正錯誤的能力。

　　數據校驗碼就是一種常用的帶有發(fā)現某些錯誤、甚至帶有一定自動(dòng)改錯能力的數據編碼方法。它的實(shí)現原理，是在合法的數據編碼之間，加進(jìn)一些不允許出現的(非法的)編碼，使合法數據編碼出現某些錯誤時(shí)，就成為非法編碼。這樣,則可以通過(guò)檢查編碼的合法性來(lái)達到發(fā)現錯誤的目的。合理地設計編碼規則，安排合法、不合法的編碼數量，就可以得到發(fā)現錯誤的能力，甚至達到自動(dòng)改正錯誤的目的。這里用到一個(gè)碼距（最小碼距）的概念。碼距是指任意兩個(gè)合法碼之間至少有幾個(gè)二進(jìn)制位不相同，僅有一位不同，稱(chēng)其（最小碼距）為1，例如用四位二進(jìn)制表示16種狀態(tài)，則16種編碼都用到了，此時(shí)碼距為1，就是說(shuō)，任何一個(gè)編碼狀態(tài)的四位碼中的一位或幾位出錯，都會(huì )變成另一個(gè)合法碼，此時(shí)無(wú)檢錯能力。若用四個(gè)二進(jìn)制位表示8種合法狀態(tài)，就可以只用其中的8個(gè)編碼來(lái)表示之，而把另8種編碼作為非法編碼，此時(shí)可使合法碼的碼距為2。一般說(shuō)來(lái)，合理地增大編碼的碼距,就能提高發(fā)現錯誤的能力，但表示一定數量的合法碼所使用的二進(jìn)制位數要變多，增加了電子線(xiàn)路的復雜性和數據存儲、數據傳送的數量。在確定與使用數據校驗碼的時(shí)候，通常要考慮在不過(guò)多增加硬件開(kāi)銷(xiāo)的情況下，盡可能地發(fā)現較多的錯誤，甚至能自動(dòng)改正某些最常出現的錯誤。常用的數據校驗碼是奇偶校驗碼、海明校驗碼、循環(huán)冗余校驗碼等。糾錯編碼是對檢錯編碼的更進(jìn)一步的發(fā)展和應用。

　　計算機內經(jīng)常遇到的錯誤有兩大類(lèi)，隨機錯誤和突發(fā)錯誤。前者指孤立出現的一個(gè)錯誤，后者指連續產(chǎn)生的一批（彼此之間可能有關(guān)聯(lián)）錯誤。對它們處理的難度和復雜度會(huì )有很大不同，在我們的課程中基本不涉及對突發(fā)錯誤的檢查與糾正問(wèn)題，有興趣者請自行查閱有關(guān)資料。對糾錯編碼的分類(lèi)方案給在圖2.1。


圖2.1 糾錯碼的分類(lèi)