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

大家都知道芯片有輸入輸出，根據不同的傳輸協議，輸入輸出的數據有可能是一串長長的數據，幾十個或者幾百個byte甚至更多。在數據傳輸過程中，由于某些意外的原因導致某些bit出現錯誤（0變為1，或者1變為0)，從而接受方接收到錯誤的數據。

為盡量提高接受方收到數據的正確率，在接收方接收數據后需要對數據進行校驗，當且僅當校驗的結果為正確時接收方才真正收下數據。循環冗余校驗(Cyclic Redundancy Check, CRC)算法通常用于數字傳輸系統或者存儲器中，用來檢測意外事件對原數據的影響，判斷接受到的數據是否正確。

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

1

前言：

因為CRC循環冗余校驗碼的算法和硬件電路結構比較簡單，所以CRC是一種在工程中常用的數據校驗方法。盡管CRC簡單，但在工程應用中還是有些問題會對工程師產生困惑。這篇文章將從以下三個方面介紹以下CRC，希望對大家有所幫助。

CRC 的數學原理；

CRC的通項公式，怎樣選取一個適合的通項公式；

CRC 硬件電路實現，串行電路到并行電路的實現。

2

CRC的數學原理：

在講CRC的數學原理之前，首先看一下下面的圖。圖1是A要給B發送1bit的信息0或者1。假設A發

圖1

送一個0給B,系統正常的情況下B會接受到一個0。但是如果有個干擾（比如信號線的串擾）在A和B相連的傳輸線上，那么B就有可能接受到一個1，傳輸數據發生錯誤。

為了改進這個傳輸過程，A和B約定(圖2)。

圖2

如果A要發送一個0給B，A就在一段時間連續發送兩個0（2’b00’）給B；

如果A要發送一個1信息給B，那么A就在一段時間連續發送兩個1（2’b11’）給B。

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

要是B接受到了一個2’b00，B就會認為A發送的信息是個0；

那么A有沒有可能發的信息是2個1？這也是有可能的，不過2’b00變成2’b11比1’b0變成1’b1的概率要低的多。

如果A和B約定以圖3的方式進行傳輸，假設A要發送一個0給B，那么A就在一段時間連續發送3個0（3’b000）給B；如果A要發送一個1信息給B，那么A就在一段時間連續發送三個1（3’b111’）給B；

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

圖3

并且B會自我判斷A給自己發送的信息是0不是1。這種判斷是合理的，因為誤判的概率很低。

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

圖4 箭頭上的數字是海明距（HD）

海明距離HD的定義

兩個碼字的對應比特值不同（異或）的總數目稱為這兩個碼字的海明距離。一個有效編碼集中,任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。

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

第二種情況其實就是奇偶校驗，碼距是2，可以檢測1個錯誤；

第三種情況就是糾錯碼了，海明距是3，如果出現了1個錯誤是可以自己糾錯的，出現小于3個錯誤可以檢測。

第三種情況的有效碼字000，其中0是信息位，00是校驗位，2位的校驗碼來確定一位數據位，看上去有點太浪費了。

一種編碼的校驗和糾錯能力取決于它的海明距離。為檢測出d比特錯，需要使用碼距d+1的編碼；因為d個單比特錯決不可能將一個有效的碼字轉變成另一個有效的碼字。當接收方看到無效的碼字，它就能明白發生傳輸錯誤。

同樣，為了糾正d比特錯，必須使用碼距為2d+1的編碼，這是因為有效碼字的距離遠到即使發生d個變化，這個發生了變化的碼字仍然比其它碼字都接近原始碼字。

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

下面看一看圖5的CRC計算過程

圖5（來自wikipedia）

CRC在數學上就是除余運算，除數是個通項公式（固定數）,

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

被除數11010011101100，除數1011

DATA=11010011101100，

最終得到的余數 CHECK SUM=100，

所以需要傳輸的CODEWORD=11010011101100100。

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

具體傳輸過程如下：

A發送DATA=11010011101100給B，

發送之前先編碼

假設初始CODEWORD=11010011101100000

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

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

CODEWORD=11010011101100100。

在B接受到CODEWORD 通過解碼來檢查A的發送有沒有錯。

解碼的過程：

用CODEWORD=11010011101100100對G(X)=X3+X+1 （1011）除余數，如果余數等于0即CHECK SUM=000，就認為B接受到的數據就沒有問題。

圖6

余數等于0，就一定沒有出錯嗎？當然不是，只能說出錯的概率很低。這個可靠性跟CRC的G(X)通項公式和信息位的長度相關；

怎樣選取一個適合的CRC通項公式呢？

CRC通項公式（生成多項式）很容易找到，網上隨便一搜就會有很多。

圖7（來自wikipedia）

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

提醒一下：當看到代碼poly=0x03，很難知道多項式是什么？因為數字表示法沒有統一的定義，容易產生歧義。建議寫數字表示的時候附上多項式，這樣不會產生誤會；程序變量poly=0x03，最好后面是注釋G(X)=X3+X+1。

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

圖8

數字表示法這樣定義是為了遵循CRC的研究者的習慣。

CRC多項式的檢錯能力其實有很多研究成果，這里以koopman phail舉例，因為可以在作者的個人主頁上找到一些算好的數據。作者還是美國著名的卡內基梅隆大學的Associate Porofesor。

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

DATA=11010011101100，

CHECK SUM=100，

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

校驗位CHECK SUM=100的DATA變成相同校驗位但是數據不同的DATA1，在接受端是沒有辦法知道出錯了的。所以koopman phail就把“幾乎所有的多項式”做了統計，這些多項式隨信息位DATA的長度的變化對應CRC多項式的海明距HD的關系。

圖9就是論文中的一張圖，虛線表示所有CRC8多項式的海明距的邊界,橫坐標表示的信息數據的長度；縱坐標表示誤碼率，誤碼率越小越好。

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

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

其實普通人也可以統計出來的，只要每個長度的DATA都窮舉所有的碼字空間再把它們的海明距找到就行。但是計算過程的運算量還是很大的，作為工程師去查koopman phail給的表就好了。如果你還是不夠用，可以去koopman phail的主頁上去找。

圖10

現在根據圖10的表格來選個好的多項式，假設CRC需要檢測2（HD=3）錯誤，你的信息位DATA的長度是256bit那就選0x167多項式。