加入星計(jì)劃,您可以享受以下權(quán)益:

  • 創(chuàng)作內(nèi)容快速變現(xiàn)
  • 行業(yè)影響力擴(kuò)散
  • 作品版權(quán)保護(hù)
  • 300W+ 專業(yè)用戶
  • 1.5W+ 優(yōu)質(zhì)創(chuàng)作者
  • 5000+ 長期合作伙伴
立即加入
  • 正文
    • 一、信息論中的 CRC
    • 二、CRC 循環(huán)校驗(yàn)碼的原理方法
    • 三、CRC 循環(huán)校驗(yàn)的代碼分析
  • 推薦器件
  • 相關(guān)推薦
  • 電子產(chǎn)業(yè)圖譜
申請(qǐng)入駐 產(chǎn)業(yè)圖譜

淺談通信校驗(yàn)碼及CRC校驗(yàn)

04/02 08:50
5420
閱讀需 12 分鐘
加入交流群
掃碼加入
獲取工程師必備禮包
參與熱點(diǎn)資訊討論

一、信息論中的 CRC

我上大學(xué)的時(shí)候,有一門課程叫做信息論,我就是從這個(gè)課程中學(xué)到的 CRC 校驗(yàn)這個(gè)詞的,沒錯(cuò),當(dāng)時(shí)學(xué)完整個(gè)課程后,CRC 對(duì)我來說依然只是一個(gè)單薄的縮寫詞語,全稱我都不知道是啥。CRC 全稱是循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check)。說到信息論中的碼可真是數(shù)不勝數(shù),信源編碼,信道編碼,校驗(yàn)碼,糾錯(cuò)碼,無損失的霍夫曼編碼,有損的熵編碼等等,話說當(dāng)時(shí)我還是手工計(jì)算過霍夫曼編碼,現(xiàn)在也確實(shí)不知道哪里會(huì)用到。

這個(gè) CRC 編碼應(yīng)該屬于信息論中的信道編碼中的校驗(yàn)碼,它沒有糾錯(cuò)能力,主要是對(duì)信道傳輸過程中做一個(gè)信息完整性的檢驗(yàn)?;氐轿覀兊漠a(chǎn)品開發(fā)中,我們可能最先接觸的是奇偶校驗(yàn),累加和以及 CRC 編碼,而并不是什么信道編碼和檢錯(cuò)碼。奇偶校驗(yàn):奇偶校驗(yàn)碼常用來做串口通信的校驗(yàn),它一種簡單的檢錯(cuò)碼,用于檢測(cè)數(shù)據(jù)傳輸中的錯(cuò)誤。它通過在數(shù)據(jù)中增加一個(gè)額外的bit,使得整個(gè)數(shù)據(jù)塊中1的個(gè)數(shù)(或0的個(gè)數(shù))為奇數(shù)(或偶數(shù)),從而實(shí)現(xiàn)簡單的錯(cuò)誤檢測(cè)。如果接收端接收到的數(shù)據(jù)中奇偶校驗(yàn)位與發(fā)送端發(fā)送的數(shù)據(jù)中的奇偶性不一致,就說明在傳輸過程中可能出現(xiàn)了錯(cuò)誤。

累加和校驗(yàn):累加和校驗(yàn)也稱為求和校驗(yàn)或加法校驗(yàn),它也是一種簡單的校驗(yàn)方法,它的原理是將數(shù)據(jù)中的所有字節(jié)(或比特)相加,并將結(jié)果附加到數(shù)據(jù)的末尾進(jìn)行傳輸。接收端對(duì)接收到的數(shù)據(jù)進(jìn)行相同的操作,然后比較計(jì)算得到的校驗(yàn)和是否相同,以判斷數(shù)據(jù)是否在傳輸過程中發(fā)生了錯(cuò)誤,這種校驗(yàn)和在 IP 協(xié)議中有部分使用。

不足:以上兩種算法都是非常簡單的,無論是計(jì)算 0 或者 1 的個(gè)數(shù),還是兩端同時(shí)做加法運(yùn)算都避免不了失誤。在奇偶校驗(yàn)中如果兩個(gè) bit 異位就會(huì)被判斷為正確,這發(fā)生的概率非常大。而在累加和校驗(yàn)中,如果出現(xiàn)兩個(gè)字節(jié)錯(cuò)誤,且他們的累加和和原值的累加和相等,最終也會(huì)被判斷為完整,這個(gè)概率相對(duì)于奇偶校驗(yàn)要小很多,但是對(duì)于大數(shù)據(jù)量,糟糕的信道環(huán)境中的傳輸還是不夠的。我們來看看 CRC 校驗(yàn)是怎么提升這個(gè)檢錯(cuò)能力的。

二、CRC 循環(huán)校驗(yàn)碼的原理方法

CRC算法是以GF(2)(模 2 除法求余數(shù))多項(xiàng)式算術(shù)為數(shù)學(xué)基礎(chǔ)的。我們先看多項(xiàng)式是怎么來的!

假設(shè)我們有一段數(shù)據(jù)需要傳輸,數(shù)據(jù)是二進(jìn)制的 10100111,那么我們以 x 為變量,定義如下的一個(gè)多項(xiàng)式:1x^7 + 0x^6 + 1x^5 + 0x^4 + 0x^3 + 1x^2 +1x^1 + 1x^0可以看出,數(shù)據(jù)就是多項(xiàng)式的系數(shù),每個(gè) bit 對(duì)應(yīng)到的是 x 的對(duì)應(yīng)指數(shù)項(xiàng)的系數(shù),這個(gè)系數(shù)非 0 即 1,因此多項(xiàng)式可以簡化為:x^7 + x^5 + x^2+ x + 1這樣是不是就很像我們平時(shí)看到的 CRC 校驗(yàn)的多項(xiàng)式了。上面這個(gè)是 8bit 的多項(xiàng)式,最高次冪為 7,對(duì)應(yīng)的 16bit 的多項(xiàng)式中,最高次冪就為 15 了。

什么是模 2 除法求余呢?

多項(xiàng)式中的加減法,使用模2算術(shù)執(zhí)行對(duì)應(yīng)項(xiàng)上系數(shù)的加減,模2就是指的加減時(shí)不考慮進(jìn)位和借位。即:0 + 0 = 0 ? ?0 - 0 = 00 + 1 = 1 ? ?0 - 1 = 11 + 0 = 1 ? ?1 - 0 = 11 + 1 = 0 ? ?1 - 1 = 0總結(jié)一下規(guī)律可以得出,這種加減法的運(yùn)算正好等同于我們計(jì)算機(jī)中的異或運(yùn)算,數(shù)學(xué)理論是基礎(chǔ),我們這里可以記住異或運(yùn)算就好了。多項(xiàng)式乘法和一般多項(xiàng)式乘法也是一樣的,只是在各項(xiàng)相加的時(shí)候按模2算術(shù)相加進(jìn)行,例如:

(x^3 + x^2 + 1)(x^3 + x^1 + 1)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x + 1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

換成除法,我們也可以通過列一下二進(jìn)制的除法算式來求余數(shù),我們把包含 n 次冪的項(xiàng)省略掉。

上面的除法就是我們用在 CRC 中做運(yùn)算用的,我們看看 CRC 的邏輯假如我們需要傳輸一個(gè)長度為 k 位的數(shù)據(jù)塊,它對(duì)應(yīng)的多項(xiàng)式我們稱為 M,按照上面圖片中的除法運(yùn)算,我們需要傳輸?shù)?8bit 數(shù)據(jù)為:11100110。假設(shè)我們傳輸 MSB,則它對(duì)應(yīng)多項(xiàng)式為 x^7 + x^6 + x^5 + x^2 + x。最后沒有常數(shù)項(xiàng) 1,因?yàn)樽詈笠粋€(gè) bit 為 0。這時(shí)候,發(fā)送信息的一端和接收信息的一端就要約定一個(gè)多項(xiàng)式 G。假設(shè)按照上圖除法中的數(shù)據(jù),我們這里使用的就是 CRC-3(一般沒有,是為了適合上圖的除式),取多項(xiàng)式為x^4 + x + 1,最高次冪為r = 4。這時(shí)候,發(fā)送端先在 M 后面添加 (r - 1) = 3 個(gè) 0,標(biāo)記為 Mx,然后我們使用 Mx 除以 G 將得到一個(gè)次數(shù)等于或者小于 r - 1 的余數(shù)多項(xiàng)式,我們標(biāo)記為 R 多項(xiàng)式,這個(gè) R 對(duì)應(yīng)的 bit 串就是校驗(yàn)碼。發(fā)送端會(huì)將原始數(shù)據(jù)和校驗(yàn)碼一起發(fā)送出去,接收端則按照同樣的方式進(jìn)行計(jì)算余數(shù) R,然后判斷和接收到的是否相同來檢驗(yàn)傳輸是否有錯(cuò)誤。

細(xì)心的你會(huì)發(fā)現(xiàn),這里的原理和校驗(yàn)和其實(shí)是一樣的,差別在于校驗(yàn)和是累加,這里是對(duì)一個(gè)多項(xiàng)式 G 做除法。而這個(gè)多項(xiàng)式 G 是可以任意定義的,不同的多項(xiàng)式的檢驗(yàn)錯(cuò)誤的能力是不同的,校驗(yàn)過程中的運(yùn)算是不同的?;诖?,很多行業(yè)形成固定的多項(xiàng)式,一般我們開發(fā)時(shí)遵循他們就可以了:

三、CRC 循環(huán)校驗(yàn)的代碼分析

我們?nèi)绾斡贸绦騺碛?jì)算這個(gè)CRC 的除法呢?

    將Mx^r的前r位放入一個(gè)長度為r的寄存器;如果寄存器的首位為1,將寄存器左移1位(將Mx^r剩下部分的MSB移入寄存器的LSB),再與G的后r位異或,否則僅將寄存器左移1位(將Mx^r剩下部分的MSB移入寄存器的LSB);重復(fù)第2步,直到M全部Mx^r移入寄存器;寄存器中的值則為校驗(yàn)碼。

我們用下面這個(gè)式子來看一下過程

通過上面的模擬寄存器操作,我們就得到了一個(gè)校驗(yàn)碼,理論上無論多少個(gè) bit 的數(shù)據(jù)塊,對(duì)我們 4bit 的多項(xiàng)式做除法最后都會(huì)得到一個(gè)4bit 可以存放的校驗(yàn)碼,我們就把他掛在我們的數(shù)據(jù)塊尾巴上送出去。只要發(fā)送接收到的多項(xiàng)式一致,就可以根據(jù)這個(gè)校驗(yàn)碼來進(jìn)行完整性校驗(yàn)了。這部分代碼的實(shí)現(xiàn),我之前講過,在我的 從 0 到 1 完成 BMS 保護(hù)板設(shè)計(jì)專輯里面。

I2C 驅(qū)動(dòng)及其 Checksum在 BMS 系統(tǒng)中的應(yīng)用

2024-02-26

文章里面講到,TI 規(guī)定的 CRC8 的多項(xiàng)式為:x^8 + x^2 + x +1,對(duì)應(yīng)可知多項(xiàng)式 G 的 Key 為100000111。由于我們?cè)谒惴ㄖ惺窍茸笠圃僮霎惢?,因此最高位可以去掉,?duì)應(yīng)到我們程序中的參數(shù) key 就是 00000111, 16 進(jìn)制為 0x7。

static u8 CRC8(u8 *ptr, u8 len, u8 key){    u8 i;    u8 crc = 0;
    while(len-- != 0) //按照數(shù)據(jù)長度進(jìn)行CRC計(jì)算    {        for(i=0x80; i!=0; i>>=1) //右移位8次        {            if((crc & 0x80) != 0) //crc高bit不為0,crc異或key            {                crc <<= 1;                crc ^= key;             }            else                crc <<= 1;
            if(((*ptr) & i) != 0) //字節(jié)中bit不為0,crc異或key                crc ^= key;        }        ptr++; //下一個(gè)字節(jié)    }    return(crc);}

這是對(duì)于 CRC8 的循環(huán)校驗(yàn)算法,看起來比較簡單,移位幾次,異或幾次就可以了,但是當(dāng)我們把校驗(yàn)位數(shù)增加到 CRC32 的時(shí)候,這個(gè)算法就復(fù)雜起來,因此很多 MCU,比如 STM32 就內(nèi)置了硬件的 CRC 校驗(yàn)。多項(xiàng)式也可以自定義,使用起來還是很靈活的。如果沒有硬件幫忙,我們解決 CRC32 校驗(yàn)的問題可以通過查表法。制作這個(gè)表的方法其實(shí)就是上面這樣的移位和異或算法。簡化的寫法如下:

unsigned int CRC;//int的大小是32位,作32位CRC寄存器unsigned int CRC_32_Table[256];//用來保存CRC碼表void GenerateCRC32_Table(){   for(int i=0;i<256;++i)//用++i以提高效率{      CRC=i;       for(int j=0;j<8;++j)         {           if(CRC&1)// LSM為1           CRC=(CRC>>1)^0xEDB88320;//采取反向校驗(yàn)           else //0xEDB88320就是CRC-32多項(xiàng)表達(dá)式的reversed值            CRC>>=1;         }     CRC_32_Table[i]=CRC;  }}

看到?jīng)],我們先把一個(gè)字節(jié)可以表示的 256 個(gè)數(shù)對(duì)應(yīng)的校驗(yàn)和計(jì)算出來了,我們的通信往往都是以字節(jié)為單位進(jìn)行傳輸?shù)?,那么我們有了這樣的表后,就相當(dāng)于直接有了一個(gè) 8bit 數(shù)及其 CRC32 校驗(yàn)碼的映射表,直接查表速度極快。以上就是對(duì) 奇偶校驗(yàn),累加和校驗(yàn)和 CRC 校驗(yàn)的理解。

推薦器件

更多器件
器件型號(hào) 數(shù)量 器件廠商 器件描述 數(shù)據(jù)手冊(cè) ECAD模型 風(fēng)險(xiǎn)等級(jí) 參考價(jià)格 更多信息
TJA1051T/E,118 1 NXP Semiconductors TJA1051 - High-speed CAN transceiver SOIC 8-Pin

ECAD模型

下載ECAD模型
$0.3 查看
NRF52832-QFAA-R 1 Nordic Semiconductor Telecom Circuit, 1-Func, 6 X 6 MM, 0.40 MM PITCH, ROHS AND REACH COMPLIANT, QFN-48
$5 查看
MCP2551-I/SN 1 Microchip Technology Inc DATACOM, INTERFACE CIRCUIT, PDSO8, 0.150 INCH, LEAD FREE, PLASTIC, SOIC-8

ECAD模型

下載ECAD模型
$1.37 查看

相關(guān)推薦

電子產(chǎn)業(yè)圖譜

多年硬件從業(yè)經(jīng)驗(yàn),專注分享從研發(fā)到供應(yīng)鏈,再到精益制造過程中的經(jīng)驗(yàn)和感悟!