檢錯與糾錯、奇偶校驗碼與海明校驗碼

計算機基礎--檢錯與糾錯碼1

• 檢錯與糾錯的原由
• • 奇偶校驗碼
  • 1、水準奇校驗
  • 2、水準偶校驗
  • 3、不足和改進
• 海明校驗碼
• • 1、編碼糾錯理論--編碼最小距離（碼距）
  • 2、檢錯
  • 3、糾錯
  • 4、不足

檢錯與糾錯的原由

元件故障、噪聲幹擾等因素常常導緻計算機在傳輸、存儲或處理的過程中出現錯誤，故采用專門的邏輯電路對信号進行編碼有便于檢測錯誤甚至校驗錯誤。本文介紹奇偶檢驗碼和海明碼。

奇偶校驗碼

這是一種最簡單且應用最廣泛的檢錯碼，用的是以為校驗位的奇偶校驗。分成水準奇校驗和水準偶校驗。

1、水準奇校驗

設資料X是一個n位字，在其高位前增加1位奇校驗位，保證資料（包括奇校驗位在内）的n+1位中，1的個數為奇數，這也就是奇校驗稱呼的由來。

例：

有X = 0100010，采用水準奇校驗時，由于X本身的1的個數是2個，是以在高位前添加1使得X的1的個數是奇數個，即X變成10100010.

2、水準偶校驗

與奇校驗類似，水準偶校驗在資料的高位前添加一位校驗位使得此資料各位上1的個數為偶數。當傳輸到對方的時候可以通過對傳過來的資料X進行檢測，如果沒有出現問題則可認為在傳輸或者存儲的過程中沒有發生1位錯誤。

例：

有X = 0100010，采用水準奇校驗時，由于X本身的1的個數是2個，是以在高位前添加0使得X的1的個數是偶數個，即X變成00100010.當傳輸到對方的時候可以通過對傳過來的資料X進行檢測，如果沒有出現問題則可認為在傳輸或者存儲的過程中沒有發生1位錯誤。

3、不足和改進

對于出現一位錯誤的情況，奇偶校驗可以檢測出錯誤但卻不能檢測出錯誤的準确位置，同時，當資料出現兩位同時出現錯誤會導緻檢錯碼失去作用，但由于實作起來非常簡單容易由此得到了廣泛的應用。對于上述提到的兩個問題，偉大的先人（是不是說老了，其實很多人還挺年輕的）在上面兩個校驗碼的基礎之上相繼發明了垂直奇偶校驗碼和水準垂直檢驗碼（在這我就不多說了）。

海明校驗碼

為了針對更複雜更龐大的資料能及時檢錯和糾錯，通常将原資料配成海明編碼。

1、編碼糾錯理論–編碼最小距離（碼距）

指在一種編碼系統中任意兩組合法代碼之間的最少二進制位數的差異。

根據糾錯理論：

L - 1 = D + C 且 D >= C

即編碼最小距離L越大，則其檢測錯誤的位數D越大，糾正錯誤的位數C也越大，且糾錯能力恒小于或等于檢錯能力。如當編碼最小距離L=3時，最多能檢錯兩位，或能檢錯一位、糾錯一位。海明碼就是根據這一理論提出的具有一位糾錯能力的編碼。

2、檢錯

為了使檢測的二進制代碼具有糾錯能力，需添加位檢測位，添加的檢測位的位數k有下面的公式得到：、

2^k > = n + k + 1

插入的位置分别是2的0次方，2的1次方，2的2次方以此類推，各位添加的檢測碼的值由在二進制數位置數有含有檢測碼的所有位置上的數進行模二加得到。

例：

X = 10101

通過上面的公式可以得到k=4，故要插入4位檢測碼，将每位檢測碼稱為Pi，每位資料碼稱為Di，則有：

P1 = D1 + D2 + D4 + D5 = 1

P2 = D1 + D3 + D4 = 1

P3 = D2 + D3 + D4 = 1

P4 = D5 = 1

故添加的檢測碼是1111，是以最後傳輸的資料是11101011。

3、糾錯

當接收方接收到資料以後，首先提取出檢測碼1111，然後求出指錯字，設指錯字為Gi，通過下列計算出指錯字Gi：

G1 = P1 + D1 + D2 + D4 + D5 = 0

G2 = P2 + D1 + D3 + D4 = 0

D3 = P3 + D2 + D3 + D4 = 0

D4 = P4 + D5 = 0

上面求出的指錯字是無資料出錯的狀态下的，當有資料出錯時指錯字的大小就是出錯資料位的位置。

4、不足

海明碼優點多多（當初學習的時候感覺發明這種檢錯碼的人簡直是天才！！！），但當檢測出錯誤并得到錯誤資料位位置後的實際糾錯的方式并沒有太過先進的地方（雖然已經很好了），同時也隻能檢測并糾錯一位資料位錯誤。

這是我的人生中的第一篇部落格，打算記錄下自己在學習計算機組成原理中感覺比較有意思的知識，大家以後多多關照(≧▽≦)/啦！