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

一、CRC概念

1． 什么是CRC?

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

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

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

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

2． 使用方法概述

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

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

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

3． 應用廣泛

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

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

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

二、CRC名稱的定義

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

1、多項式公式

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

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

2、多項式簡記式

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

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

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

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

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

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

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

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

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

輸入值反轉(zhuǎn)的意思是在計算之前先將二項式反轉(zhuǎn),然后再用得到的新值和數(shù)據(jù)進行計算。如對于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é)果值也會是反轉(zhuǎn)的,所以這兩個選項一般是同向的,我們只有在在線CRC計算器中會看到自由選擇正反轉(zhuǎn)的情況存在。