一文了解CRC校驗算法知識 - OFweek 人工智能網(wǎng)

一文了解CRC校驗算法知識

2021-06-29 14:27

三、常見的CRC算法

雖然CRC可以任意定義二項式、數(shù)據(jù)長度等,但沒有一個統(tǒng)一的標(biāo)準(zhǔn)的話,就會讓整個計算變得非常的麻煩。但實(shí)際上,不同的廠家經(jīng)常采用不同的標(biāo)準(zhǔn)算法,這里列出了一些國際常用的模型表:

名稱多項式表示法應(yīng)用舉例CRC-8X8+X2+X+10X107
CRC-12X12+X11+X3+X2+X+10X180Ftelecom systemsCRC-16X16+X15+X2+10X18005Bisync, Modbus, USB, ANSI X3．28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSICRC-CCITTX16+X12+X5+10X11021ISO HDLC, ITU X．25, V．34/V．41/V．42, PPP-FCSCRC-32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+10x104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32CX32+X28+X27+X26+X25+X23+X22+X20+X19+X18+X14+X13+X11+X10+X9+X8+X6+10x11EDC6F41iSCSI, SCTP, G．hn payload, SSE4．2, Btrfs, ext4, Ceph

四、CRC校驗算法前置知識

在學(xué)習(xí)CRC校驗算法之前,先復(fù)習(xí)一下CRC會涉及的主要幾個主要的算法。

1．異或

異或,就是不同為1,相同為0,運(yùn)算符號是^。

0^0 = 0
0^1 = 1
1^1 = 0
1^0 = 1

異或運(yùn)算存在如下幾個規(guī)律,需要了解。

0^x = x 即0 異或任何數(shù)等于任何數(shù)
1^x = ～x 即1異或任何數(shù)等于任何數(shù)取反
x^x = 0 即任何數(shù)與自己異或,結(jié)果為0
a ^ b = b ^ a 交換律
a ^ (b ^ c) = (a ^ b) ^c 結(jié)合律
2．模2加法

模2加法相對于普通的算術(shù)加法,主要的區(qū)別在模2加法,不做進(jìn)位處理。具體結(jié)果如下。0+0 = 00+1 = 11+1 = 01+0 = 1我們發(fā)現(xiàn)模2加法的計算結(jié)果,同異或運(yùn)算結(jié)果一模一樣。進(jìn)一步推演,我們會發(fā)現(xiàn),異或運(yùn)算的5個規(guī)律,同樣適合于模2加法。這里,就不在一一列舉了。

3．模2減法

模2減法相對于普通的算術(shù)減法,主要的區(qū)別在模2減法,不做借位處理。具體結(jié)果如下。0-0 = 00-1 = 11-1 = 01-0 = 1我們發(fā)現(xiàn)模2減法的計算結(jié)果,同模2加法,以及異或的運(yùn)算結(jié)果一模一樣。進(jìn)一步推演,我們會發(fā)現(xiàn),異或運(yùn)算的5個規(guī)律,同樣適合于模2減法。這里,就不在一一列舉了。

4．模2除法

模2除法相對于普通的算術(shù)除法,主要的區(qū)別在模2除法,它既不向上位借位,也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小,只要以相同位數(shù)進(jìn)行相除即可。

五、CRC原理

CRC原理:在K位信息碼(目標(biāo)發(fā)送數(shù)據(jù))后再拼接R位校驗碼,使整個編碼長度為N位,因此這種編碼也叫(N,K)碼。

通俗的說,就是在需要發(fā)送的信息后面附加一個數(shù)(即校驗碼),生成一個新的發(fā)送數(shù)據(jù)發(fā)送給接收端。這個數(shù)據(jù)要求能夠使生成的新數(shù)據(jù)被一個特定的數(shù)整除。這里的整除需要引入模 2除法的概念。

那么,CRC校驗的具體做法就是

(1)選定一個標(biāo)準(zhǔn)除數(shù)(K位二進(jìn)制數(shù)據(jù)串)

(2)在要發(fā)送的數(shù)據(jù)(m位)后面加上K-1位0,然后將這個新數(shù)(M+K-1位)以模2除法的方式除以上面這個標(biāo)準(zhǔn)除數(shù),所得到的余數(shù)也就是該數(shù)據(jù)的CRC校驗碼(注:余數(shù)必須比除數(shù)少且只少一位,不夠就補(bǔ)0)

(3)將這個校驗碼附在原m位數(shù)據(jù)后面,構(gòu)成新的M+K-1位數(shù)據(jù),發(fā)送給接收端。

(4)接收端將接收到的數(shù)據(jù)除以標(biāo)準(zhǔn)除數(shù),如果余數(shù)為0則認(rèn)為數(shù)據(jù)正確。

注意:CRC校驗中有兩個關(guān)鍵點(diǎn):

一是要預(yù)先確定一個發(fā)送端和接收端都用來作為除數(shù)的二進(jìn)制比特串(或多項式);

二是把原始幀與上面選定的除進(jìn)行二進(jìn)制除法運(yùn)算,計算出FCS。

前者可以隨機(jī)選擇,也可按國際上通行的標(biāo)準(zhǔn)選擇,但最高位和最低位必須均為“1”

六、循環(huán)冗余的計算

實(shí)例:

由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致,只有位數(shù)和生成多項式不一樣,下面就舉例,來說明CRC校驗碼生成過程。

對于數(shù)據(jù)1110 0101(16#E5),以指定除數(shù)11011求它的CRC校驗碼,其過程如下: