校驗,是在數據傳送過程中為了檢查數據完整性的一種手段。通常的做法是發送方在數據幀之中或者之后附帶一段校驗碼,接收方通過特定的方式對接收到的所有數據做某種操作,操作的結果與預定的不符,說明傳送中發生了錯誤,而有些校驗碼還附帶糾錯功能,即檢查出錯誤后還可以恢復原數據,不過這種恢復是建立在一些假設基礎上的,因此在實際大量數據傳輸中并不經常使用。
首先介紹distance的概念,distance就是兩個N位碼之間不同的位的個數。例如0110100與0111010,他們有3個位不同,distance就為3。
所有校驗碼的原理都是一樣的:即從選取一個集合,這個集合中任意2個碼的distance要大于m。只用這個集合中的元素傳輸數據,如果接收方接受到的數據不屬于此集合,說明有錯誤在傳輸中發生。上面說的校驗碼就是為了達到這個目的。
如大家最熟悉最簡單的奇偶校驗,通過添加一個校驗位,合法碼集合的任意2個碼的distance大于2,即1個合法碼至少要改變2個位才能得到另一個合法碼。
一個最小distance為m的集合,可以檢測最多m-1位錯誤的傳輸,若有m位錯誤,就會被當作合法碼而校驗成功,還拿奇偶校驗做例子,如果發生了2個位都因錯誤改變了(如1011變為1000),奇偶校驗后還是合法的。
再說一個奇偶校驗的衍生,就是累加和校驗。奇偶校驗的算法可以描述為:我們對一個數據幀按位相加,所得的結果作為校驗位。類似的,我們講數據1byte1byte的相加,無視溢出,就得到累加和校驗byte。當然,并不一定必須要1byte1byte相加,這取決于處理器的位數,用16位機你也可以用2byte做累加和。
海明校驗:distance=3,即可以校驗2位錯誤
海明校驗的基本思想是把數據分組,分別對每個組做奇偶校驗。通過一系列規則的確定檢查并且改正錯誤
分組規則:海明校驗用bit1,bit2,bit4,bit8,bit16,bit32.......做為校驗位,插到數據幀里面。這里的bit1,bit2指的是將校驗位插入后,從低位到高位進行編號,從1開始編。例如發送01010010111(高位在前),則其中最末位1(bit1),次末位1(bit2),以及0(bit4),1(bit8),就是校驗位。
由于校驗位是2的倍數,因此校驗位的編碼都只含有1個1,如bit1=bit0001,bit2=bit0010,bit4=bit0100,bit8=bit1000.......那么,我們把所有與之對應位是1的分在一組,如bit3=bit0011,bit5=bit0101,bit7=bit0111,bit9=bit1001,bit11=bit1011,bit13=bit1101,bit15=bit1111這些最低位都為1,因此與bit1校驗位分在同一組。對這組做奇校驗或者偶校驗,決定bit1的值。
bit7 bit6 bit5 bit3 bit4 bit2 bit1
1 0 1 0
1 0 0 1
1 1 0 0
這是一個7位數據的例子,bit7,6,5與bit4分為一組;bit7,6,3與bit2分為一組;bit7,5,3與bit1分為一組;對每行做偶校驗,即可決定bit4,bit2,bit1的值
下面看下海明校驗怎樣糾錯,在實際傳輸中,兩位都發生錯誤的幾率比一位發生錯誤的幾率高很多,我們假設只有1位發生錯誤,如:
bit7 bit6 bit5 bit3 bit4 bit2 bit1
1 0 1 1
1 0 0 0
1 1 0 0
可以看出,第一行與第二行不滿足偶校驗規則,而能夠引起這一結果的只有可能是bit6在傳輸中發生了錯誤,因為只有bit6對且僅對這兩行產生效果。我們將bit6取反 就可得到未出錯的數據
CRC校驗,cyclic redundancy check 循環冗余碼校驗 。這種校驗被廣泛用于數據傳輸之中,因為它的糾錯率很高,你的硬盤上,每512個字節后就會有一個CRC校驗碼,但是大部分人可能都不知道CRC校驗的原理,這是我研究好久才得出的結論,網上絕對找不到的。
CRC校驗的原理很簡單:任何一個數位異或它本身,就得到全0。下面我們看一下CRC是如何產生校驗碼的。先介紹一下生成多項式的概念,一個多項式可以由一段二進制代碼表示,如x3+x2+1可以用1101來表示,即1*x3+1*x2+0*x1+1*x0(次方我打不出來。。。)數據傳送中,接受方和發送方先約定一個生成多項式(你可以在各種通信協議中找到,例如CRC-ITU,CRC-16,CRC-12等等),用數據幀左移N位后所代表的多項式除以NN+1位的生成多項式,就可得到N位的余式,這個余式代表的二進制序列就作為CRC校驗碼。這里的多項式除法和我們一般的除法有一些不同,大家不要深究,但是有除法的概念會對以后查表算法的理解有很到的幫助,所以在這里介紹一下。
那么怎么進行這種除法呢?比如數據幀為1011,生成多項式為11011,以生成4位CRC,首先把數據幀左移4位成10110000,寫在被除數的位置,然后和11011首位對齊,做位異或:
10110000
11011
01101000(結果)
將11011右移直到上一步結果的左數第一個1與11011首位對齊,繼續做位異或,直到結果為4位或以下
01101000
011011
00000100
則4位CRC就為0100
將來我們發送的數據就是10110100,將CRC附在數據幀后面。
很奇妙的是:把這個發送數據按上述規律再做同樣的位異或操作,得到必定是全0,(原理會在以后講到)大家可以筆算一下。這就是CRC檢查錯誤的方法,CRC也有糾錯功能,如果得到結果不是全0,則還按上述規則繼續位異或,我們會發現余數是按某個規律循環的,這也是循環冗余碼校驗之所以得名的原因,直到出現某個特殊的余數時,可以證明出錯位此時對應的就是出錯位。但在實際中大量數據傳輸這種糾錯能力很少應用,這里就不詳細介紹了。
歡迎光臨 (http://m.zg4o1577.cn/bbs/) | Powered by Discuz! X3.1 |