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

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

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

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


圖2.1 糾錯碼的分類