1、CRC簡介

CRC 是Cyclic Redundancy Check的縮寫，循環(huán)冗余校驗(yàn)，用于校驗(yàn)數(shù)據(jù)傳輸?shù)耐暾浴?一般情況下在數(shù)據(jù)發(fā)送前計算CRC校驗(yàn)值，附在發(fā)送數(shù)據(jù)之后，數(shù)據(jù)接收方也按照同樣方法計算CRC，然后對比計算結(jié)果，如果一致說明數(shù)據(jù)數(shù)據(jù)傳輸無誤，否則數(shù)據(jù)傳輸出錯。

2、什么是模二運(yùn)算

CRC計算采用二進(jìn)制模二除法，來解釋一下模二運(yùn)算，模二運(yùn)算忽略進(jìn)位和借位，下面一一解釋。

1）模二加法，類似異或運(yùn)算

1+1=0 0+0=0

1+0=1 0+1=1

2）模二減法，類似異或運(yùn)算

1-1=0 0-0=0

1-0=1 0-1=1

3）模二乘法

1×1=1 0×0=0

1×0=0 0×1=0

4）模二除法

模二除法和十進(jìn)制除法類似，運(yùn)用了模二乘法和模二減法，直接舉例說明。

3、常見CRC模型如下：

不同的多項(xiàng)式計算方法不同，下面以CRC-5/EPC舉例說明：

多項(xiàng)式公式 ：x5 + x3 + 1

完整寫出來是x5 + 0x4 + x3 + 0x2 + 0*x + 1

多項(xiàng)式 ：取以上多項(xiàng)式中的系數(shù)101001為多項(xiàng)式，一般最高位不寫出來，所以多項(xiàng)式是01001，即0x09

初始值 ：運(yùn)算的初始值，EPC要求是0x09

結(jié)果異或值 ：所有數(shù)據(jù)計算完的結(jié)果與其異或，EPC這里是0

輸入反轉(zhuǎn) ：輸入數(shù)據(jù)每字節(jié)高低位是否翻轉(zhuǎn)，EPC不翻轉(zhuǎn)。

輸出反轉(zhuǎn) ：輸出結(jié)果高低位是否翻轉(zhuǎn)，EPC不翻轉(zhuǎn)。

4、手撕CRC

仍然以CRC-5/EPC舉例，計算字節(jié)0xAA的CRC值，這是一個5位的CRC，使用模二除法，最終計算出5位CRC校驗(yàn)值。 被除數(shù)是0xAA，二進(jìn)制10101010，除數(shù)是多項(xiàng)式，即101001。 計算過程如下圖所示，為了表明計算過程把商為0的計算過程也寫出來了。 這是5位CRC，只取最后5位，即10000。 輸出結(jié)果不需要異或也不需要反轉(zhuǎn)，所以10000就是計算結(jié)果。

兩個字節(jié)AA55的CRC計算過程，同樣為了表明計算過程把商為0的計算過程也寫出來了。 這是5位CRC，只取最后5位，即01000。 輸出結(jié)果不需要異或也不需要反轉(zhuǎn)，所以01000就是計算結(jié)果。

再舉一個例子，仍然計算0xAA的CRC。 這次采用模型CRC-5/USB，多項(xiàng)式：x5+x2+1，輸入輸出數(shù)據(jù)都反轉(zhuǎn)，多項(xiàng)式0x05，初始值為0x1F，輸出異或值為0x1F。 最終計算結(jié)果00111。

5、C語言實(shí)現(xiàn)

以下是CRC-5/EPC的C語言實(shí)現(xiàn)代碼：

/*
 * Name:    CRC-5/EPC   x5+x3+1
 * Poly:    0x09
 * Init:    0x09
 * Refin:   False
 * Refout:  False
 * Xorout:  0x00
 * Note:
*/
uint8_t crc5_epc(uint8_t *data, uint16_t length)
{
    uint8_t i;

    //初始值是0x09的低5位，要和輸入數(shù)據(jù)的高五位異或
    //所以0x09左移三位，00001001<<3 = 01001000 = 0x48
    uint8_t crc = 0x48;
    while(length--)
    {
        crc ^= *data++;        //異或第一個字節(jié)
        for ( i = 0; i < 8; i++ )
        {
            if ( crc & 0x80 )
            {
                //最高位是1，需要異或多項(xiàng)式，多項(xiàng)式是最高位為1的6bit
                //多項(xiàng)式異或后最高位為0，所以這里不異或最高位了，他肯定是0
                //直接把crc左移1位，去掉最高位，然后異或多項(xiàng)式的低5bit
                //多項(xiàng)式是0x09<<3 = 00001001<<3 = 01001000 = 0x48
                crc = (crc << 1) ^ 0x48;        // 0x48 = 0x09<<(8-5)
            }
            else
            {
                //最高位是0，所以商為0，可以省去運(yùn)算，見上面圖表，因?yàn)楹?異或值不變。
                crc <<= 1;
            }

        }
    }
    return crc >> 3;    //計算完成后結(jié)果在高5位，右移動3位。
}