CRC

在數據傳輸過程中，無論傳輸系統的設計再怎麼完美，差錯總會存在，這種差錯可能會導致在鏈路上傳輸的一個或者多個幀被破壞(出現比特差錯，0變為1，或者1變為0)，從而接受方接收到錯誤的數據。為儘量提高接受方收到數據的正確率，在接收方接收數據之前需要對數據進行差錯檢測，當且僅當檢測的結果為正確時接收方才真正收下數據。檢測的方式有多種，常見的有奇偶校驗、因特網校驗和循環冗餘校驗等。循環冗餘校驗是一種用於校驗通信鏈路上數字傳輸準確性的計算方法（通過某種數學運算來建立數據位和校驗位的約定關係的 ^[1]  ）。發送方計算機使用某公式計算出被傳送數據所含信息的一個值，並將此值 附在被傳送數據後，接收方計算機則對同一數據進行 相同的計算，應該得到相同的結果。如果這兩個 CRC結果不一致，則説明發送中出現了差錯，接收方計算機可要求發送方計算機重新發送該數據。

在計算機網絡通信中運用CRC校驗時相對於其他校驗方法就有一定的優勢。CRC可以高比例的糾正信息傳輸過程中的錯誤，可以在極短的時間內完成數據校驗碼的計算，並迅速完成糾錯過程，通過數據包自動重發的方式使得計算機的通信速度大幅提高，對通信效率和安全提供了保障。由於 CRC 算法檢驗的檢錯能力極強，且檢測成本較低，因此在對於編碼器和電路的檢測中使用較為廣泛。從檢錯的正確率與速度、成本等方面，都比奇偶校驗等校驗方式具有優勢。因而，CRC 成為計算機信息通信領域最為普遍的校驗方式。

循環冗餘校驗同其他差錯檢測方式一樣，通過在要傳輸的k比特數據D後添加(n-k)比特冗餘位(又稱幀檢驗序列，Frame Check Sequence，FCS)F形成n比特的傳輸幀T，再將其發送出去。

特別的，循環冗餘校驗提供一個預先設定的(n-k+1)比特整數P，並且要求添加的(n-k)比特F滿足：

其中 T =2^n-kD + F

基於上述要求，實際應用時，發送方和接收方按以下方式通信：

1. 發送方和接收方在通信前，約定好預設整數P。

2. 發送方在發送前根據數據D確定滿足(1)式的F，生成CRC碼 T，T 即為數據位D與校驗位F的拼接，發送T。

3. 接收方收到CRC碼 T，進行 result = T mod P 運算，當且僅當result = 0時接收方認為沒有差錯。

發送方在發送數據前需要確定填充的(n-k)比特F，以下提供了兩種等價的方式來確定F。

模二運算採用無進位的二進制加法，恰好為異或(XOR)操作。(以下運算均為模2運算)

CRC碼 T 需要滿足(1)式，即(2^n-kD + F)/P結果為某一整數

對此表達式進行恆等變換，可得：

繼續對等式中2^n-kD / P 進行恆等變換，將其整數部分 Q 分離，即 Q=(2^n-kD - R)/P，有

將(3)式帶入(2)式 得到：

由於採用無進位的二進制加法(等價於XOR操作)，因此當我們令 F = R 時，有

當Q為整數時，T =(2^n-kD + F)滿足T mod P == 0。

故我們只要找到 F = R 使得(3)式中 Q 恆為整數即可。

由 Q=(2^n-kD - R)/P，可知

（1）當2^n-kD modP ≠ 0 時

R=2^n-kD modP可使等式恆成立。

（2）當2^n-kD modP == 0 時

F = R = n * P （n ∈ Z）可使等式恆成立。

R=2^n-kD modP 即為 n = 0 時情況。

綜上，令R=2^n-kD modP 時 可使等式Q=(2^n-kD - R)/P 中Q恆為整數。

因此我們需要添加的幀檢驗序列F為：

F = R=2^n-kD modP …… (6)

該種方法，我們試圖對任意的二進制數都構造與其對應的一個二進制係數多項式，構造如下：

對於任意k位二進制數D =d_k-1…d₂d₁d₀，其對應的多項式為

例如，D = 110101，則D(X) = X⁵ + X⁴ + X² + 1。

運算過程依然是模二的，則此時的CRC過程可描述如下：

即，此時的F(X)滿足：

上面我們介紹了F(X)的求法，但F(X)依賴於P(X)，因此選取一個合適的P(X)也是CRC的一個關鍵問題。通常，一個m位的CRC多項式P(X)是由如下兩種形式的多項式之一產生的：

其中q(X)是一種特殊類型的多項式，稱為本原多項式。且P(X)滿足：

下面展示常用CRC版本：

利用多項式，我們定義誤碼多項式E(X)是接收到的消息碼字與正確碼字的異或。即

則我們容易知道，當且僅當E(X)能夠被CRC多項式P(X)整除的時候CRC算法無法檢查到錯誤。當我們選擇一個適當的P(X)時，以下所有差錯E(X)都不能被P(X)整除，因此可以檢測出：

在數據存儲和數據通訊領域，為了保證數據的正確，就不得不採用檢錯的手段。在諸多檢錯手段中，CRC是最著名的一種。CRC的全稱是循環冗餘校驗，其特點是：檢錯能力強，開銷小，易於用編碼器及檢測電路實現。從其檢錯能力來看，它所不能發現的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優於奇偶校驗及算術和校驗等方式。因而，在數據存儲和數據通訊領域，CRC無處不在：著名的通訊協議X.25的FCS(幀檢錯序列)採用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等壓縮工具軟件採用的是CRC32，磁盤驅動器的讀寫採用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。下面介紹硬件生成與計算CRC的過程。

下面以最常用的CRC-16為例來説明其生成過程。

CRC-16碼由兩個字節構成，在開始時CRC寄存器的每一位都預置為1，然後把CRC寄存器與8-bit的數據進行異或，之後對CRC寄存器從高到低進行移位，在最高位（MSB）的位置補零，而最低位（LSB，移位後已經被移出CRC寄存器）如果為1，則把寄存器與預定義的多項式碼進行異或，否則如果LSB為零，則無需進行異或。重複上述的由高至低的移位8次，第一個8-bit數據處理完畢，用此時CRC寄存器的值與下一個8-bit數據異或並進行如前一個數據似的8次移位。所有的字符處理完成後CRC寄存器內的值即為最終的CRC值。

1．設置CRC寄存器，並給其賦值FFFF(hex)。

2．將數據的第一個8-bit字符與16位CRC寄存器的低8位進行異或，並把結果存入CRC寄存器。

3．CRC寄存器向右移一位，MSB補零，移出並檢查LSB。

4．如果LSB為0，重複第三步；若LSB為1，CRC寄存器與多項式碼相異或。

注意：該步檢查LSB應該是右移前的LSB，即第3步前的LSB。

5．重複第3與第4步直到8次移位全部完成。此時一個8-bit數據處理完畢。

6．重複第2至第5步直到所有數據全部處理完成。

7．最終CRC寄存器的內容即為CRC值。

循環冗餘校驗碼（CRC），簡稱循環碼，是一種常用的、具有檢錯、糾錯能力的校驗碼，在早期的通信中運用廣泛。循環冗餘校驗碼常用於外存儲器和計算機同步通信的數據校驗。奇偶校驗碼和海明校驗碼都是採用奇偶檢測為手段檢錯和糾錯的(奇偶校驗碼不具有糾錯能力)，而循環冗餘校驗則是通過某種數學運算來建立數據位和校驗位的約定關係的 ^[2]  。