淺談通信校驗碼及CRC校驗

一、信息論中的 CRC

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

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

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

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

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

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

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

什么是模 2 除法求余呢？

多項式中的加減法，使用模2算術(shù)執(zhí)行對應(yīng)項上系數(shù)的加減，模2就是指的加減時不考慮進(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ī)律可以得出，這種加減法的運算正好等同于我們計算機(jī)中的異或運算，數(shù)學(xué)理論是基礎(chǔ)，我們這里可以記住異或運算就好了。多項式乘法和一般多項式乘法也是一樣的，只是在各項相加的時候按模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 次冪的項省略掉。

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

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

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

我們?nèi)绾斡贸绦騺碛嬎氵@個CRC 的除法呢？

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

我們用下面這個式子來看一下過程

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

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

2024-02-26

文章里面講到，TI 規(guī)定的 CRC8 的多項式為：x^8 + x^2 + x +1，對應(yīng)可知多項式 G 的 Key 為100000111。由于我們在算法中是先左移再做異或，因此最高位可以去掉，對應(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計算    {        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++; //下一個字節(jié)    }    return(crc);}

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

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;//采取反向校驗           else //0xEDB88320就是CRC-32多項表達(dá)式的reversed值            CRC>>=1;         }     CRC_32_Table[i]=CRC;  }}

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