查看“︁循環冗餘校驗”︁的源代码

{{noteTA
|G1=IT
|1=zh-hans:散列函数;zh-hant:雜湊函數;
|2=zh-hans:校验;zh-hant:驗證;
|3=zh-hans:异或;zh-hant:互斥或;
|4=zh-hans:同余;zh-hant:同餘;
|5=zh-hans:取反;zh-hant:反相;
}}
'''循環冗餘校驗'''（{{lang-en|'''Cyclic redundancy check'''}}，通稱「'''CRC'''」）是一種根據網路數據封包或[[電腦檔案]]等數據產生簡短固定位數驗證碼的一種[[散列函數]]，主要用來檢測或校驗數據傳輸或者保存後可能出現的錯誤。生成的數字在傳輸或者儲存之前計算出來並且附加到數據後面，然後接收方進行檢驗確定數據是否發生變化。由於本函數易於用二進制的[[電腦硬件]]使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。此方法是由{{tsl|en|W. Wesley Peterson}}於1961年發表<ref name="PetersonBrown1961">{{cite journal |author=Peterson, W. W. and Brown, D. T. |title=Cyclic Codes for Error Detection |journal=Proceedings of the IRE |date=January 1961 |volume=49 |pages=228 |doi=10.1109/JRPROC.1961.287814 |issn=0096-8390}}</ref>。

CRCs經常被叫做「[[校驗和]]」，但是這樣的說法嚴格來說並不是準確的，因為技術上來說，校驗「和」是通過加法來計算的，而不是CRC這裡的除法。

「[[纠错码]]」<small>（{{lang|en|Error–Correcting Codes}}，簡稱ECC）</small>常常和CRCs緊密相關，其語序糾正在傳輸過程中所產生的錯誤。這些編碼方式常常和數學原理緊密相關。例如常見于通訊或資訊傳遞上[[BCH码]]、[[前向錯誤更正]]、[[错误检测与纠正]]等。
== 簡介 ==
CRC是兩個字節數據流採用二進制除法（沒有進位，使用[[XOR]]來代替減法）相除所得到的餘數。其中被除數是需要計算校驗和的信息數據流的二進制表示；除數是一個長度為<math>(n+1)</math>的預定義（短）的二進制數，通常用多項式的系數來表示。在做除法之前，要在信息數據之後先加上<math>n</math>個0。

CRC是基於[[有限域]]'''GF(2)'''（即[[除以2]]的[[同余]]）的[[多項式環]]。簡單的來說，就是所有系數都為0或1（又叫做二進制）的多項式系數的集合，並且集合對於所有的代數操作都是封閉的。例如：

:<math>(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1</math>

2會變成0，因為對系數的加法運算都會再取2的模數。乘法也是類似的：

:<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x</math>

同樣可以對多項式作除法並且得到商和餘數。例如，如果用''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x''除以''x'' + 1。會得到：
:<math>\frac{(x^3 + x^2 + x)}{(x+1)} = (x^2 + 1) - \frac{1}{(x+1)}</math>
<!--註：在說「除以」的時候，讀者將會看到等式中的除號。這裡看不到除號常使我感到有點混亂。-->

也就是說，

:<math>(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1</math>

<!--註：下面提到了「在上面的等式中，<math>x^2+x+1</math>表示...」，而上面這個等式左邊不做分解的話，是看不出<math>x^+x+1</math>的。-->
等價於：

:<math>(x^2 + x + 1)x = (x^2 + 1)(x + 1) - 1</math>

這裡除法得到了商''x''<sup>2</sup> + 1和餘數-1，因為是奇數所以最後一位是1。

字符串中的每一位其實就對應了這樣類型的多項式的系數。為了得到CRC，首先將其乘以<math>x^{n}</math>，這裡<math>n</math>是一個固定多項式的'''{{le|多項式的階|Degree of a polynomial|階數}}'''，然後再將其除以這個固定的多項式，餘數的系數就是CRC。

在上面的等式中，<math>x^2+x+1</math>表示了本來的信息位是<code>111</code>, <math>x+1</math>是所謂的'''鑰匙'''，而餘數<math>1</math>（也就是<math>x^0</math>）就是CRC. key的最高次為1,所以將原來的信息乘上<math>x^1</math>來得到<math>x^3 + x^2 + x</math>，也可視為原來的信息位補1個零成為<code>1110</code>。

一般來說，其形式為：

:<math>M(x) \cdot x^{n} = Q(x) \cdot K(x) - R(x) </math>

這裡M(x)是原始的信息多項式。K(x)是<math>n</math>階的「鑰匙」多項式。<math>M(x) \cdot x^{n}</math>表示了將原始信息後面加上<math>n</math>個0。R(x)是餘數多項式，即是CRC「校驗和」。在通訊中，發送者在原始的信息數據M後附加上<math>n</math>位的R（替換本來附加的0）再發送。接收者收到M和R後，檢查<math>M(x) \cdot x^{n} + R(x)</math>是否能被<math>K(x)</math>整除。如果是，那麼接收者認為該信息是正確的。值得注意的是<math>M(x) \cdot x^{n} + R(x)</math>就是發送者所想要發送的數據。這個串又叫做''codeword''.

== 實現 ==

== 變體 ==
CRC有幾種不同的變體：

* <code>shiftRegister</code>可以逆向使用，這樣就需要檢測最低位的值，每次向右移動一位。這就要求<code>polynomial</code>生成逆向的數據位結果。''實際上這是最常用的一個變體。''
* 可以先將數據最高位讀到[[移位寄存器]]，也可以先讀最低位。在通訊協議中，為了保留CRC的{{le|突發錯誤|Burst error}}檢測特性，通常按照[[物理層]]發送數據位的方式計算CRC。
* 為了檢查CRC，需要在全部的碼字上進行CRC計算，而不是僅僅計算消息（Message）的CRC並把它與CRC比較。如果結果是0，那麼就通過這項檢查。這是因為碼字<math>M(x) \cdot x^{n} + R(x) = Q(x) \cdot K(x)</math>可以被<math>K(x)</math>整除。
* 移位寄存器可以初始化成1而不是0。同樣，在用算法處理之前，消息的最初<math>n</math>個數據位要取反。這是因為未經修改的CRC無法區分只有起始0的個數不同的兩條消息。而經過這樣的取反過程，CRC就可以正確地分辨這些消息了。
* CRC在附加到消息數據流（Message stream）的時候可以進行字節取反。這樣，CRC的檢查可以用直接的方法計算消息的CRC、取反、然後與消息數據流中的CRC比較這個過程來完成，也可以通過計算全部的消息來完成。在後一種方法中，正確消息的結果不再是0，而是<math>\sum_{i=n}^{2n-1} x^{i}</math>除以<math>K(x)</math>得到的結果。這個結果叫作核驗多項式<math>C(x)</math>，它的十六進製表示也叫作[[魔術數字 (程式設計)|幻數]]。

按照慣例，使用CRC-32多項式以及CRC-16-CCITT多項式時通常都要取反。CRC-32的核驗多項式是<br>
<math>C(x) = x^{31} + x^{30} + x^{26} + x^{25} + x^{24} + x^{18} + x^{15} + x^{14} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1</math>。

* 對於要處理的資料M(x)有前置0時，用<math> x^{m} L(x) </math>與<math>M(x).x^{n}</math>兩式相加作反相運算，使得前置的0變成1後，再作mod 2運算得到CRC。公式：
<math>M(x) \cdot x^{n} + x^{m} L(x) = Q(x) \cdot K(x)  + R(x)</math><BR><math>L(x) \,\!</math><math>= \sum_{i=0}^{n-1} x^i </math><BR><math>T(x) = M(x) \cdot x^{n} + L(x) + R(x)  </math><BR>
例：
<math>M(x) = 01111 </math><br>
<math>K(x) = x^{3} + x^{2} + 1 = 1101 </math>，這裡可知<math>n=3</math><br>
<math>M(x).x^{3} = 01111000 </math><br>
因<math>\sum_{i=0}^{n-1} x^{i}</math>，<math>n=3</math>故L(x)階數從2開始<br>
<math>L(x) = x^{2} + x^{1} + x^{0} = 111 </math><br>
用<math>x^{m} L(x)</math>求得一組n個1及m個0以便與<math>M(x).x^{n}</math>相加<br>
令m = 5，<math>X^{m} L(x) = X^{5} L(x) = 11100000 </math>（bitwise shift）<br>
<math>M(x).x^{n} + x^{m} L(x) = 01111000 + 11100000 = 10011000</math>（使M前置的0變成1）<br>
用<math>10011000</math> mod2 <math>K(x)</math>求得餘R(x)= 011<br>
<math>T(x) = M(x).x^{n} + L(x) + R(x) = 01111000 + 111 + 011 = 01111100</math>送出<BR>
接收端L(x) = 111且開頭不為1 => m = 5 <BR>
可反推<math> M(x).x^{n} + x^{m} L(x) + R(x) = 01111000 + 11100000 + 011 = 10011011</math><BR>
用10011011 mod2  1101可驗證能被K(x)整除。

== 錯誤檢測能力 ==
CRC的錯誤檢測能力依賴於關鍵多項式的階次以及所使用的特定關鍵多項式。''誤碼多項式''<math>E(x)</math>是接收到的消息碼字與正確消息碼字的''異或''結果。當且僅當誤碼多項式能夠被CRC多項式整除的時候CRC算法無法檢查到錯誤。
* 由於CRC的計算基於除法，任何多項式都無法檢測出一組全為零的數據出現的錯誤或者前面丟失的零。但是，可以根據CRC的[[#變體|變體]]來解決這個問題。
* 所有只有一個數據位的錯誤都可以被至少有兩個非零系數的任意多項式檢測到。誤碼多項式是<math>x^k</math>，並且<math>x^k</math>只能被<math>i \le k</math>的多項式<math>x^i</math>整除。
* CRC可以檢測出所有間隔距離小於多項式階次的雙位錯誤，在這種情況下的誤碼多項式是
 <math>E(x) = x^i + x^k = x^k \cdot(x^{i-k} + 1), \; i > k</math>。
如上所述，<math>x^k</math>不能被CRC多項式整除，它得到一個<math>x^{i-k} + 1</math>項。根據定義，滿足多項式整除<math>x^{i-k} + 1</math>的<math>{i-k}</math>最小值就是多項式的階次。最高階次的多項式是[[本原多項式]]，帶有二進制系數的<math>n</math>階多項式

== CRC多項式規範 ==
下面的表格略去了「初始值」、「反射值」以及「最終異或值」。
* 對於一些複雜的校驗和來說這些十六進制數值是很重要的，如CRC-32以及CRC-64。通常小於CRC-16的CRC不需要使用這些值。
* 通常可以通過改變這些值來得到各自不同的校驗和，但是校驗和算法機制並沒有變化。

CRC標準化問題
* 由於CRC-12有三種常用的形式，所以CRC-12的定義會有歧義
* 在應用的CRC-8的兩種形式都有數學上的缺陷。
* 據稱CRC-16與CRC-32至少有10種形式，但沒有一種在數學上是最優的。
* 同樣大小的CCITT CRC與ITU CRC不同，這個機構在不同時期定義了不同的校驗和。

== 常用CRC（按照ITU-IEEE規範） ==
{|class="wikitable"
! 名稱|| 多項式 || 表示法：正常或者翻轉
|-
|CRC-1 || <math>x + 1</math><br />（用途：硬件，也稱為[[奇偶校驗位]]） || 0x1 or 0x1 (0x1)
|-
|CRC-5-CCITT || <math>x^{5} + x^{3} + x + 1</math>（[[ITU]] G.704標準） || 0xB（0x??）
|-
|CRC-5-USB || <math>x^{5} + x^{2} + 1</math>（用途：[[USB]]信令包） || 0x5 or 0x14 (0x9)
|-
|CRC-7 || <math>x^{7} + x^{3} + 1</math>（用途：通信系統） || 0x9 or 0x48 (0x11)
|-
|CRC-8-ATM || <math>x^8 + x^2 + x + 1</math>（用途：ATM HEC, PMBUS （參見SMBUS org[http://smbus.org/faq/crc8Applet.htm] {{Wayback|url=http://smbus.org/faq/crc8Applet.htm |date=20220328104435 }}）） || 0x7或0xE0 (0xC1)
|-
|CRC-8-[[CCITT]] || <math>x^8 + x^7 + x^3 + x^2 + 1</math>（用途：[[1-Wire]] [[總線]]） ||0x8D
|-
|CRC-8-[[Dallas Semiconductor|Dallas]]/[[Maxim IC|Maxim]] || <math>x^8 + x^5 + x^4 + 1</math>（用途：[[1-Wire]] [[bus]]） || 0x31或0x8C
|-
|CRC-8 || <math>x^8 + x^7 + x^6 + x^4 + x^2 +1</math> || 0xD5（0x??）
|-
|CRC-10 || <math>x^{10} + x^9 + x^5 + x^4 + x + 1</math> || 0x233（0x????）
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math>（用途：通信系統） || 0x80F或0xF01 (0xE03)
|-
|CRC-16-Fletcher || 參見[[Fletcher's checksum]] || 用於[[Adler-32]] A & B CRC
|-
|CRC-16-CCITT || <math>x^{16} + x^{12} + x^5 + 1</math>（[[X25]], [[V.41]], [[Bluetooth]], [[PPP]], [[IrDA]]） || 0x1021或0x8408 (0x0811)
|-
|CRC-16-[[IBM]] || <math>x^{16} + x^{15} + x^2 + 1</math>（用途：[[Modbus|Modbus）]] || 0x8005或0xA001 (0x4003)
|-
|CRC-16-[[BBS]] || <math>x^{16} + x^{15} + x^{10} + x^3</math>（用途：[[XMODEM]]協議） || 0x8408（0x????）
|-
|CRC-32-Adler || 參見[[Adler-32]] || 參見[[Adler-32]]
|-
|CRC-32-MPEG2 || 參見[[IEEE 802.3]] || 參見[[IEEE 802.3]]
|-
|CRC-32-[[IEEE 802.3]] || <math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math> || 0x04C11DB7或0xEDB88320 (0xDB710641)
|-
|CRC-32C(Castagnoli)|| <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1</math> || 0x1EDC6F41或0x82F63B78 (0x05EC76F1)
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math><br />（用途: ISO 3309） || 0x000000000000001B或0xD800000000000000 (0xB000000000000001)
|-
|CRC-64-[[Ecma International|ECMA]]-182 || <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} </math><br /><!--Too long to display in one table--><math>+ x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1</math><br />（參見[http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] {{Wayback|url=http://www.ecma-international.org/publications/standards/Ecma-182.htm |date=20200731173949 }} p.63） || 0x42F0E1EBA9EA3693或0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)
|-
|CRC-128 || IEEE-ITU標準。被[[MD5]] & [[SHA-1]]取代||
|-
|CRC-160 || IEEE-ITU標準。被[[MD5]] & [[SHA-1]]取代||
|}

== CRC與數據完整性 ==
儘管在[[錯誤檢測]]中非常有用，CRC並不能可靠地驗證[[數據完整性]]（即數據沒有發生任何變化），這是因為CRC多項式是線性結構，可以非常容易地''故意''改變數據而維持CRC不變，參見[http://www.woodmann.com/fravia/crctut1.htm CRC and how to Reverse it] {{Wayback|url=http://www.woodmann.com/fravia/crctut1.htm |date=20220308042934 }}中的證明。可以用[[訊息鑑別碼]]驗證數據完整性。

=== CRC發生碰撞的情況 ===

與所有其它的[[散列函數]]一樣，在一定次數的碰撞測試之後CRC也會接近100%出現碰撞。CRC中每增加一個數據位，碰撞機率就會減少接近50%，如CRC-20與CRC-21相比。
* 理論上來講，CRC64的碰撞概率大約是每18{{e|18}}個CRC碼出現一次。
* 由於CRC的不分解多項式特性，所以經過合理設計的較少位數的CRC可能會與使用較多數據位但是設計很差的CRC的效率相媲美。在這種情況下CRC-32幾乎同CRC-40一樣優秀。

=== 設計CRC多項式 ===

生成多項式的選擇是CRC算法實現中最重要的部分，所選擇的多項式必須有最大的錯誤檢測能力，同時保證總體的碰撞概率最小。多項式最重要的屬性是它的長度，也就是最高非零系數的數值，因為它直接影響著計算的校驗和的長度。

最常用的多項式長度有
* 9位（CRC-8）
* 17位（CRC-16）
* 33位（CRC-32）
* 65位（CRC-64）

在構建一個新的CRC多項式或者改進現有的CRC時，一個通用的數學原則是使用滿足所有模運算不可分解多項式約束條件的多項式。
* 這種情況下的不可分解是指多項式除了1與它自身之外不能被任何其它的多項式整除。

生成多項式的特性可以從算法的定義中推導出來：
* 如果CRC有多於一個的非零系數，那麼CRC能夠檢查出輸入消息中的所有單數據位錯誤。
* CRC可以用於檢測短於2k的輸入消息中的所有雙位錯誤，其中k是多項式的最長的不可分解部分的長度。
* 如果多項式可以被x+1整除，那麼不存在可以被它整除的有奇數個非零系數的多項式。因此，它可以用來檢測輸入消息中的奇數個錯誤，就像奇偶校驗函數那樣。

== 參見 ==
總的分類
* [[糾錯碼]]
* [[校驗和算法列表]]
* [[奇偶校驗位]]

特殊技術參考
* [[Adler-32]]
* [[Fletcher's checksum]]

== 參考文獻 ==
<references/>

== 外部連結 ==
* [https://web.archive.org/web/20060806001102/http://relisoft.com/Science/CrcMath.html Tutorial and C++ implementation] of CRC (所引用网址代码运行存在问题)
* [http://www.softwarepatch.com/tips/cyclic-redundancy.html Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs] {{Wayback|url=http://www.softwarepatch.com/tips/cyclic-redundancy.html |date=20180303010310 }} 
* [https://web.archive.org/web/20051204020946/http://www.ross.net/crc/ ''The CRC Pitstop''] 
* Williams, R.（1993-09）[https://web.archive.org/web/20060927004051/http://www.repairfaq.org/filipg/LINK/F_crc_v3.html ''A Painless Guide to CRC Error Detection Algorithms'']
* [https://web.archive.org/web/20050408104838/http://www.4d.com/docs/CMU/CMU79909.HTM ''Understanding Cyclic Redundancy Check'']
* Black, R.（1994-02）[http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html ''Fast CRC32 in Software'']—Algorithm 4 is used in Linux and info-zip's zip and unzip.
* Barr, M.（[https://web.archive.org/web/20060621071959/http://www.netrino.com/Connecting/1999-11/ ''1999-11''], [https://web.archive.org/web/20060621072155/http://www.netrino.com/Connecting/1999-12/ ''1999-12''], [https://web.archive.org/web/20060621072010/http://www.netrino.com/Connecting/2000-01/ ''2000-01'']）checksums, CRCs, and their source code. Embedded Systems Programming 
* [https://web.archive.org/web/20060831082356/http://www.codeproject.com/cpp/crc32.asp CRC32: Generating a checksum for a file], C++ implementation by Brian Friesen
* Online [https://web.archive.org/web/20060702231245/http://serversniff.net/hash.php Tool to compute common CRCs（8/16/32/64）from strings]
* Online [http://www.zorc.breitbandkatze.de/crc.html CRC calculator] {{Wayback|url=http://www.zorc.breitbandkatze.de/crc.html |date=20220618044531 }}
* Online [http://www.easics.com/webtools/crctool CRC Tool: Generator of synthesizable CRC functions] {{Wayback|url=http://www.easics.com/webtools/crctool |date=20051125113717 }}
* [http://arquivo.pt/wayback/20100530092446/http%3A//home1.paulschou.net/tools/xlate/ Online Char(ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms]
* [http://apollo.backplane.com/matt/crc64.html CRC16 to CRC64 collision research] {{Wayback|url=http://apollo.backplane.com/matt/crc64.html |date=20220120165826 }}
* [http://sar.informatik.hu-berlin.de/research/publications/index.htm#SAR-PR-2006-05 Reversing CRC – Theory and Practice.] {{Wayback|url=http://sar.informatik.hu-berlin.de/research/publications/index.htm#SAR-PR-2006-05 |date=20220610150429 }}

{{-}}
{{Ecma标准}}

[[Category:校驗和算法]]
[[Category:二进制算术]]
[[Category:有限域]]