什么是 CRC（循環(huán)冗余校驗(yàn)）？

循環(huán)冗余校驗(yàn)（英語(yǔ)：Cyclic redundancy check，通稱(chēng)“CRC”）是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包或電腦文件等數(shù)據(jù)產(chǎn)生簡(jiǎn)短固定位數(shù)校驗(yàn)碼的一種散列函數(shù)，主要用來(lái)檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。生成的數(shù)字在傳輸或者存儲(chǔ)之前計(jì)算出來(lái)并且附加到數(shù)據(jù)后面，然后接收方進(jìn)行檢驗(yàn)確定數(shù)據(jù)是否發(fā)生變化。由于本函數(shù)易于用二進(jìn)制的電腦硬件使用、容易進(jìn)行數(shù)學(xué)分析并且尤其善于檢測(cè)傳輸通道干擾引起的錯(cuò)誤，因此獲得廣泛應(yīng)用。此方法是由W. Wesley Peterson于1961年發(fā)表。

CRCs經(jīng)常被叫做“校驗(yàn)和”，但是這樣的說(shuō)法嚴(yán)格來(lái)說(shuō)并不是準(zhǔn)確的，因?yàn)榧夹g(shù)上來(lái)說(shuō)，校驗(yàn)“和”是通過(guò)加法來(lái)計(jì)算的，而不是CRC這里的除法。

“糾錯(cuò)碼”（Error–Correcting Codes，簡(jiǎn)稱(chēng)ECC）常常和CRCs緊密相關(guān)，其語(yǔ)序糾正在傳輸過(guò)程中所產(chǎn)生的錯(cuò)誤。這些編碼方式常常和數(shù)學(xué)原理緊密相關(guān)。例如常見(jiàn)于通信或信息傳遞上BCH碼、前向錯(cuò)誤更正、錯(cuò)誤檢測(cè)與糾正等。

CRC簡(jiǎn)介

CRC是兩個(gè)字節(jié)數(shù)據(jù)流采用二進(jìn)制除法（沒(méi)有進(jìn)位，使用XOR來(lái)代替減法）相除所得到的余數(shù)。其中被除數(shù)是需要計(jì)算校驗(yàn)和的信息數(shù)據(jù)流的二進(jìn)制表示；除數(shù)是一個(gè)長(zhǎng)度為（n+1）(n+1)的預(yù)定義（短）的二進(jìn)制數(shù)，通常用多項(xiàng)式的系數(shù)來(lái)表示。在做除法之前，要在信息數(shù)據(jù)之后先加上nn個(gè)0。

CRC是基于有限域GF(2)（即除以2的同余）的多項(xiàng)式環(huán)。簡(jiǎn)單的來(lái)說(shuō)，就是所有系數(shù)都為0或1（又叫做二進(jìn)制）的多項(xiàng)式系數(shù)的集合，并且集合對(duì)于所有的代數(shù)操作都是封閉的。例如：

2會(huì)變成0，因?yàn)閷?duì)系數(shù)的加法運(yùn)算都會(huì)再取2的模數(shù)。乘法也是類(lèi)似的：

同樣可以對(duì)多項(xiàng)式作除法并且得到商和余數(shù)。例如，如果用x3 + x2 + x除以x + 1。會(huì)得到：

也就是說(shuō)，

等價(jià)于：

這里除法得到了商x2 + 1和余數(shù)-1，因?yàn)槭瞧鏀?shù)所以最后一位是1。

字符串中的每一位其實(shí)就對(duì)應(yīng)了這樣類(lèi)型的多項(xiàng)式的系數(shù)。為了得到CRC，首先將其乘以xn

，這里n

是一個(gè)固定多項(xiàng)式的階數(shù)，然后再將其除以這個(gè)固定的多項(xiàng)式，余數(shù)的系數(shù)就是CRC。

在上面的等式中，x2+x+1

表示了本來(lái)的信息位是111, x+1

x+1 是所謂的鑰匙，而余數(shù)11就是CRC. key的最高次為1,所以將原來(lái)的信息乘上x1

來(lái)得到x3+x2+x

也可視為原來(lái)的信息位補(bǔ)1個(gè)零成為1110。

一般來(lái)說(shuō)，其形式為：

CRC是如何計(jì)算的？

CRC的思想就是先在要發(fā)送的K比特長(zhǎng)度的數(shù)據(jù)后面附加一個(gè)R比特長(zhǎng)度的校驗(yàn)碼，然后生成一個(gè)新幀發(fā)送給接收端。接收端接收到新幀后，根據(jù)收到的數(shù)據(jù)和校驗(yàn)碼來(lái)驗(yàn)證接收到的數(shù)據(jù)是否正確。

當(dāng)然，這個(gè)附加的校驗(yàn)碼不是隨意添加的，要使所生成的新幀能與發(fā)送端和接收端共同選定的某個(gè)特定數(shù)整除（“模2除法”）。接收端把接收到的新幀除以這個(gè)選定的除數(shù)。因?yàn)樵诎l(fā)送數(shù)據(jù)幀之前就已通過(guò)附加一個(gè)數(shù)，做了“去余”處理（也就已經(jīng)能整除了），所以結(jié)果應(yīng)該是沒(méi)有余數(shù)。如果有余數(shù)，則表明該幀在傳輸過(guò)程中出現(xiàn)了差錯(cuò)。

在K比特?cái)?shù)據(jù)后面再拼接R比特的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N比特，這種編碼也叫(N,K)碼。對(duì)于一個(gè)給定的(N,K)碼，可以證明存在一個(gè)最高次冪為N-K=R的多項(xiàng)式g(x)，根據(jù)g(x)可以生成R比特的校驗(yàn)碼。其算法是以GF(2)多項(xiàng)式算術(shù)為數(shù)學(xué)基礎(chǔ)的，原理如下圖所示。

CRC計(jì)算公式 g(x)叫做這個(gè)校驗(yàn)碼的生成多項(xiàng)式。不同的CRC生成多項(xiàng)式，其檢錯(cuò)能力是不同的。要使用R位校驗(yàn)碼，生成多項(xiàng)式的次冪應(yīng)為R。以下為常見(jiàn)的一些標(biāo)準(zhǔn)多項(xiàng)式。

這些多項(xiàng)式的值便是模2除法的除數(shù)。而根據(jù)這個(gè)除數(shù)獲得校驗(yàn)碼并進(jìn)行校驗(yàn)的原理可以分為以下幾個(gè)步驟：

發(fā)送端、接收端在通信前，約定好除數(shù)P，也就是前面說(shuō)的多項(xiàng)式的值。P應(yīng)該是R+1位長(zhǎng)度； 發(fā)送端首先在原來(lái)的K位數(shù)據(jù)后面加R個(gè)0，相當(dāng)于原來(lái)的數(shù)據(jù)左移了R位； 然后進(jìn)行模2除法運(yùn)算（其實(shí)就是異或XOR運(yùn)算），將加0之后的K+R位的數(shù)除以P，循環(huán)計(jì)算，直到余數(shù)的階數(shù)小于R，這個(gè)余數(shù)就是附加的校驗(yàn)碼，如果長(zhǎng)度不足R位需要在前面加0補(bǔ)齊； 發(fā)送端將R位校驗(yàn)碼附加在原數(shù)據(jù)后面發(fā)送給接收方； 接收方接收到數(shù)據(jù)后，將數(shù)據(jù)以模2除法方式除以除數(shù)P。如果沒(méi)有余數(shù)，說(shuō)明在傳輸過(guò)程中沒(méi)有出現(xiàn)錯(cuò)誤，否則說(shuō)明有錯(cuò)誤。 下面以一個(gè)簡(jiǎn)單示例來(lái)展示CRC的計(jì)算過(guò)程：

以g(x)為CRC-4=X4+X+1為例，此時(shí)除數(shù)P=10011。假設(shè)源數(shù)據(jù)M為10110011。

在發(fā)送端將M左移4位，然后除以P。

計(jì)算得到的余數(shù)就是0100，也就是CRC校驗(yàn)碼。將0100附加到原始數(shù)據(jù)幀10110011后，組成新幀101100110100發(fā)送給接收端。接收端接收到該幀后，會(huì)用該幀去除以上面選定的除數(shù)P，驗(yàn)證余數(shù)是否為0，如果為0，則表示數(shù)據(jù)在傳輸過(guò)程中沒(méi)有出現(xiàn)差錯(cuò)。

PY32F030 內(nèi)置的 CRC 外設(shè)采用 CRC32 多項(xiàng)式作為公式。

示例：examples/crc.rs

#![no_std]
#![no_main]

use embassy_executor::Spawner;
use py32f030_hal::crc::Crc;
use py32f030_hal::{selfas hal};

use {defmt_rtt as _, panic_probe as _};

#[embassy_executor::main]
asyncfn main(_spawner: Spawner) {
    let p = hal::init(Default::default());

    let crc = Crc::new(p.CRC);

    let buf1 = [
        0x00001021, 0x20423063, 0x408450a5, 0x60c670e7, 0x9129a14a, 0xb16bc18c, 0xd1ade1ce,
        0xf1ef1231, 0x32732252, 0x52b54294, 0x72f762d6, 0x93398318, 0xa35ad3bd, 0xc39cf3ff,
        0xe3de2462, 0x34430420, 0x64e674c7, 0x44a45485, 0xa56ab54b, 0x85289509, 0xf5cfc5ac,
        0xd58d3653, 0x26721611, 0x063076d7, 0x569546b4, 0xb75ba77a, 0x97198738, 0xf7dfe7fe,
        0xc7bc48c4, 0x58e56886, 0x78a70840, 0x18612802, 0xc9ccd9ed, 0xe98ef9af, 0x89489969,
        0xa90ab92b, 0x4ad47ab7, 0x6a961a71, 0x0a503a33, 0x2a12dbfd, 0xfbbfeb9e, 0x9b798b58,
        0xbb3bab1a, 0x6ca67c87, 0x5cc52c22, 0x3c030c60, 0x1c41edae, 0xfd8fcdec, 0xad2abd0b,
        0x8d689d49, 0x7e976eb6, 0x5ed54ef4, 0x2e321e51, 0x0e70ff9f, 0xefbedfdd, 0xcffcbf1b,
        0x9f598f78, 0x918881a9, 0xb1caa1eb, 0xd10cc12d, 0xe16f1080, 0x00a130c2, 0x20e35004,
        0x40257046, 0x83b99398, 0xa3fbb3da, 0xc33dd31c, 0xe37ff35e, 0x129022f3, 0x32d24235,
        0x52146277, 0x7256b5ea, 0x95a88589, 0xf56ee54f, 0xd52cc50d, 0x34e224c3, 0x04817466,
        0x64475424, 0x4405a7db, 0xb7fa8799, 0xe75ff77e, 0xc71dd73c, 0x26d336f2, 0x069116b0,
        0x76764615, 0x5634d94c, 0xc96df90e, 0xe92f99c8, 0xb98aa9ab, 0x58444865, 0x78066827,
        0x18c008e1, 0x28a3cb7d, 0xdb5ceb3f, 0xfb1e8bf9, 0x9bd8abbb, 0x4a755a54, 0x6a377a16,
        0x0af11ad0, 0x2ab33a92, 0xed0fdd6c, 0xcd4dbdaa, 0xad8b9de8, 0x8dc97c26, 0x5c644c45,
        0x3ca22c83, 0x1ce00cc1, 0xef1fff3e, 0xdf7caf9b, 0xbfba8fd9, 0x9ff86e17, 0x7e364e55,
        0x2e933eb2, 0x0ed11ef0,
    ];

    assert_eq!(crc.calculate(&buf1), 0x379E9F06);

    defmt::info!("{:x}", crc.calculate(&buf1));
    crc.reset();

    crc.accumulat(&buf1[0..10]);
    let rst = crc.accumulat(&buf1[10..]);
    defmt::info!("{:x}", rst);

    loop {
        cortex_m::asm::wfe();
    }
}