循環冗餘校驗

循環冗餘校驗（Cyclic Redundancy Check， CRC）是一種根據網絡數據包或計算機文件等數據產生簡短固定位數校驗碼的一種信道編碼技術，主要用來檢測或校驗數據傳輸或者保存後可能出現的錯誤。它是利用除法及餘數的原理來作錯誤偵測的。^[1]

工作原理

循環冗餘校驗同其他差錯檢測方式一樣，通過在要傳輸的k比特數據D後添加(n-k)比特冗餘位(又稱幀檢驗序列，Frame Check Sequence，FCS)F形成n比特的傳輸幀T，再將其發送出去。特別的，循環冗餘校驗提供一個預先設定的(n-k+1)比特整數P，並且要求添加的(n-k)比特F滿足：

T mod P == 0 ……(1)

其中 T =2n-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)式，即(2n-kD + F)/P結果為某一整數對此表達式進行恆等變換，可得：(2n-kD + F)/P = 2n-kD / P + F / P …… (2)繼續對等式中2n-kD / P 進行恆等變換，將其整數部分 Q 分離，即 Q=(2n-kD - R)/P，有2n-kD / P = Q + R / P …… (3)

將(3)式帶入(2)式得到：(2n-kD + F) / P = Q + R / P+ F / P …… (4)由於採用無進位的二進制加法(等價於XOR操作)，因此當我們令 F = R 時，有(2n-kD + F) / P = Q + R / P+ F / P = Q …… (5)

當Q為整數時，T =(2n-kD + F)滿足T mod P == 0。故我們只要找到 F = R 使得(3)式中 Q 恆為整數即可。

由 Q=(2n-kD - R)/P，可知（1）當2n-kD modP ≠ 0 時R=2n-kD modP可使等式恆成立。（2）當2n-kD modP == 0 時F = R = n * P （n ∈ Z）可使等式恆成立。R=2n-kD modP 即為 n = 0 時情況。綜上，令R=2n-kD modP 時可使等式Q=(2n-kD - R)/P 中Q恆為整數。

因此我們需要添加的幀檢驗序列F為：F = R=2n-kD modP …… (6)

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

對於任意k位二進制數D =dk-1…d2d1d0，其對應的多項式為D(X) = ∑di*Xi，i∊[0， k) …… (7) 例如，D = 110101，則D(X) = X5 + X4 + X2 + 1。

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

Xn-kD(X) / P(X) = Q(X) + R(X) / P(X) …… (8)

T(X) = Xn-kD(X) + R(X) …… (9)

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

F(X) = Xn-kD(X) mod P(X) …… (10)

常用CRC版本

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

P(X) = q(X) …… (12)

P(X) = (X + 1)q(X) …… (13)

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

最高位和最低位都是1

當被傳送信息任何一位發生錯誤時，P(X)不被T(X)整除

不同位發生錯誤時，餘數應該不同

對餘數繼續做模二除法時，應該使餘數循環

下面展示常用CRC版本：

差錯檢測能力

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

E(X) = Trecv(X) XOR Tcorrect(X) …… (14)

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

單比特差錯，只要P(X)含有一個以上的非零項。

雙比特差錯，只要P(X)滿足上述兩種形式((12)(13)式)。

任意奇數個比特差錯，只要P(X)含有因式(X - 1)。

任意突發差錯，當突發差錯長度小於或等於幀檢驗序列(F(X))的長度(n - k)。

長度為(n - k + 1)的突發差錯片段，這個片段等於(1-2-(n-k-1))。

長度大於(n - k + 1)的突發差錯片段，這個片段等於(1 - 2-(n-k))

應用場合

在數據存儲和數據通訊領域，為了保證數據的正確，就不得不採用檢錯的手段。在諸多檢錯手段中，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值。