一、概述

CRC，即Cyclic Redundancy Check，循環(huán)冗余校驗，是一種數(shù)字通信中的常用信道編碼技術。其特征是信息段和校驗字段的長度可以任意選定。



二、CRC校驗的基本原理
CRC碼是由兩部分組成的，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼長共n bit，信息碼長k bit，就稱為(n,k)碼，剩余的r bit即為校驗位。如：(7,3)碼：110 1001，前三位110為信息碼，1001為校驗碼。



三、校驗碼的生成規(guī)則
1) 將原信息碼左移r bit，右側補零，如 110--> 110 0000；
2) 用110 0000除以g(x)  (注意，使用的是模2除法，見下文)，得到的余數(shù)即為CRC校驗碼；
3) 將校驗碼續(xù)接到信息碼的尾部，形成CRC碼。



四、關于生成多項式g(x)
在產(chǎn)生CRC校驗碼時，要用到除法運算，一般來說，這是比較麻煩的，因此，把二進制信息預先轉換成一定的格式，這就是CRC的多項式表示。二進制數(shù)表示為生成多項式的系數(shù)，如下：
所有二進制數(shù)均被表示為一個多項式，x僅是碼元位置的標記，因此我們并不關心x的取值，稱之為碼多項式。(我沒研究過CRC代數(shù)推理過程，沒體會到用多項式計算的方便之處，這里要學會的就是給出生成多項式g(x)，能寫出對應的二進制即可)
常見的生成多項式如下：



五、關于模2除法
模2運算就是加法不考慮進位，減法不考慮借位。 1）加法運算： 0＋0＝0        0＋1＝1        1＋0＝1        1＋1＝0
例如0101＋0011＝0110，列豎式計算：
0 1 0 1
＋ 0 0 1 1
──────
0 1 1 0

2）減法運算： 0－0＝0        0－1＝1        1－0＝1        1－1＝0 例如0110－0011＝0101，列豎式計算：
0 1 1 0
－  0 0 1 1
──────
0 1 0 1

3）乘法運算
0×0＝0        0×1＝0        1×0＝0        1×1＝1
多位二進制模2乘法類似于普通意義上的多位二進制乘法，不同之處在于后者累加中間結果時采用帶進位的加法，而模2乘法對中間結果的處理方式采用的是模2加法。例如1011×101＝100111，列豎式計算：
4）除法運算：
0÷1＝0        1÷1＝1

多位二進制模2除法也類似于普通意義上的多位二進制除法，但是在如何確定商的問題上兩者采用不同的規(guī)則。后者按帶借位的二進制減法，根據(jù)余數(shù)減除數(shù)夠減與否確定商1還是商0，若夠減則商1，否則商0。多位模2除法采用模2減法，不帶借位的二進制減法，因此考慮余數(shù)夠減除數(shù)與否是沒有意義的。實際上，在CRC運算中，總能保證除數(shù)的首位為1，則模2除法運算的商是由余數(shù)首位與除數(shù)首位的模2除法運算結果確定。因為除數(shù)首位總是1，按照模2除法運算法則，那么余數(shù)首位是1就商1，是0就商0。例如1100100÷1011＝1110……110，列豎式計算：


掌握了上面的運算規(guī)則，你可以嘗試計算一個復雜一點的，如下：
如果得到的余數(shù)結果正確，你掌握的東西就夠用了。



六、CRC-CCITT的硬件實現(xiàn)
CRC-CCITT的生成多項式為：
對應的二進制數(shù)就是上面復雜運算中那個除數(shù)。由剛才的計算可知，對于8 bit的數(shù)據(jù) 0xaa，它的CRC校驗碼為0001 0100 1010 0000，下面用verilog來實現(xiàn)，看能否得到這個結果：
要實現(xiàn)這一過程，仍然需要LFSR電路，參看《FPGA設計中，產(chǎn)生LFSR偽隨機數(shù)》中關于該電路特性的介紹，如果你不需要了解原理，直接略過即可；有所改進的地方就是，可以將偽隨機數(shù)發(fā)生器看作一個Moore型狀態(tài)機，它的輸出只與當前的狀態(tài)有關；而此時利用LFSR電路，需要引入數(shù)據(jù)輸入端，輸出不僅取決于當前的狀態(tài)，還取決于輸入信號，相當于Mealy型狀態(tài)機，如下圖：
注意對比與偽隨機數(shù)產(chǎn)生器中該反饋支路的區(qū)別。
反饋項gr+1gr……g0為生成多項式的系數(shù)，依然是1代表存在反饋，0代表不存在反饋；此電路可以完成上述的模2除法操作，若我們要求0xaa的CRC校驗碼，則從高位到低位順序輸入0xaa共8 bit后，D15……D0中的數(shù)據(jù)即為所要求的余數(shù)，即CRC校驗位。

七、verilog描述
如果用時序電路串行實現(xiàn)，則8 bit數(shù)據(jù)要移位8次，就需要8個clk，效率低下，為了能在一個時鐘周期輸出結果，必須采用組合電路，當然，這是以空間換時間的方法，由于使用了for循環(huán)8次，直觀的講電路規(guī)模將擴大8倍。

仿真結果如下：得到的是數(shù)據(jù)0xaa和0xf0的CRC校驗碼，為驗證結果的正確性，可以按照模2法則手工計算一下。

八、其他例子同樣給出一個4 bit信息位，5 bitCRC碼的(9，4)碼的程序和仿真結果，程序的流程與上述流程完全一樣：

 

說明：細心的大俠可能發(fā)現(xiàn)，本篇對LFSR電路能完成模2求余操作的原因避而不談，不是因為不告訴你，是因為目前也不是很清楚，工科背景對數(shù)學推理實在是有點不知所云，尤其是看到國內(nèi)教材那好幾頁的公式的時候，如果您有通俗易懂的講解LFSR電路由來與應用的文章，注意是深入淺出的，請大力推薦，在此感謝。