當(dāng)前位置:首頁 > 公眾號精選 > C語言與CPP編程
[導(dǎo)讀]最近工作用到CRC校驗(yàn),順便整理本篇文章和大家一起研究。一、CRC概念1.什么是CRC?CRC(CyclicRedundancyChecksum)是一種糾錯(cuò)技術(shù),代表循環(huán)冗余校驗(yàn)和。數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼,其信息字段和校驗(yàn)字段長度可以任意指定,但要求通信雙方定義的C...

最近工作用到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)字段長度可以任意指定,但要求通信雙方定義的CRC標(biāo)準(zhǔn)一致。主要用來檢測或校驗(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ù)之前需要對數(shù)據(jù)進(jìn)行差錯(cuò)檢測,當(dāng)且僅當(dāng)檢測的結(jié)果為正確時(shí)接收方才真正收下數(shù)據(jù)。檢測的方式有多種,常見的有奇偶校驗(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ī)則對同一數(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),開銷小,易于用編碼器及檢測電路實(shí)現(xiàn)。從其檢錯(cuò)能力來看,它所不能發(fā)現(xiàn)的錯(cuò)誤的幾率僅為0.0047%以下。

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

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

二、CRC名稱的定義

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

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

對于CRC標(biāo)準(zhǔn)除數(shù),一般使用多項(xiàng)式(或二項(xiàng)式)公式表示,如下圖中除數(shù)11011(poly值為0x1b)的二項(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)式簡記式

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

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

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

以上三個(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ì)算。如對于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)的情況存在。

三、常見的CRC算法

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

名稱多項(xiàng)式表示法應(yīng)用舉例
CRC-8X8 X2 X 10X107
CRC-12X12 X11 X3 X2 X 10X180Ftelecom systems
CRC-16X16 X15 X2 10X18005Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSI
CRC-CCITTX16 X12 X5 10X11021ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS
CRC-32X32 X26 X23 X22 X16 X12 X11 X10 X8 X7 X5 X4 X2 X 10x104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
CRC-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校驗(yàn)算法前置知識

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

1. 異或

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

0^0?=?0
0^1?=?1
1^1?=?0
1^0?=?1
異或運(yùn)算存在如下幾個(gè)規(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 = 0 0 1 = 1 1 1 = 0 1 0 = 1 我們發(fā)現(xiàn)模2加法的計(jì)算結(jié)果,同異或運(yùn)算結(jié)果一模一樣。進(jìn)一步推演,我們會(huì)發(fā)現(xiàn),異或運(yùn)算的5個(gè)規(guī)律,同樣適合于模2加法。這里,就不在一一列舉了。

3. 模2減法

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

4. 模2除法

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

五、CRC原理

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

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

那么,CRC校驗(yàn)的具體做法就是

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

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

(3)將這個(gè)校驗(yàn)碼附在原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校驗(yàn)中有兩個(gè)關(guān)鍵點(diǎn):

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

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

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

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

實(shí)例:

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

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

使用上面計(jì)算的校驗(yàn)和和消息數(shù)據(jù),可以創(chuàng)建要傳輸?shù)拇a字。

有時(shí)候,我們需要填充checksum到制定的位置,這就涉及到字節(jié)序問題,建議用memcpy()進(jìn)行拷貝。

七、代碼實(shí)現(xiàn)

實(shí)現(xiàn)算法參考網(wǎng)絡(luò)相關(guān)代碼,進(jìn)行整理并驗(yàn)證,可直接使用。crc.c

/*??
?*一口Linux
?*2021.6.21
?*version:?1.0.0
*/

#include?"crc.h"
#include?

typedef?enum?{
?REF_4BIT?=?4,
?REF_5BIT?=?5,
?REF_6BIT?=?6,
?REF_7BIT?=?7,
?REF_8BIT?=?8,
?REF_16BIT?=?16,
?REF_32BIT?=?32
}REFLECTED_MODE;

uint32_t?ReflectedData(uint32_t?data,?REFLECTED_MODE?mode)
{
?data?=?((data?
本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉