CRC校驗原理和verilog實現方法(一)
1.CRC簡介
CRC全稱循環冗餘校驗(Cyclic Redundancy Check， CRC)，是通訊領域數據傳輸技術中常用的檢錯方法，用於保證數據傳輸的可靠性。網上有關這方面的部落格和資料很多，本文盡量簡潔的梳理一下它的原理。後面還會結合自己的實踐經驗(不多)，說一說如何使用verilog語言在FPGA中做CRC校驗。感興趣的朋友可以關注我後續的更新，一起交流學習！
CRC校驗的基本思路是數據發送方發送數據之前，先生成一個CRC校驗碼，可以是單bit也可以是多bit，並附在有效數據末尾，以串列方式發送到接收方。接收方接收到數據後，進行CRC校驗，根據校驗結果就可以知道數據是否有誤。
CRC校驗碼的生成：將有效數據擴展後作為被除數，使用一個指定的多項式作為除數，進行模二除法，得到的餘數就是校驗碼。
數據接收方的CRC校驗：將接受的數據(有效數據+CRC校驗碼)擴展後作為被除數，用指定的多項式作為除數，進行模二除法，得到餘數為0，則表示校驗正確。
2.CRC校驗過程
2.1多項式選取
多項式關係到檢查錯誤的可靠性，其中有一定的數學關係，這裡不去深究，感興趣的朋友可查閱通訊原理和線性編碼相關書籍。
多項式的常規表達式：G(x)=x^n+x^(n-1)…+1，其中n>=1。
也可以用2進位數表示，以便軟體編程。例如多項式G(x)=x^5+x^3+x^2+1，用2進位表示就是101101；多項式G(x)=x^6+x^5+x^1+1，用2進位表示就是1100011。很容易看出規律吧。
有些資料里將多項式最高位的1省略，不過這裡建議手動計算時保留這一位，免得出錯。
通訊領域有一些常用的多項式，如下表示所示，可根據通訊方式選擇，例如CRC-5/USB演算法對應的是用於USB通訊的CRC多項式。
2.2求餘數(發送方)
求余目的是得到CRC校驗碼。首先將有效數據擴展n位作為被除數，n是多項式的最高次冪，例如前面的多項式101101最高次冪是5(比2進位位數少1)，則有效數據擴展5位。然後用多項式的2進位數用模2除法去除被除數，得到的餘數是CRC校驗碼。
先搞明白模2除法運算機制。
模2除法可以藉助邏輯上的異或運算和移位實現，例如被除數是2進位的10001111，除數是1010，則模2除法求餘數的計算過程如下圖所示，得到商是101，餘數是111。可以看出，每次計算，除數最高位的「1」都要和被除數最高位的「1」對齊，然後進行異或運算。得到的餘數位數不小於除數，則移位後再次對齊、計算，直到餘數位數(從最高位的1開始算)小於除數位數。
再看CRC校驗碼的計算過程。
假如發送的有效數據是10101010(注意是2進位)，我們把它作為被除數。這裡選擇CRC-5/USB校驗演算法，多項式是x^5+x^2+1，對應2進位形式是100101。
首先對有效數據擴展5bit，也就是在後面添5個0，得到被除數1010101000000。然後進行模2除法，最終得到5bit(比多項式少1bit)餘數11000，這就是CRC校驗碼。
把上面得到的校驗碼附在有效數據後面，構成數據1010101011000，然後發送給接收方。
2.3求餘數(接收方)
數據接收方對數據(包含校驗碼)求餘數，計算過程與上述完全相同。最終得到的餘數為0，才能說明數據傳輸無誤。
假如接收的數據無誤，這裡寫出來接收方的計算過程：
最終得到餘數為0，證明數據無誤。
需要注意的是，在構造被除數之前，原始數據必須是以位元組(8bit)為單位，如果不夠一個完整的位元組，可以在高位補0。這一點在後面verilog實現時很關鍵。
3.CRC校驗計算實例
關於CRC校驗碼的計算，上面繁瑣的手算有助於了解計算過程，現在也有很多CRC計算工具，在線的和離線的都有。例如參考鏈接1的在線計算工具，可以用來驗證手算或者自己的校驗程式碼的計算結果。
這裡用一個2byte數據做一次完整CRC校驗，其中校驗碼的計算分別用手算和在線工具計算進行對比。
1）要發送的數據是0x8421，對應2進位為1000 0100 0010 0001；校驗演算法使用CRC-8，對應多項式是100000111。
2）手動計算，求校驗碼：有效數據擴展後為1000 0100 0010 0001 0000 0000，計算得CRC校驗碼為00000101，16進位為0x05。（算到眼疼~）
3）在線工具計算校驗碼：得0x05，結果一致，說明手算無誤。
4）在原始的發送數據後面附上校驗碼：得1000 0100 0010 0001 0000 0101，即0x842105。
4）手動計算，求接收方的校驗結果：得0x00。
5）在線工具計算，求接收方的校驗結果：得0x00，接收校驗無誤。
參考鏈接：
1、//www.ip33.com/crc.html
2、//www.cnblogs.com/liushui-sky/p/9962123.html
