校驗(yàn)，是在數(shù)據(jù)傳送過程中為了檢查數(shù)據(jù)完整性的一種手段。通常的做法是發(fā)送方在數(shù)據(jù)幀之中或者之后附帶一段校驗(yàn)碼，接收方通過特定的方式對接收到的所有數(shù)據(jù)做某種操作，操作的結(jié)果與預(yù)定的不符，說明傳送中發(fā)生了錯誤，而有些校驗(yàn)碼還附帶糾錯功能，即檢查出錯誤后還可以恢復(fù)原數(shù)據(jù)，不過這種恢復(fù)是建立在一些假設(shè)基礎(chǔ)上的，因此在實(shí)際大量數(shù)據(jù)傳輸中并不經(jīng)常使用。
首先介紹distance的概念，distance就是兩個N位碼之間不同的位的個數(shù)。例如0110100與0111010，他們有3個位不同，distance就為3。
所有校驗(yàn)碼的原理都是一樣的：即從選取一個集合，這個集合中任意2個碼的distance要大于m。只用這個集合中的元素傳輸數(shù)據(jù)，如果接收方接受到的數(shù)據(jù)不屬于此集合，說明有錯誤在傳輸中發(fā)生。上面說的校驗(yàn)碼就是為了達(dá)到這個目的。
如大家最熟悉最簡單的奇偶校驗(yàn)，通過添加一個校驗(yàn)位，合法碼集合的任意2個碼的distance大于2，即1個合法碼至少要改變2個位才能得到另一個合法碼。
一個最小distance為m的集合，可以檢測最多m-1位錯誤的傳輸，若有m位錯誤，就會被當(dāng)作合法碼而校驗(yàn)成功，還拿奇偶校驗(yàn)做例子，如果發(fā)生了2個位都因錯誤改變了（如1011變?yōu)?000），奇偶校驗(yàn)后還是合法的。
再說一個奇偶校驗(yàn)的衍生，就是累加和校驗(yàn)。奇偶校驗(yàn)的算法可以描述為：我們對一個數(shù)據(jù)幀按位相加，所得的結(jié)果作為校驗(yàn)位。類似的，我們講數(shù)據(jù)1byte1byte的相加，無視溢出，就得到累加和校驗(yàn)byte。當(dāng)然，并不一定必須要1byte1byte相加，這取決于處理器的位數(shù)，用16位機(jī)你也可以用2byte做累加和。

海明校驗(yàn)：distance=3,即可以校驗(yàn)2位錯誤
海明校驗(yàn)的基本思想是把數(shù)據(jù)分組，分別對每個組做奇偶校驗(yàn)。通過一系列規(guī)則的確定檢查并且改正錯誤
分組規(guī)則：海明校驗(yàn)用bit1,bit2,bit4,bit8,bit16,bit32.......做為校驗(yàn)位，插到數(shù)據(jù)幀里面。這里的bit1,bit2指的是將校驗(yàn)位插入后，從低位到高位進(jìn)行編號，從1開始編。例如發(fā)送01010010111（高位在前），則其中最末位1（bit1）,次末位1（bit2）,以及0(bit4),1(bit8),就是校驗(yàn)位。

由于校驗(yàn)位是2的倍數(shù)，因此校驗(yàn)位的編碼都只含有1個1，如bit1=bit0001,bit2=bit0010,bit4=bit0100,bit8=bit1000.......那么，我們把所有與之對應(yīng)位是1的分在一組，如bit3=bit0011,bit5=bit0101,bit7=bit0111,bit9=bit1001,bit11=bit1011,bit13=bit1101,bit15=bit1111這些最低位都為1，因此與bit1校驗(yàn)位分在同一組。對這組做奇校驗(yàn)或者偶校驗(yàn)，決定bit1的值。



bit7        bit6        bit5        bit3        bit4        bit2        bit1
1            0             1                          0               
1            0                           0                         1        
1            1                           0                                         0
這是一個7位數(shù)據(jù)的例子，bit7,6,5與bit4分為一組；bit7,6,3與bit2分為一組；bit7,5,3與bit1分為一組;對每行做偶校驗(yàn)，即可決定bit4,bit2,bit1的值
下面看下海明校驗(yàn)怎樣糾錯，在實(shí)際傳輸中，兩位都發(fā)生錯誤的幾率比一位發(fā)生錯誤的幾率高很多，我們假設(shè)只有1位發(fā)生錯誤，如：
bit7        bit6        bit5        bit3        bit4        bit2        bit1
1             0           1                           1               
1             0                           0                        0        
1             1                           0                                        0
可以看出，第一行與第二行不滿足偶校驗(yàn)規(guī)則，而能夠引起這一結(jié)果的只有可能是bit6在傳輸中發(fā)生了錯誤，因?yàn)橹挥衎it6對且僅對這兩行產(chǎn)生效果。我們將bit6取反 就可得到未出錯的數(shù)據(jù)

CRC校驗(yàn)，cyclic redundancy check 循環(huán)冗余碼校驗(yàn) 。這種校驗(yàn)被廣泛用于數(shù)據(jù)傳輸之中，因?yàn)樗�的糾錯率很高，你的硬盤上，每512個字節(jié)后就會有一個CRC校驗(yàn)碼，但是大部分人可能都不知道CRC校驗(yàn)的原理，這是我研究好久才得出的結(jié)論，網(wǎng)上絕對找不到的。
CRC校驗(yàn)的原理很簡單：任何一個數(shù)位異或它本身，就得到全0。下面我們看一下CRC是如何產(chǎn)生校驗(yàn)碼的。先介紹一下生成多項(xiàng)式的概念，一個多項(xiàng)式可以由一段二進(jìn)制代碼表示，如x3+x2+1可以用1101來表示，即1*x3+1*x2+0*x1+1*x0(次方我打不出來。。。)數(shù)據(jù)傳送中，接受方和發(fā)送方先約定一個生成多項(xiàng)式（你可以在各種通信協(xié)議中找到，例如CRC-ITU,CRC-16，CRC-12等等），用數(shù)據(jù)幀左移N位后所代表的多項(xiàng)式除以NN+1位的生成多項(xiàng)式，就可得到N位的余式，這個余式代表的二進(jìn)制序列就作為CRC校驗(yàn)碼。這里的多項(xiàng)式除法和我們一般的除法有一些不同，大家不要深究，但是有除法的概念會對以后查表算法的理解有很到的幫助，所以在這里介紹一下。
那么怎么進(jìn)行這種除法呢？比如數(shù)據(jù)幀為1011，生成多項(xiàng)式為11011，以生成4位CRC，首先把數(shù)據(jù)幀左移4位成10110000，寫在被除數(shù)的位置，然后和11011首位對齊，做位異或：
10110000
11011
01101000（結(jié)果）
將11011右移直到上一步結(jié)果的左數(shù)第一個1與11011首位對齊，繼續(xù)做位異或，直到結(jié)果為4位或以下
01101000
011011
00000100
則4位CRC就為0100
將來我們發(fā)送的數(shù)據(jù)就是10110100，將CRC附在數(shù)據(jù)幀后面。
很奇妙的是：把這個發(fā)送數(shù)據(jù)按上述規(guī)律再做同樣的位異或操作，得到必定是全0，（原理會在以后講到）大家可以筆算一下。這就是CRC檢查錯誤的方法，CRC也有糾錯功能，如果得到結(jié)果不是全0，則還按上述規(guī)則繼續(xù)位異或，我們會發(fā)現(xiàn)余數(shù)是按某個規(guī)律循環(huán)的，這也是循環(huán)冗余碼校驗(yàn)之所以得名的原因，直到出現(xiàn)某個特殊的余數(shù)時，可以證明出錯位此時對應(yīng)的就是出錯位。但在實(shí)際中大量數(shù)據(jù)傳輸這種糾錯能力很少應(yīng)用，這里就不詳細(xì)介紹了。