CRC校驗(yàn)原來這么簡(jiǎn)單！
由于公眾號(hào)申請(qǐng)的時(shí)間比較晚，所以沒有留言互動(dòng)功能，最近公眾號(hào)上線了讀者討論功能，和留言差不多，對(duì)本篇文章有什么感想的都可以到文章末尾留言評(píng)論。
目錄
前言
CRC算法簡(jiǎn)介
CRC計(jì)算
CRC校驗(yàn)
CRC計(jì)算的C語言實(shí)現(xiàn)
CRC計(jì)算工具
總結(jié)
前言
最近的工作中，要實(shí)現(xiàn)對(duì)通信數(shù)據(jù)的CRC計(jì)算，所以花了兩天的時(shí)間好好研究了一下，周末有時(shí)間整理了一下筆記。
一個(gè)完整的數(shù)據(jù)幀通常由以下部分構(gòu)成：
校驗(yàn)位是為了保證數(shù)據(jù)在傳輸過程中的完整性，采用一種指定的算法對(duì)原始數(shù)據(jù)進(jìn)行計(jì)算，得出的一個(gè)校驗(yàn)值。接收方接收到數(shù)據(jù)時(shí)，采用同樣的校驗(yàn)算法對(duì)原始數(shù)據(jù)進(jìn)行計(jì)算，如果計(jì)算結(jié)果和接收到的校驗(yàn)值一致，說明數(shù)據(jù)校驗(yàn)正確，這一幀數(shù)據(jù)可以使用，如果不一致，說明傳輸過程中出現(xiàn)了差錯(cuò)，這一幀數(shù)據(jù)丟棄，請(qǐng)求重發(fā)。
常用的校驗(yàn)算法有奇偶校驗(yàn)、校驗(yàn)和、CRC，還有LRC、BCC等不常用的校驗(yàn)算法。
以串口通訊中的奇校驗(yàn)為例，如果數(shù)據(jù)中1的個(gè)數(shù)為奇數(shù)，則奇校驗(yàn)位0，否則為1。
例如原始數(shù)據(jù)為：0001 0011，數(shù)據(jù)中1的個(gè)數(shù)（或各位相加）為3，所以奇校驗(yàn)位為0。這種校驗(yàn)方法很簡(jiǎn)單，但這種校驗(yàn)方法有很大的誤碼率。假設(shè)由于傳輸過程中的干擾，接收端接收到的數(shù)據(jù)是0010 0011，通過奇校驗(yàn)運(yùn)算，得到奇校驗(yàn)位的值為0，雖然校驗(yàn)通過，但是數(shù)據(jù)已經(jīng)發(fā)生了錯(cuò)誤。
校驗(yàn)和同理也會(huì)有類似的錯(cuò)誤：
一個(gè)好的校驗(yàn)校驗(yàn)方法，配合數(shù)字信號(hào)編碼方式，如(差分)曼徹斯特編碼，(不)歸零碼等對(duì)數(shù)據(jù)進(jìn)行編碼，可大大提高通信的健壯性和穩(wěn)定性。例如以太網(wǎng)中使用的是CRC-32校驗(yàn)，曼徹斯特編碼方式。本篇文章介紹CRC校驗(yàn)的原理和實(shí)現(xiàn)方法。
CRC算法簡(jiǎn)介
循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check， CRC）是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包或計(jì)算機(jī)文件等數(shù)據(jù)產(chǎn)生簡(jiǎn)短固定位數(shù)校驗(yàn)碼的一種信道編碼技術(shù)，主要用來檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。它是利用除法及余數(shù)的原理來作錯(cuò)誤偵測(cè)的。
CRC校驗(yàn)計(jì)算速度快，檢錯(cuò)能力強(qiáng)，易于用編碼器等硬件電路實(shí)現(xiàn)。從檢錯(cuò)的正確率與速度、成本等方面，都比奇偶校驗(yàn)等校驗(yàn)方式具有優(yōu)勢(shì)。因而，CRC 成為計(jì)算機(jī)信息通信領(lǐng)域最為普遍的校驗(yàn)方式。常見應(yīng)用有以太網(wǎng)/USB通信，壓縮解壓，視頻編碼，圖像存儲(chǔ)，磁盤讀寫等。
CRC參數(shù)模型
不知道你是否遇到過這種情況，同樣的CRC多項(xiàng)式，調(diào)用不同的CRC計(jì)算函數(shù)，得到的結(jié)果卻不一樣，而且和手算的結(jié)果也不一樣，這就涉及到CRC的參數(shù)模型了。計(jì)算一個(gè)正確的CRC值，需要知道CRC的參數(shù)模型。
一個(gè)完整的CRC參數(shù)模型應(yīng)該包含以下信息：WIDTH，POLY，INIT，REFIN，REFOUT，XOROUT。
NAME：參數(shù)模型名稱。
WIDTH：寬度，即生成的CRC數(shù)據(jù)位寬，如CRC-8，生成的CRC為8位
POLY：十六進(jìn)制多項(xiàng)式，省略最高位1，如 x8 + x2 + x + 1，二進(jìn)制為1 0000 0111，省略最高位1，轉(zhuǎn)換為十六進(jìn)制為0x07。
INIT：CRC初始值，和WIDTH位寬一致。
REFIN：true或false，在進(jìn)行計(jì)算之前，原始數(shù)據(jù)是否翻轉(zhuǎn)，如原始數(shù)據(jù)：0x34 = 0011 0100，如果REFIN為true，進(jìn)行翻轉(zhuǎn)之后為0010 1100 = 0x2c
REFOUT：true或false，運(yùn)算完成之后，得到的CRC值是否進(jìn)行翻轉(zhuǎn)，如計(jì)算得到的CRC值：0x97 = 1001 0111，如果REFOUT為true，進(jìn)行翻轉(zhuǎn)之后為11101001 = 0xE9。
XOROUT：計(jì)算結(jié)果與此參數(shù)進(jìn)行異或運(yùn)算后得到最終的CRC值，和WIDTH位寬一致。
通常如果只給了一個(gè)多項(xiàng)式，其他的沒有說明則：INIT=0x00，REFIN=false，REFOUT=false，XOROUT=0x00。
常用的21個(gè)標(biāo)準(zhǔn)CRC參數(shù)模型：
CRC校驗(yàn)在電子通信領(lǐng)域非常常用，可以說有通信存在的地方，就有CRC校驗(yàn)：
美信(MAXIM)的芯片DS2401/DS18B20，都是使用的CRC-8/MAXIM模型
SD卡或MMC使用的是CRC-7/MMC模型
Modbus通信使用的是CRC-16/MODBUS參數(shù)模型
USB協(xié)議中使用的CRC-5/USB和CRC-16/USB模型
STM32自帶的硬件CRC計(jì)算模塊使用的是CRC-32模型
至于多項(xiàng)式的選擇，初始值和異或值的選擇，輸入輸出是否翻轉(zhuǎn)，這就涉及到一定的編碼和數(shù)學(xué)知識(shí)了。感興趣的朋友，可以了解一下每個(gè)CRC模型各個(gè)參數(shù)的來源。至于每種參數(shù)模型的檢錯(cuò)能力、重復(fù)率，需要專業(yè)的數(shù)學(xué)計(jì)算了，不在本文討論的范疇內(nèi)。
CRC計(jì)算
好了，了解了CRC參數(shù)模型知識(shí)，下面手算一個(gè)CRC值，來了解CRC計(jì)算的原理。
問：原始數(shù)據(jù)：0x34，使用CRC-8/MAXIN參數(shù)模型，求CRC值？
答：根據(jù)CRC參數(shù)模型表，得到CRC-8/MAXIN的參數(shù)如下：
POLY = 0x31 = 0011 0001(最高位1已經(jīng)省略)
INIT = 0x00
XOROUT = 0x00
REFIN = TRUE
REFOUT = TRUE
有了上面的參數(shù)，這樣計(jì)算條件才算完整，下面來實(shí)際計(jì)算：
0.原始數(shù)據(jù) = 0x34 = 0011 0100，多項(xiàng)式 = 0x31 = 1 0011 0001
1.INIT = 00，原始數(shù)據(jù)高8位和初始值進(jìn)行異或運(yùn)算保持不變。
2.REFIN為TRUE，需要先對(duì)原始數(shù)據(jù)進(jìn)行翻轉(zhuǎn)：0011 0100 > 0010 1100
3.原始數(shù)據(jù)左移8位，即后面補(bǔ)8個(gè)0：0010 1100 0000 0000
4.把處理之后的數(shù)據(jù)和多項(xiàng)式進(jìn)行模2除法，求得余數(shù)：
原始數(shù)據(jù)：0010 1100 0000 0000 = 10 1100 0000 0000
多項(xiàng)式：1 0011 0001
模2除法取余數(shù)低8位：1111 1011
5.與XOROUT進(jìn)行異或，1111 1011 xor 0000 0000 = 1111 1011
6.因?yàn)镽EFOUT為TRUE，對(duì)結(jié)果進(jìn)行翻轉(zhuǎn)得到最終的CRC-8值：1101 1111 = 0xDF
7.數(shù)據(jù)+CRC：0011 0100 1101 1111 = 34DF，相當(dāng)于原始數(shù)據(jù)左移8位+余數(shù)。
模2除法求余數(shù)：
驗(yàn)證手算結(jié)果：
可以看出是一致的，當(dāng)你手算的結(jié)果和工具計(jì)算結(jié)果不一致時(shí)，可以看看INIT，XOROUT，REFINT，REFOUT這些參數(shù)是否一致，有1個(gè)參數(shù)不對(duì)，計(jì)算出的CRC結(jié)果都不一樣。
CRC校驗(yàn)
上面通過筆算的方式，講解了CRC計(jì)算的原理，下面來介紹一下如何進(jìn)行校驗(yàn)。
按照上面CRC計(jì)算的結(jié)果，最終的數(shù)據(jù)幀：0011 0100 1101 1111 = 34DF，前8位0011 0100是原始數(shù)據(jù)，后8位1101 1111 是 CRC結(jié)果。
接收端的校驗(yàn)有兩種方式，一種是和CRC計(jì)算一樣，在本地把接收到的數(shù)據(jù)和CRC分離，然后在本地對(duì)數(shù)據(jù)進(jìn)行CRC運(yùn)算，得到的CRC值和接收到的CRC進(jìn)行比較，如果一致，說明數(shù)據(jù)接收正確，如果不一致，說明數(shù)據(jù)有錯(cuò)誤。
另一種方法是把整個(gè)數(shù)據(jù)幀進(jìn)行CRC運(yùn)算，因?yàn)槭菙?shù)據(jù)幀相當(dāng)于把原始數(shù)據(jù)左移8位，然后加上余數(shù)，如果直接對(duì)整個(gè)數(shù)據(jù)幀進(jìn)行CRC運(yùn)算（除以多項(xiàng)式），那么余數(shù)應(yīng)該為0，如果不為0說明數(shù)據(jù)出錯(cuò)。
而且，不同位出錯(cuò)，余數(shù)也不同，可以證明，余數(shù)與出錯(cuò)位數(shù)的對(duì)應(yīng)關(guān)系只與CRC參數(shù)模型有關(guān)，而與原始數(shù)據(jù)無關(guān)。
CRC計(jì)算的C語言實(shí)現(xiàn)
無論是用C還是其他語言，實(shí)現(xiàn)方法網(wǎng)上很多，這里我找了一個(gè)基于C語言的CRC計(jì)算庫，里面包含了常用的21個(gè)CRC參數(shù)模型計(jì)算函數(shù)，可以直接使用，只有crcLib.c和crcLib.h兩個(gè)文件。
GitHub地址：https://github.com/whik/crc-lib-c
使用方法非常簡(jiǎn)單：
#include
#include
#include "crcLib.h"
int main()
{
? ?uint8_t LENGTH = 10;
? ?uint8_t data[LENGTH];
? ?uint8_t crc;
? ?for(int i = 0; i < LENGTH; i++)
? {
? ? ? ?data[i] = i*5;
? ? ? ?printf("%02x ", data[i]);
? }
? ?printf("\n");
? ?crc = crc8_maxim(data, LENGTH);
? ?printf("CRC-8/MAXIM:%02x\n", crc);
? ?return 0;
}
計(jì)算結(jié)果：
CRC計(jì)算工具
下面這幾款工具都可以自定義CRC算法模型，而且都有標(biāo)準(zhǔn)CRC模型可供選擇。如果自己用C語言或者Verilog實(shí)現(xiàn)校驗(yàn)算法時(shí)，非常適合作為標(biāo)準(zhǔn)答案進(jìn)行驗(yàn)證。
在線計(jì)算：www.ip33.com/crc.html
離線計(jì)算工具：CRC_Calc v0.1.exe或者GCRC.exe
格西CRC計(jì)算器：
公眾號(hào)后臺(tái)回復(fù)【CRC】，獲取以上兩款CRC計(jì)算工具的下載鏈接。
總結(jié)
CRC校驗(yàn)并不能100%的檢查出數(shù)據(jù)的錯(cuò)誤，非常低的概率會(huì)出現(xiàn)CRC校驗(yàn)正確但數(shù)據(jù)中有錯(cuò)誤位的情況。這和CRC的位數(shù)，多項(xiàng)式的選擇等等有很大的關(guān)系，所以在實(shí)際使用中盡量選擇標(biāo)準(zhǔn)CRC參數(shù)模型，這些多項(xiàng)式參數(shù)都是經(jīng)過理論計(jì)算得出的，可以提高CRC的檢錯(cuò)能力。CRC校驗(yàn)可以檢錯(cuò)，也可以糾正單一比特的錯(cuò)誤，你知道糾錯(cuò)的原理嗎？
參考資料
www.cnblogs.com/liushui-sky/p/9962123.html
segmentfault.com/a/1190000018094567
推薦閱讀
[踩坑]CMOS器件輸入管腳不能懸空？
[開源]基于STM32F103的疫情監(jiān)控平臺(tái)（RT-Thread）
[開源]基于Qt+STM32MP1的疫情監(jiān)控平臺(tái)
[踩坑]STM32外部8M晶體不起振會(huì)有什么現(xiàn)象？
我的博客：www.wangchaochao.top
我的公眾號(hào)：mcu149
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
