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

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

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

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


圖2.1 糾錯(cuò)碼的分類