什么是 CRC（循環冗余校驗）？

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

CRCs經常被叫做“校驗和”，但是這樣的說法嚴格來說并不是準確的，因為技術上來說，校驗“和”是通過加法來計算的，而不是CRC這里的除法。

“糾錯碼”（Error–Correcting Codes，簡稱ECC）常常和CRCs緊密相關，其語序糾正在傳輸過程中所產生的錯誤。這些編碼方式常常和數學原理緊密相關。例如常見于通信或信息傳遞上BCH碼、前向錯誤更正、錯誤檢測與糾正等。

CRC簡介

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

CRC是基于有限域GF(2)（即除以2的同余）的多項式環。簡單的來說，就是所有系數都為0或1（又叫做二進制）的多項式系數的集合，并且集合對于所有的代數操作都是封閉的。例如：

2會變成0，因為對系數的加法運算都會再取2的模數。乘法也是類似的：

同樣可以對多項式作除法并且得到商和余數。例如，如果用x3 + x2 + x除以x + 1。會得到：

也就是說，

等價于：

這里除法得到了商x2 + 1和余數-1，因為是奇數所以最后一位是1。

字符串中的每一位其實就對應了這樣類型的多項式的系數。為了得到CRC，首先將其乘以xn

，這里n

是一個固定多項式的階數，然后再將其除以這個固定的多項式，余數的系數就是CRC。

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

表示了本來的信息位是111, x+1

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

來得到x3+x2+x

也可視為原來的信息位補1個零成為1110。

一般來說，其形式為：

CRC是如何計算的？

CRC的思想就是先在要發送的K比特長度的數據后面附加一個R比特長度的校驗碼，然后生成一個新幀發送給接收端。接收端接收到新幀后，根據收到的數據和校驗碼來驗證接收到的數據是否正確。

當然，這個附加的校驗碼不是隨意添加的，要使所生成的新幀能與發送端和接收端共同選定的某個特定數整除（“模2除法”）。接收端把接收到的新幀除以這個選定的除數。因為在發送數據幀之前就已通過附加一個數，做了“去余”處理（也就已經能整除了），所以結果應該是沒有余數。如果有余數，則表明該幀在傳輸過程中出現了差錯。

在K比特數據后面再拼接R比特的校驗碼，整個編碼長度為N比特，這種編碼也叫(N,K)碼。對于一個給定的(N,K)碼，可以證明存在一個最高次冪為N-K=R的多項式g(x)，根據g(x)可以生成R比特的校驗碼。其算法是以GF(2)多項式算術為數學基礎的，原理如下圖所示。

CRC計算公式 g(x)叫做這個校驗碼的生成多項式。不同的CRC生成多項式，其檢錯能力是不同的。要使用R位校驗碼，生成多項式的次冪應為R。以下為常見的一些標準多項式。

這些多項式的值便是模2除法的除數。而根據這個除數獲得校驗碼并進行校驗的原理可以分為以下幾個步驟：

發送端、接收端在通信前，約定好除數P，也就是前面說的多項式的值。P應該是R+1位長度； 發送端首先在原來的K位數據后面加R個0，相當于原來的數據左移了R位； 然后進行模2除法運算（其實就是異或XOR運算），將加0之后的K+R位的數除以P，循環計算，直到余數的階數小于R，這個余數就是附加的校驗碼，如果長度不足R位需要在前面加0補齊； 發送端將R位校驗碼附加在原數據后面發送給接收方； 接收方接收到數據后，將數據以模2除法方式除以除數P。如果沒有余數，說明在傳輸過程中沒有出現錯誤，否則說明有錯誤。 下面以一個簡單示例來展示CRC的計算過程：

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

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

計算得到的余數就是0100，也就是CRC校驗碼。將0100附加到原始數據幀10110011后，組成新幀101100110100發送給接收端。接收端接收到該幀后，會用該幀去除以上面選定的除數P，驗證余數是否為0，如果為0，則表示數據在傳輸過程中沒有出現差錯。

PY32F030 內置的 CRC 外設采用 CRC32 多項式作為公式。

示例：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();
    }
}