一口君最近工作用到CRC校驗(yàn),順便整理本篇文章和大家一起研究。

一、CRC概念

1． 什么是CRC?

CRC(Cyclic Redundancy Checksum)是一種糾錯(cuò)技術(shù),代表循環(huán)冗余校驗(yàn)和。

數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼,其信息字段和校驗(yàn)字段長(zhǎng)度可以任意指定,但要求通信雙方定義的CRC標(biāo)準(zhǔn)一致。主要用來檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。它的使用方式可以說明如下圖所示:

在數(shù)據(jù)傳輸過程中,無論傳輸系統(tǒng)的設(shè)計(jì)再怎么完美,差錯(cuò)總會(huì)存在,這種差錯(cuò)可能會(huì)導(dǎo)致在鏈路上傳輸?shù)囊粋�(gè)或者多個(gè)幀被破壞(出現(xiàn)比特差錯(cuò),0變?yōu)?,或者1變?yōu)?),從而接受方接收到錯(cuò)誤的數(shù)據(jù)。

為盡量提高接受方收到數(shù)據(jù)的正確率,在接收方接收數(shù)據(jù)之前需要對(duì)數(shù)據(jù)進(jìn)行差錯(cuò)檢測(cè),當(dāng)且僅當(dāng)檢測(cè)的結(jié)果為正確時(shí)接收方才真正收下數(shù)據(jù)。檢測(cè)的方式有多種,常見的有奇偶校驗(yàn)、因特網(wǎng)校驗(yàn)和循環(huán)冗余校驗(yàn)等。

2． 使用方法概述

循環(huán)冗余校驗(yàn)是一種用于校驗(yàn)通信鏈路上數(shù)字傳輸準(zhǔn)確性的計(jì)算方法(通過某種數(shù)學(xué)運(yùn)算來建立數(shù)據(jù)位和校驗(yàn)位的約定關(guān)系的 )。

發(fā)送方計(jì)算機(jī)使用某公式計(jì)算出被傳送數(shù)據(jù)所含信息的一個(gè)值,并將此值 附在被傳送數(shù)據(jù)后,接收方計(jì)算機(jī)則對(duì)同一數(shù)據(jù)進(jìn)行 相同的計(jì)算,應(yīng)該得到相同的結(jié)果。

如果這兩個(gè) CRC結(jié)果不一致,則說明發(fā)送中出現(xiàn)了差錯(cuò),接收方計(jì)算機(jī)可要求發(fā)送方計(jì)算機(jī)重新發(fā)送該數(shù)據(jù)。

3． 應(yīng)用廣泛

在諸多檢錯(cuò)手段中,CRC是最著名的一種。CRC的全稱是循環(huán)冗余校驗(yàn),其特點(diǎn)是:檢錯(cuò)能力強(qiáng),開銷小,易于用編碼器及檢測(cè)電路實(shí)現(xiàn)。從其檢錯(cuò)能力來看,它所不能發(fā)現(xiàn)的錯(cuò)誤的幾率僅為0．0047%以下。

從性能上和開銷上考慮,均遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)及算術(shù)和校驗(yàn)等方式。

因而,在數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)通訊領(lǐng)域,CRC無處不在:著名的通訊協(xié)議X．25的FCS(幀檢錯(cuò)序列)采用的是CRC-CCITT,WinRAR、NERO、ARJ、LHA等壓縮工具軟件采用的是CRC32,磁盤驅(qū)動(dòng)器的讀寫采用了CRC16,通用的圖像存儲(chǔ)格式GIF、TIFF等也都用CRC作為檢錯(cuò)手段。

二、CRC名稱的定義

這里需要知道幾個(gè)組成部分或者說計(jì)算概念:多項(xiàng)式公式、多項(xiàng)式簡(jiǎn)記式、數(shù)據(jù)寬度、初始值、結(jié)果異或值、輸入值反轉(zhuǎn)、輸出值反轉(zhuǎn)、參數(shù)模型。

1、多項(xiàng)式公式

對(duì)于CRC標(biāo)準(zhǔn)除數(shù),一般使用多項(xiàng)式(或二項(xiàng)式)公式表示,如下圖中除數(shù)11011(poly值為0x1c)的二項(xiàng)式為G(X)=X4+X3+X+1,X的指數(shù)就代表了該bit位上的數(shù)據(jù)為1,(最低位為0)。

這里特別注意一下位數(shù)問題,除數(shù)的位數(shù)為二項(xiàng)式最高次冪+1(4+1=5),這個(gè)很重要。

2、多項(xiàng)式簡(jiǎn)記式

通過對(duì)CRC的基本了解我們知道,多項(xiàng)式的首尾必定為1,而這個(gè)1的位置在下一步計(jì)算一定為0,所以就把前面這個(gè)1給省略掉了,出現(xiàn)了一個(gè)叫簡(jiǎn)記式的東西,如上例中除數(shù)11011的簡(jiǎn)記式為1011,很多看過CRC高級(jí)語言源碼的人會(huì)知道,對(duì)于CRC_16標(biāo)準(zhǔn)下G(X)=X16+X15+X2+1(16#18005)的poly值實(shí)際上是8005,這里使用的就是簡(jiǎn)記式。后面會(huì)對(duì)這個(gè)用法做一個(gè)說明。

3、數(shù)據(jù)寬度

數(shù)據(jù)寬度指的就是CRC校驗(yàn)碼的長(zhǎng)度(二進(jìn)制位數(shù)),知道了CRC的運(yùn)算概念和多項(xiàng)式,就可以理解這個(gè)概念了,CRC長(zhǎng)度始終要比除數(shù)位數(shù)少1,與簡(jiǎn)記式長(zhǎng)度是一致的。

以上三個(gè)數(shù)據(jù)就是我們經(jīng)常能夠用到的基本數(shù)據(jù)

4、初始值與結(jié)果異或值

在一些標(biāo)準(zhǔn)中,規(guī)定了初始值,則數(shù)據(jù)在進(jìn)行上述二項(xiàng)式運(yùn)算之前,需要先將要計(jì)算的數(shù)據(jù)與初始值的最低字節(jié)進(jìn)行異或,然后再與多項(xiàng)式進(jìn)行計(jì)算。

而在結(jié)果異或值不為零的情況下,則需要將計(jì)算得到的CRC結(jié)果值再與結(jié)果異或值進(jìn)行一次異或計(jì)算,得到的最終值才是我們需要的CRC校驗(yàn)碼。

這里可以看出,初始值與結(jié)果值的位數(shù)要求與數(shù)據(jù)寬度一致。

5、輸入值反轉(zhuǎn)與輸出值反轉(zhuǎn)

輸入值反轉(zhuǎn)的意思是在計(jì)算之前先將二項(xiàng)式反轉(zhuǎn),然后再用得到的新值和數(shù)據(jù)進(jìn)行計(jì)算。如對(duì)于G(X)=X16+X15+X2+1(16#18005),其正向值為1 1000 0000 0000 0101,反轉(zhuǎn)值則為1010 0000 0000 0001 1

輸出值反轉(zhuǎn)則是將最終得到的CRC結(jié)果反轉(zhuǎn)。

通常,輸入值反轉(zhuǎn)后的結(jié)果值也會(huì)是反轉(zhuǎn)的,所以這兩個(gè)選項(xiàng)一般是同向的,我們只有在在線CRC計(jì)算器中會(huì)看到自由選擇正反轉(zhuǎn)的情況存在。