糾錯算法（Error correction algorithm）是建立在機率統計的基礎上的：出現2個差錯的機率遠小於出現1個差錯的機率，而出現3個差錯的機率又遠小於出現2個差錯的機率。從而有理由認為：當接收到的代碼是一個非法的代碼時，它的正確代碼應該是在邏輯空間中離它最近的有效代碼。
基本介紹
- 中文名：糾錯算法
- 外文名：Error correction algorithm
- 定 義：糾正有效編碼的差錯
- 套用學科：計算機原理術語
概念,工作原理,漢明碼,檢二糾一碼,
概念
糾錯算法（Error correction algorithm）是建立在機率統計的基礎上的：出現2個差錯的機率遠小於出現1個差錯的機率，而出現3個差錯的機率又遠小於出現2個差錯的機率。從而有理由認為：當接收到的代碼是一個非法的代碼時，它的正確代碼應該是在邏輯空間中離它最近的有效代碼。
各有效編碼之間的間距必須等於2才能具有檢出一個差錯的能力，這時如果發生兩個差錯，就會將一個有效編碼變成另一個有效編碼，從而造成不能發現的差錯。如果將有效編碼之間的最小碼距加大為3，在發生一個差錯時形成的代碼離各有效代碼的距離就不相等，我們就可以將這個出錯的代碼按離得最近的有效代碼來看待，從而具有糾正一個差錯的能力。
工作原理
漢明碼
如果某種編碼的合法代碼之間的最小碼距為1（所有的順序編碼都是如此），顯然沒有檢錯能力，更沒有糾錯能力。要想使得其具有糾錯能力，必須進行改造，或者按某種糾錯碼格式重新編碼，或者在原編碼的基礎上附加一部分代碼，使其滿足糾錯碼的條件。後一種方法比較方便，只是在傳送時臨時附加一部分代碼，接收端利用它進行糾錯處理後就捨棄，使原代碼部分維持不變，漢明碼就是這一類型的糾錯碼。
檢二糾一碼
包含4位有效信息的漢明碼只能發現並糾正一個差錯，如果出現兩個差錯，就會被它強行“糾正”成另外一個合法代碼，造成不被發現的錯誤。例如發方將十六進制數6按7位漢明碼66H發出，在接收過程中如果出現兩個差錯而變成60H，經糾錯處理使得到68H，還原後就成為十六進制數8，這就產生了錯誤。能否進一步提高編碼的性能，使它在出現兩個差錯時能夠及時發現而不亂加糾正呢？根據檢錯理論，只要將有效編碼之前的最小碼距加大到4就可以達到這個目的，這就是“檢二糾一碼”。
7位漢明碼在實際使用中是用1位元組來表示的，如果把浪費了的1位也利用起來，無疑會進一步提供抗干擾性能。
要想在不加大碼距的前提下，糾正連續多位差錯，提供抵抗突發乾擾的能力，方法就是將編碼後的漢明碼重新進行組織排列。以16位的漢明碼為例，把11位元組的數據編碼為16位元組的漢明碼後再按高低位元組分成兩組。把每組位元組8個漢明碼的第1位分別取出，組成1位元組；然後再把這8位元組嗎的第2位取出，組成第2位元組；依此類推，將這組8位元組漢明碼處理完畢，得到新的8位元組編碼。只要在糾錯前把受干擾的編碼恢復原來正常的排列順序，就可通過計算校驗碼完成差錯的定位及糾錯。
