如何使用CRC算法檢查數(shù)據(jù)傳輸?shù)恼_性

還有半個(gè)多月就要過(guò)年了，工作之后時(shí)間過(guò)得真是飛快啊，才剛剛熟悉在各種文件上簽2018的日期，現(xiàn)在竟然又變成2019了。最郁悶的是又老了一歲，找誰(shuí)說(shuō)理去

大家都知道芯片有輸入輸出，根據(jù)不同的傳輸協(xié)議，輸入輸出的數(shù)據(jù)有可能是一串長(zhǎng)長(zhǎng)的數(shù)據(jù)，幾十個(gè)或者幾百個(gè)byte甚至更多。在數(shù)據(jù)傳輸過(guò)程中，由于某些意外的原因?qū)е履承゜it出現(xiàn)錯(cuò)誤（0變?yōu)?，或者1變?yōu)?)，從而接受方接收到錯(cuò)誤的數(shù)據(jù)。

為盡量提高接受方收到數(shù)據(jù)的正確率，在接收方接收數(shù)據(jù)后需要對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)，當(dāng)且僅當(dāng)校驗(yàn)的結(jié)果為正確時(shí)接收方才真正收下數(shù)據(jù)。循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check, CRC)算法通常用于數(shù)字傳輸系統(tǒng)或者存儲(chǔ)器中，用來(lái)檢測(cè)意外事件對(duì)原數(shù)據(jù)的影響，判斷接受到的數(shù)據(jù)是否正確。

下面是IC君文武雙全的朋友文武寫的CRC文章，IC君稍微做了優(yōu)化排版和少量的編輯工作提升大家的閱讀體驗(yàn)。

1

前言：

因?yàn)镃RC循環(huán)冗余校驗(yàn)碼的算法和硬件電路結(jié)構(gòu)比較簡(jiǎn)單，所以CRC是一種在工程中常用的數(shù)據(jù)校驗(yàn)方法。盡管CRC簡(jiǎn)單，但在工程應(yīng)用中還是有些問(wèn)題會(huì)對(duì)工程師產(chǎn)生困惑。這篇文章將從以下三個(gè)方面介紹以下CRC，希望對(duì)大家有所幫助。

CRC 的數(shù)學(xué)原理；

CRC的通項(xiàng)公式，怎樣選取一個(gè)適合的通項(xiàng)公式；

CRC 硬件電路實(shí)現(xiàn)，串行電路到并行電路的實(shí)現(xiàn)。

2

CRC的數(shù)學(xué)原理：

在講CRC的數(shù)學(xué)原理之前，首先看一下下面的圖。圖1是A要給B發(fā)送1bit的信息0或者1。假設(shè)A發(fā)

圖1

送一個(gè)0給B,系統(tǒng)正常的情況下B會(huì)接受到一個(gè)0。但是如果有個(gè)干擾（比如信號(hào)線的串?dāng)_）在A和B相連的傳輸線上，那么B就有可能接受到一個(gè)1，傳輸數(shù)據(jù)發(fā)生錯(cuò)誤。

為了改進(jìn)這個(gè)傳輸過(guò)程，A和B約定(圖2)。

圖2

如果A要發(fā)送一個(gè)0給B，A就在一段時(shí)間連續(xù)發(fā)送兩個(gè)0（2’b00’）給B；

如果A要發(fā)送一個(gè)1信息給B，那么A就在一段時(shí)間連續(xù)發(fā)送兩個(gè)1（2’b11’）給B。

如果B接受了一個(gè)2’b01或者2’b10，B就知道他們之間有干擾；

要是B接受到了一個(gè)2’b00，B就會(huì)認(rèn)為A發(fā)送的信息是個(gè)0；

那么A有沒(méi)有可能發(fā)的信息是2個(gè)1？這也是有可能的，不過(guò)2’b00變成2’b11比1’b0變成1’b1的概率要低的多。

如果A和B約定以圖3的方式進(jìn)行傳輸，假設(shè)A要發(fā)送一個(gè)0給B，那么A就在一段時(shí)間連續(xù)發(fā)送3個(gè)0（3’b000）給B；如果A要發(fā)送一個(gè)1信息給B，那么A就在一段時(shí)間連續(xù)發(fā)送三個(gè)1（3’b111’）給B；

如果B接受到的值為3’b001、3’b010或者3’b100，B就知道他們之間有干擾，

圖3

并且B會(huì)自我判斷A給自己發(fā)送的信息是0不是1。這種判斷是合理的，因?yàn)檎`判的概率很低。

圖1，圖2，圖3可以概括成圖4。

圖4 箭頭上的數(shù)字是海明距（HD）

海明距離HD的定義

兩個(gè)碼字的對(duì)應(yīng)比特值不同（異或）的總數(shù)目稱為這兩個(gè)碼字的海明距離。一個(gè)有效編碼集中,任意兩個(gè)碼字的海明距離的最小值稱為該編碼集的海明距離。

圖4的第一種情況就是沒(méi)有編碼，0和1的碼距（HD海明距）是1；

第二種情況其實(shí)就是奇偶校驗(yàn)，碼距是2，可以檢測(cè)1個(gè)錯(cuò)誤；

第三種情況就是糾錯(cuò)碼了，海明距是3，如果出現(xiàn)了1個(gè)錯(cuò)誤是可以自己糾錯(cuò)的，出現(xiàn)小于3個(gè)錯(cuò)誤可以檢測(cè)。

第三種情況的有效碼字000，其中0是信息位，00是校驗(yàn)位，2位的校驗(yàn)碼來(lái)確定一位數(shù)據(jù)位，看上去有點(diǎn)太浪費(fèi)了。

一種編碼的校驗(yàn)和糾錯(cuò)能力取決于它的海明距離。為檢測(cè)出d比特錯(cuò)，需要使用碼距d+1的編碼；因?yàn)閐個(gè)單比特錯(cuò)決不可能將一個(gè)有效的碼字轉(zhuǎn)變成另一個(gè)有效的碼字。當(dāng)接收方看到無(wú)效的碼字，它就能明白發(fā)生傳輸錯(cuò)誤。

同樣，為了糾正d比特錯(cuò)，必須使用碼距為2d+1的編碼，這是因?yàn)橛行Тa字的距離遠(yuǎn)到即使發(fā)生d個(gè)變化，這個(gè)發(fā)生了變化的碼字仍然比其它碼字都接近原始碼字。

通過(guò)上面的例子大家理解了碼字(CODEWORD)，信息位(DATA)，校驗(yàn)位(CHECK SUM)，海明距(HD)等概念。

下面看一看圖5的CRC計(jì)算過(guò)程

圖5（來(lái)自wikipedia）

CRC在數(shù)學(xué)上就是除余運(yùn)算，除數(shù)是個(gè)通項(xiàng)公式（固定數(shù)）,

例如G(X)=X3+X+1 （1011），

被除數(shù)11010011101100，除數(shù)1011

DATA=11010011101100，

最終得到的余數(shù) CHECK SUM=100，

所以需要傳輸?shù)腃ODEWORD=11010011101100100。

用上面CRC算法作為A和B的通信協(xié)議，傳輸數(shù)據(jù)只添加了3bit的checksum，編碼效率比圖2、圖3提高不少。但是編碼和解碼算法會(huì)變復(fù)雜，所以有得必有失吧。

具體傳輸過(guò)程如下：

A發(fā)送DATA=11010011101100給B，

發(fā)送之前先編碼

假設(shè)初始CODEWORD=11010011101100000

對(duì)G(X)=X3+X+1 （1011）除余數(shù)，

最后用初始DATA加上CHECK SUM=100得到最終發(fā)送：

CODEWORD=11010011101100100。

在B接受到CODEWORD 通過(guò)解碼來(lái)檢查A的發(fā)送有沒(méi)有錯(cuò)。

解碼的過(guò)程：

用CODEWORD=11010011101100100對(duì)G(X)=X3+X+1 （1011）除余數(shù)，如果余數(shù)等于0即CHECK SUM=000，就認(rèn)為B接受到的數(shù)據(jù)就沒(méi)有問(wèn)題。

圖6

余數(shù)等于0，就一定沒(méi)有出錯(cuò)嗎？當(dāng)然不是，只能說(shuō)出錯(cuò)的概率很低。這個(gè)可靠性跟CRC的G(X)通項(xiàng)公式和信息位的長(zhǎng)度相關(guān)；

怎樣選取一個(gè)適合的CRC通項(xiàng)公式呢？

CRC通項(xiàng)公式（生成多項(xiàng)式）很容易找到，網(wǎng)上隨便一搜就會(huì)有很多。

圖7（來(lái)自wikipedia）

生成多項(xiàng)式有很多表示方法，CRC3多項(xiàng)式表示法G(X)=X3+X+1；數(shù)字表示法0x3、0x6、0x5等。數(shù)字表示法簡(jiǎn)潔，在用軟件語(yǔ)言實(shí)現(xiàn)CRC算法時(shí)常用。

提醒一下：當(dāng)看到代碼poly=0x03，很難知道多項(xiàng)式是什么？因?yàn)閿?shù)字表示法沒(méi)有統(tǒng)一的定義，容易產(chǎn)生歧義。建議寫數(shù)字表示的時(shí)候附上多項(xiàng)式，這樣不會(huì)產(chǎn)生誤會(huì)；程序變量poly=0x03，最好后面是注釋G(X)=X3+X+1。

下面總結(jié)一下數(shù)字表示法圖8，CRC的最高位和最低位系數(shù)都有。這些表示法無(wú)非就是順序排列丟掉高位或者低位；或者逆序排列丟掉高位或者低位。

圖8

數(shù)字表示法這樣定義是為了遵循CRC的研究者的習(xí)慣。

CRC多項(xiàng)式的檢錯(cuò)能力其實(shí)有很多研究成果，這里以koopman phail舉例，因?yàn)榭梢栽谧髡叩膫€(gè)人主頁(yè)上找到一些算好的數(shù)據(jù)。作者還是美國(guó)著名的卡內(nèi)基梅隆大學(xué)的Associate Porofesor。

在講他的成果之前，先還是給出一下一些概念。用圖6的CRC3的多項(xiàng)式 G(X)=X3+X+1編碼：

DATA=11010011101100，

CHECK SUM=100，

CODEWORD=11010011101100100。CRC3就3個(gè)校驗(yàn)位最多也就8個(gè)狀態(tài)，要編碼的DATA=11010011101100有14位，總共就有2^14種可能的接受DATA，這么多的DATA肯定有很多校驗(yàn)位是相同的。

校驗(yàn)位CHECK SUM=100的DATA變成相同校驗(yàn)位但是數(shù)據(jù)不同的DATA1，在接受端是沒(méi)有辦法知道出錯(cuò)了的。所以koopman phail就把“幾乎所有的多項(xiàng)式”做了統(tǒng)計(jì)，這些多項(xiàng)式隨信息位DATA的長(zhǎng)度的變化對(duì)應(yīng)CRC多項(xiàng)式的海明距HD的關(guān)系。

圖9就是論文中的一張圖，虛線表示所有CRC8多項(xiàng)式的海明距的邊界,橫坐標(biāo)表示的信息數(shù)據(jù)的長(zhǎng)度；縱坐標(biāo)表示誤碼率，誤碼率越小越好。

如果信息位是8bit以下，0x9C是比較好的多項(xiàng)式；

如果信息位是16bit到64bit之間， 0xEA和0x97都是比較好的多項(xiàng)式。

其實(shí)普通人也可以統(tǒng)計(jì)出來(lái)的，只要每個(gè)長(zhǎng)度的DATA都窮舉所有的碼字空間再把它們的海明距找到就行。但是計(jì)算過(guò)程的運(yùn)算量還是很大的，作為工程師去查koopman phail給的表就好了。如果你還是不夠用，可以去koopman phail的主頁(yè)上去找。

圖10

現(xiàn)在根據(jù)圖10的表格來(lái)選個(gè)好的多項(xiàng)式，假設(shè)CRC需要檢測(cè)2（HD=3）錯(cuò)誤，你的信息位DATA的長(zhǎng)度是256bit那就選0x167多項(xiàng)式。