檢錯糾錯的有關概念和實現思路

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

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

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


圖2.1 糾錯碼的分類