校驗(yàn)技術(shù)

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

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

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



bit7        bit6        bit5        bit3        bit4        bit2        bit1
1            0             1                          0               
1            0                           0                         1        
1            1                           0                                         0
這是一個(gè)7位數(shù)據(jù)的例子，bit7,6,5與bit4分為一組；bit7,6,3與bit2分為一組；bit7,5,3與bit1分為一組;對(duì)每行做偶校驗(yàn)，即可決定bit4,bit2,bit1的值
下面看下海明校驗(yàn)怎樣糾錯(cuò)，在實(shí)際傳輸中，兩位都發(fā)生錯(cuò)誤的幾率比一位發(fā)生錯(cuò)誤的幾率高很多，我們假設(shè)只有1位發(fā)生錯(cuò)誤，如：
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ā)生了錯(cuò)誤，因?yàn)橹挥衎it6對(duì)且僅對(duì)這兩行產(chǎn)生效果。我們將bit6取反 就可得到未出錯(cuò)的數(shù)據(jù)

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