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

一、信息論中的 CRC

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

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

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

不足：以上兩種算法都是非常簡(jiǎn)單的，無(wú)論是計(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)境中的傳輸還是不夠的。我們來(lái)看看 CRC 校驗(yàn)是怎么提升這個(gè)檢錯(cuò)能力的。

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

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

假設(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)式可以簡(jiǎn)化為：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

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

上面的除法就是我們用在 CRC 中做運(yùn)算用的，我們看看 CRC 的邏輯假如我們需要傳輸一個(gè)長(zhǎng)度為 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。最后沒(méi)有常數(shù)項(xiàng) 1，因?yàn)樽詈笠粋€(gè) bit 為 0。這時(shí)候，發(fā)送信息的一端和接收信息的一端就要約定一個(gè)多項(xiàng)式 G。假設(shè)按照上圖除法中的數(shù)據(jù)，我們這里使用的就是 CRC-3（一般沒(méi)有，是為了適合上圖的除式），取多項(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，然后判斷和接收到的是否相同來(lái)檢驗(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)過(guò)程中的運(yùn)算是不同的。基于此，很多行業(yè)形成固定的多項(xiàng)式，一般我們開(kāi)發(fā)時(shí)遵循他們就可以了：

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

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

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

我們用下面這個(gè)式子來(lái)看一下過(guò)程

通過(guò)上面的模擬寄存器操作，我們就得到了一個(gè)校驗(yàn)碼，理論上無(wú)論多少個(gè) bit 的數(shù)據(jù)塊，對(duì)我們 4bit 的多項(xiàng)式做除法最后都會(huì)得到一個(gè)4bit 可以存放的校驗(yàn)碼，我們就把他掛在我們的數(shù)據(jù)塊尾巴上送出去。只要發(fā)送接收到的多項(xiàng)式一致，就可以根據(jù)這個(gè)校驗(yàn)碼來(lái)進(jìn)行完整性校驗(yàn)了。這部分代碼的實(shí)現(xiàn)，我之前講過(guò)，在我的 從 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ù)長(zhǎng)度進(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)算法，看起來(lái)比較簡(jiǎn)單，移位幾次，異或幾次就可以了，但是當(dāng)我們把校驗(yàn)位數(shù)增加到 CRC32 的時(shí)候，這個(gè)算法就復(fù)雜起來(lái)，因此很多 MCU，比如 STM32 就內(nèi)置了硬件的 CRC 校驗(yàn)。多項(xiàng)式也可以自定義，使用起來(lái)還是很靈活的。如果沒(méi)有硬件幫忙，我們解決 CRC32 校驗(yàn)的問(wèn)題可以通過(guò)查表法。制作這個(gè)表的方法其實(shí)就是上面這樣的移位和異或算法。簡(jiǎn)化的寫(xiě)法如下：

unsigned int CRC;//int的大小是32位，作32位CRC寄存器unsigned int CRC_32_Table[256];//用來(lái)保存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ì)算出來(lái)了，我們的通信往往都是以字節(jié)為單位進(jìn)行傳輸?shù)?，那么我們有了這樣的表后，就相當(dāng)于直接有了一個(gè) 8bit 數(shù)及其 CRC32 校驗(yàn)碼的映射表，直接查表速度極快。以上就是對(duì) 奇偶校驗(yàn)，累加和校驗(yàn)和 CRC 校驗(yàn)的理解。