奇偶校驗、海明碼、CRC循環(huán)冗余校驗碼
三種校驗碼比較重要，需要牢記，在計算機(jī)網(wǎng)絡(luò)中用處較大
奇偶校驗
根據(jù)被傳輸?shù)囊唤M二進(jìn)制代碼的數(shù)位中“1”的個數(shù)是奇數(shù)或偶數(shù)來進(jìn)行校驗。采用奇數(shù)的稱為奇校驗，反之，稱為偶校驗。采用何種校驗是事先規(guī)定好的。通常專門設(shè)置一個奇偶校驗位，用它使這組代碼中“1”的個數(shù)為奇數(shù)或偶數(shù)。若用奇校驗，則當(dāng)接收端收到這組代碼時，校驗“1”的個數(shù)是否為奇數(shù)，從而確定傳輸代碼的正確性。
校驗方法
奇校驗：就是讓原有數(shù)據(jù)序列中（包括你要加上的一位）1的個數(shù)為奇數(shù)
1000110（0）你必須添0這樣原來有3個1已經(jīng)是奇數(shù)了所以你添上0之后1的個數(shù)還是奇數(shù)個。
偶校驗：就是讓原有數(shù)據(jù)序列中（包括你要加上的一位）1的個數(shù)為偶數(shù)
1000110（1）你就必須加1了這樣原來有3個1要想1的個數(shù)為偶數(shù)就只能添1了
范例
串行數(shù)據(jù)在傳輸過程中，由于干擾可能引起信息的出錯，例如，傳輸字符‘E’，其各位為：
0100，0101=45H
D7 D0
由于干擾，可能使位變?yōu)?，（為什么不變0？）這種情況，我們稱為出現(xiàn)了“誤碼”。我們把如何發(fā)現(xiàn)傳輸中的錯誤，叫“檢錯”。發(fā)現(xiàn)錯誤后，如何消除錯誤，叫“糾錯”。最簡單的檢錯方法是“奇偶校驗”，即在傳送字符的各位之外，再傳送1位奇/偶校驗位?？刹捎闷嫘ｒ灮蚺夹ｒ灐?br>
奇校驗：所有傳送的數(shù)位（含字符的各數(shù)位和校驗位）中，“1”的個數(shù)為奇數(shù)，如：
1 0110，0101
0 0110，0101
偶校驗：所有傳送的數(shù)位（含字符的各數(shù)位和校驗位）中，“1”的個數(shù)為偶數(shù)，如：
1 0100，0101
0 0100，0101
奇偶校驗?zāi)軌驒z測出信息傳輸過程中的部分誤碼（奇數(shù)位誤碼能檢出，偶數(shù)位誤碼不能檢出），同時，它不能糾錯。在發(fā)現(xiàn)錯誤后，只能要求重發(fā)。但由于其實現(xiàn)簡單，仍得到了廣泛使用。有些檢錯方法，具有自動糾錯能力。如循環(huán)冗余碼（CRC）檢錯等
CRC校驗
CRC即循環(huán)冗余校驗碼（Cyclic Redundancy Check）：是數(shù)據(jù)通信領(lǐng)域中最常用的一種查錯校驗碼，其特征是信息字段和校驗字段的長度可以任意選定。循環(huán)冗余檢查（CRC）是一種數(shù)據(jù)傳輸檢錯功能，對數(shù)據(jù)進(jìn)行多項式計算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。
工作原理
循環(huán)冗余校驗碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼也叫（N，K）碼。對于一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據(jù)G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式。 校驗碼的具體生成過程為：假設(shè)要發(fā)送的信息用多項式C(X)表示，將C(x)左移R位（可表示成C(x)2R），這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。用 C(x)2R 除以生成多項式G(x)得到的余數(shù)就是校驗碼。
對應(yīng)關(guān)系
多項式和二進(jìn)制數(shù)有直接對應(yīng)關(guān)系：X的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位，以下各位對應(yīng)多項式的各冪次，有此冪次項對應(yīng)1，無此冪次項對應(yīng)0。可以看出：X的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R+1位。
多項式包括生成多項式G(X)和信息多項式C(X)。
如生成多項式為G(X)=X4+X3+X+1， 可轉(zhuǎn)換為二進(jìn)制數(shù)碼11011。
而發(fā)送信息位 101111，可轉(zhuǎn)換為數(shù)據(jù)多項式為C(X)=X5+X3+X2+X+1。
生成多項式
是接受方和發(fā)送方的一個約定，也就是一個二進(jìn)制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。
在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接收方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。
應(yīng)滿足以下條件：
A、生成多項式的最高位和最低位必須為1。
B、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做除后應(yīng)該使余數(shù)不為0。
C、不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。
D、對余數(shù)繼續(xù)做除，應(yīng)使余數(shù)循環(huán)。
校驗碼位數(shù)
CRC校驗碼位數(shù) = 生成多項式位數(shù) - 1。注意有些生成多項式的簡記式中將生成多項式的最高位1省略了。
生成步驟
1、將X的最高次冪為R的生成多項式G(X)轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)。
2、將信息碼左移R位，相當(dāng)于對應(yīng)的信息多項式C(X)*2R。
3、用生成多項式（二進(jìn)制數(shù)）對信息碼做除，得到R位的余數(shù)(注意：這里的二進(jìn)制做除法得到的余數(shù)其實是模2除法得到的余數(shù)，并不等于其對應(yīng)十進(jìn)制數(shù)做除法得到的余數(shù)。)。
4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。
【例】假設(shè)使用的生成多項式是G(X)=X3+X+1。4位的原始報文為1010，求編碼后的報文。
解：
1、將生成多項式G(X)=X3+X+1轉(zhuǎn)換成對應(yīng)的二進(jìn)制除數(shù)1011。
2、此題生成多項式有4位（R+1）(注意：4位的生成多項式計算所得的校驗碼為3位，R為校驗碼位數(shù))，要把原始報文C(X)左移3（R）位變成1010 000
3、用生成多項式對應(yīng)的二進(jìn)制數(shù)對左移3位后的原始報文進(jìn)行模2除（高位對齊），相當(dāng)于按位異或：
1010000
1011
———–】
0001000
0001011
———-】
0000011
得到的余位011，所以最終編碼為：1010 011
原則
若設(shè)碼字長度為N，信息字段為K位，校驗字段為R位(N=K+R)，則對于CRC碼集中的任一碼字，存在且僅存在一個R次多項式g(x)，使得
V(x)=A(x)g(x)=xRm(x)+r(x);
其中: m(x)為K次原始的信息多項式， r(x)為R-1次校驗多項式（即CRC校驗和），
g(x)稱為生成多項式：
g(x)=g0+g1x1+ g2x2+…+g(R-1)x(R-1)+gRxR
發(fā)送方通過指定的g(x)產(chǎn)生CRC碼字，接收方則通過該g(x)來驗證收到的CRC碼字。
生成方法
借助于模2除法則，其余數(shù)為校驗字段。
例如：信息字段代碼為: 1011001；對應(yīng)m(x)=x6+x4+x3+1
假設(shè)生成多項式為：g(x)=x4+x3+1；則對應(yīng)g(x)的代碼為: 11001
x4m(x)=x10+x8+x7+x4 對應(yīng)的代碼記為：10110010000；
采用模2除法則: 得余數(shù)為: 1010(即校驗字段為：1010）
發(fā)送方：發(fā)出的傳輸字段為: 1 0 1 1 0 0 1 1010
信息字段 校驗字段
接收方：使用相同的生成碼進(jìn)行校驗:接收到的字段/生成碼（二進(jìn)制除法）
如果能夠除盡，則正確，
給出余數(shù)（1010）的計算步驟：
除法沒有數(shù)學(xué)上的含義，而是采用計算機(jī)的模二除法，即除數(shù)和被除數(shù)做異或運(yùn)算。進(jìn)行異或運(yùn)算時除數(shù)和被除數(shù)最高位對齊，按位異或。
10110010000
^11001
————————–】
01111010000
1111010000
^11001
————————-】
0011110000
11110000
^11001
————————–】
00111000
111000
^11001
——————-】
001010
則四位CRC校驗碼就為：1010。
利用CRC進(jìn)行檢錯的過程可簡單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗，以確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”。
海明碼校驗
將有效信息按某種規(guī)律分成若干組，每組安排一個校驗位，做奇偶測試，就能提供多位檢錯信息，以指出最大可能是哪位出錯，從而將其糾正。實質(zhì)上，海明校驗是一種多重校驗。
假設(shè)為k個數(shù)據(jù)位設(shè)置r個校驗位，則校驗位能表示2^r個狀態(tài)，可用其中的一個狀態(tài)指出 “沒有發(fā)生錯誤”，用其余的2 ^r -1個狀態(tài)指出有錯誤發(fā)生在某一位，包括k個數(shù)據(jù)位和r個校驗位，因此校驗位的位數(shù)應(yīng)滿足如下關(guān)系:
2^r ≥ k + r + 1 (2.7)
如要能檢出與自動校正一位錯，并能同時發(fā)現(xiàn)哪位錯，此時校驗位的位數(shù)r和數(shù)據(jù)位的位數(shù)k應(yīng)滿足下述關(guān)系:
2^r-1 ≥ k + r (2.8)
按上述不等式，可計算出數(shù)據(jù)位k與校驗位r的對應(yīng)關(guān)系，如表2.2所示。
表2.2
k值 最小r值
2～4 3
5～11 4
12～26 5
27～57 6
58～120 7
分組原則
編輯
在海明碼中， 位號數(shù)（1、2、3、……、n）為2的權(quán)值的那些位，即：
1(20)、2(21)、4(22)、8(23)、…2^(r-1)位，作為奇偶校驗位，并記作: P1、P2、P3 、P4、…Pr，余下各位則為有效信息位。例如： N=11（海明碼位數(shù)）K=7（數(shù)據(jù)位數(shù)）r=4（校驗位） ，相應(yīng)海明碼可表示位號為： 1， 2， 3， 4 ，5 ，6， 7， 8， 9 ，10 ，11，校驗位P占第1，2，4，8位，其他位為有效信息位，海明碼中的校驗位分別標(biāo)示為P1,P2,P3,P4… Pr ,并被信息位中的一至若干位所校驗，其規(guī)律是：第i位，由校驗位位號之和等于i的那些校驗位所校驗，如：海明碼的位號為3，它被P1P2（位號分別為1,2）所校驗，海明碼的位號為5，它被P1P3（位號分別為1,4）所校驗。歸并起來: 形成了4個小組，每個小組一個校驗位，校驗位的取值，仍采用奇偶校驗方式確定。
設(shè)計海明碼編碼的關(guān)鍵技術(shù)，是合理地把每個數(shù)據(jù)位分配到r個校驗組中，以確保能發(fā)現(xiàn)碼字中任何一位出錯；若要實現(xiàn)糾錯，還要求能指出是哪一位出錯，對出錯位求反則得到該位的正確值。例如，當(dāng)數(shù)據(jù)位為3位（用D3 D2 D1表示）時，檢驗位應(yīng)為4位（用P4 P3 P2 P1表示）?？赏ㄟ^表2.3表示的關(guān)系，完成把每個數(shù)據(jù)位劃分在形成不同校驗位的偶校驗值的邏輯表達(dá)式中。
表2.3 校驗位與數(shù)據(jù)位的對應(yīng)關(guān)系
在P1、P2、P3、P4豎列相應(yīng)行分別填1，
在該4列的低3橫行其它位置分別填0，
在最頂橫行的每個尚空位置都分別填1。
若只看低3橫行，右4豎列的3個bit的組合值分別為十進(jìn)制的1、2、4、0，則分配 D1 D2 D3列的組合值為3 5 6，保證低3橫行各豎列的編碼值各不相同。
表中D3 D2 D1為三位數(shù)據(jù)位，P4 P3 P2 P1為四位校驗位。其中低三位中的每一個校驗位P3 P2 P1的值，都是用三個數(shù)據(jù)位中不同的幾位通過偶校驗運(yùn)算規(guī)則計算出來的。其對應(yīng)關(guān)系是：對Pi（i的取值為1~3），總是用處在Pi取值為1的行中的、用1標(biāo)記出來的數(shù)據(jù)位計算該P(yáng)i的值。最高一個校驗位P4，被稱為總校驗位，它的值，是通過對全部三個數(shù)據(jù)位和其它全部校驗位（不含P4本身）執(zhí)行偶校驗計算求得的。
形成各校驗位的值的過程叫做編碼，按剛說明的規(guī)則，4個校驗位所用的編碼方程為：
P4 = D3 D2 D1 P3 P2 P1
P3 = D3 D2
P2 = D3 D1
P1 = D2 D1
由多個數(shù)據(jù)位和多個校驗位組成的一個碼字，將作為一個數(shù)據(jù)單位處理，例如被寫入內(nèi)存或被傳送走。之后，在執(zhí)行內(nèi)存讀操作或在數(shù)據(jù)接收端，則可以對得到的碼字，通過偶校驗來檢查其合法性，通常稱該操作過程為譯碼，所用的譯碼方程為：
S4 = P4 D3 D2 D1 P3 P2 P1
S3 = P3 D3 D2
S2 = P2 D3 D1
S1 = P1 D2 D1
對應(yīng)關(guān)系
編輯
譯碼方程和編碼方程的對應(yīng)關(guān)系很簡單。譯碼方程，是用一個校驗碼和形成這個校驗碼的編碼方程執(zhí)行異或，實際上是又一次執(zhí)行偶校驗運(yùn)算。通過檢查四個S的結(jié)果，可以實現(xiàn)檢錯糾錯的的目的。實際情況是，當(dāng)譯碼求出來的S4、S3、S2、S1的得值與表2.3中的那一列的值相同，就說明是哪一位出錯；故人們又稱表2.3為出錯模式表。若出錯的是數(shù)據(jù)位，對其求反則實現(xiàn)糾錯；若出錯的是校驗位則不必理睬。舉例如下：
任何一位（含數(shù)據(jù)位、校驗位）均不錯，則四個S都應(yīng)為0值；
任何單獨(dú)一位數(shù)據(jù)位出錯，四個S中會有三個為1；如D3錯，則S4 S3 S2 S1為1110。
若單獨(dú)一位校驗位出錯，四個S中會有一個或兩個為1；如P1錯，S4 S3 S2 S1為1001，如P4錯，S4 S3 S2 S1為1000。
任何兩位（含數(shù)據(jù)位、校驗位）同時出錯，S4一定為0，而另外三個S位一定不全為0，此時只知道是兩位同時出錯，但不能確定是哪兩位出錯，故已無法糾錯。如D1、 P2出錯，會使S4 S3 S2 S1為0001。請注意，S4的作用在于區(qū)分是奇數(shù)位出錯還是偶數(shù)位出錯，S4為1是奇數(shù)位錯，為0是無錯或偶數(shù)位錯。這不僅為發(fā)現(xiàn)兩位錯所必需，也是為確保能發(fā)現(xiàn)并改正一位錯所必需的。若不設(shè)置S4，某種兩位出錯對幾個S的影響與單獨(dú)另一位出錯可能是一樣的（不必花費(fèi)精力推敲），此時若不加以區(qū)分，簡單地按一位出錯自動完成糾錯處理反而會幫倒忙。
--------------------- 本文來自 jxm_96 的CSDN 博客 ，全文地址請點(diǎn)擊：https://blog.csdn.net/jxm_96/article/details/53047310?utm_source=copy
