CRC是什麼？用0與1的除法找出傳輸錯誤的原理
CRC（循環冗餘檢查）是從資料算出簡短的檢查值一起傳送，再由接收端重新計算來發現錯誤的機制。計算的是只用0和1的「除法的餘數」，並以XOR代替減法，所以用小小的電路就能快速算出。有線網路、Wi-Fi、ZIP檔等都會用到，偶然發生的錯誤幾乎不會漏掉。不過，它無法更正錯誤，也無法識破蓄意的竄改。
這篇文章可以了解
- 用來發現錯誤的「檢查值」的概念
- 同位檢查和檢查碼（checksum）會漏掉的錯誤
- 用只有0和1的除法，手算求出CRC的方法
- 計算CRC的電路原理
- CRC一定能發現的錯誤，以及CRC做不到的事
先備知識：二進位，以及XOR（互斥或：2個輸入不同時輸出1的運算）。兩者都在「電腦怎麼用0和1計算？」中說明。
生活中的例子
你是否曾經在打開下載的ZIP檔時，看到「檔案已損毀」的訊息？ZIP檔裡，每個檔案都記錄著一個從內容算出的檢查值。開啟的軟體會重新計算同樣的值，如果不一致，就判斷檔案已損毀。這個值就是CRC。
資料是以0和1的排列來傳送與儲存的。在這過程中，0可能翻轉成1，1也可能翻轉成0。原因包括傳進纜線的電氣雜訊、微弱的電波，以及來自宇宙的粒子打到記憶體（軟錯誤）等。
這些都很少發生，但無法降到零。例如錯誤的比例即使只有1兆位元中1個，若每秒傳送10億位元，大約每17分鐘就會錯1個。因此，接收端需要有確認資料的機制。
附上檢查值的概念
商店商品上的條碼（EAN-13，日本稱JAN）通常是13位數字。最後1位，是由其他12位依固定的算法算出的檢查用數字。收銀機做同樣的計算，確認是否和最後1位一致，不一致就重新讀取。
「把從資料算出的簡短值一起送出，由接收端重新計算再比對」。這就是發現錯誤的基本概念。CRC也是同樣的概念，只是計算方法不同。
最簡單的檢查：同位檢查
對0和1的排列來說，最簡單的方法是數1的個數。在最後補上1個0或1，讓資料中1的個數成為偶數。這1個位元稱為同位位元。
例如1011001有4個1（偶數），所以補上0，傳送10110010。途中若只有1個位元翻轉，1的個數會變成奇數，就能發現錯誤。
但如果同時有2個位元翻轉，1的個數仍是偶數，錯誤就會被漏掉。雜訊往往會持續一段時間，相鄰的幾個位元容易一起出錯。這種成塊出現的錯誤，稱為叢發錯誤。出錯的位元若是偶數個，同位檢查就會漏掉。
用加法檢查：檢查碼
也有一種方法，是把資料切成16位元等大小的區塊，全部相加後附上總和。這稱為檢查碼（checksum），網際網路的IP和TCP都有使用（RFC 1071）。
不過，加法即使調換順序，答案也一樣。因此，區塊之間互換位置的錯誤，或某個區塊加1、另一個區塊減1的錯誤，都會被漏掉。CRC則在計算方法上下了工夫，連位元的位置都能區分。
CRC用在哪裡
CRC廣泛用於身邊的通訊和檔案。名稱後面的數字，是檢查值的位元數。
| 使用的地方 | CRC的種類 | 保護的對象 |
|---|---|---|
| 有線網路（乙太網路） | CRC-32 | 每次傳送的整個單位 |
| Wi-Fi | CRC-32 | 每次傳送的整個單位 |
| USB | CRC-5、CRC-16 | 簡短的指示、資料 |
| SD卡 | CRC-7、CRC-16 | 命令、資料 |
| PNG圖片 | CRC-32 | 檔案內的每個區段 |
| ZIP檔 | CRC-32 | 裡面的每個檔案 |
乙太網路把資料分成稱為「訊框」的單位來傳送，並在最後附上4位元組（32位元）的CRC。這個部分稱為FCS（訊框檢查序列）。
接收的設備會丟棄FCS不一致的訊框。乙太網路本身不會重送，缺少的資料由稱為TCP的機制重送。在Wi-Fi中，正確收到時接收端會回覆，沒有回覆就會重送（「Wi-Fi是怎麼運作的？」）。
原理1：沒有進位、只有0和1的計算
CRC的計算，是在和一般算術稍有不同的「只有0和1的世界」裡進行的。這個世界的加法規則只有以下3條。
- 0+0=0
- 0+1=1、1+0=1
- 1+1=0（沒有進位）
一般的二進位中，1+1=10會進位，但這裡把進位捨去。於是規則變成「兩者不同就是1，相同就是0」，和XOR的規則相同。也就是把加法電路（半加器）的進位輸出拿掉的樣子。
減法也是同樣的規則。0−1是「加上1會變成0的數」，由1+1=0可知是1。也就是說，在這個世界裡，減法和加法都是XOR。每一位都能和相鄰的位無關地計算，所以電路非常簡單。
在數學上，這個只有0和1的世界稱為GF(2)。GF是伽羅瓦體（Galois field）的縮寫，名稱來自19世紀的數學家伽羅瓦。在這篇文章中，只要記得「沒有進位的二進位計算」就夠了。
原理2：把0和1的排列看成多項式
接著，把0和1的排列改寫成稱為多項式的形式。多項式是像x²+3x+1這樣，把x的幾次方相加的式子。CRC把排列的每一位用「x的幾次方」當作名牌，該位是1就寫出來，是0就不寫。
例如1011，從左起依序是x³、x²、x¹、x⁰的位，所以寫成x³+x+1（x⁰寫成1）。這裡不是把數字代入x來計算，x的幾次方只是表示位數位置的記號。
寫成多項式後，就能運用數學上研究已久的多項式性質。因此能夠證明「哪些錯誤一定能發現」。
CRC中當作除數的多項式，稱為生成多項式。乙太網路的CRC-32是x³²+x²⁶+x²³+…+x+1這個32次的式子。規格書省略最高次的x³²，把其餘32位用十六進位寫成04C11DB7。十六進位是把二進位的4位寫成1個字元的方法。
原理3：用手算算看
用小例子來手算CRC。要傳送的資料是4位元的1101，生成多項式是x³+x+1，也就是1011。除數是4位，所以餘數是3位，得到3位元的CRC。
- 在資料後面補上和CRC位數相同的3個0，成為1101000（空出放CRC的位置）
- 在最左邊的1下方，對齊除數1011的左端寫下，做XOR
- 對結果中留在最左邊的1，再對齊1011做XOR。0的位就跳過
- 持續到除數超出右端為止。最後留下的右邊3位就是餘數，也就是CRC
這個例子做了4次XOR，得到餘數001。傳送端把這個餘數接在資料後面，傳送1101001。
和一般的直式除法不同，不需要比較「是否比除數大」。最左邊是1就做XOR，是0就前進到下一位。這種單純，正是CRC快速的原因。
接收端把收到的7個位元，直接用同樣的1011去除。沒有錯誤的話，餘數是000。因為附上餘數之後，整體已成為剛好能整除的排列。例如左起第3個位元出錯，收到1111001時，餘數會變成110，就能發現錯誤。
實際的規格會再加上一些約定。例如乙太網路的CRC-32，把計算的初始值全部設為1，最後再把所有位元反轉。初始值設為1，是為了連開頭多出或少了0的錯誤也能發現。
用CRC 計算工具，也能逐段看到這個除法。種類選CRC-8，寬度設3，生成多項式設3，資料格式選十六進位，再輸入0D。0D用二進位表示是00001101，開頭的0不會改變餘數。
原理4：用電路計算
在設備裡，CRC是由專用的小電路，在資料流進來的同時計算的。這種電路把記住1位元的電路串成一串，每來一次節拍訊號（時脈），就把內容往隔壁送1格。這稱為移位暫存器。
如果是3位元的CRC，就排3個記住1位元的方格A、B、C，並在2個地方放入XOR。資料從右邊1位元1位元進入，每次時脈往左前進1格。從左端C溢出的位元，會經由線路送回右邊，進入2個地方的XOR。
只有溢出的位元是1時，2個地方的位元才會反轉。這和直式計算中「最左邊是1就和1011做XOR」是同樣的操作。這種把輸出送回輸入端的接法，稱為線性回饋移位暫存器（LFSR）。依序送入1101和3個0，方格的內容會如下變化。
| 進入的位元 | 從C溢出的位元 | 之後的內容（C、B、A） |
|---|---|---|
| 1 | 0 | 001 |
| 1 | 0 | 011 |
| 0 | 0 | 110 |
| 1 | 1 | 110 |
| 0 | 1 | 111 |
| 0 | 1 | 101 |
| 0 | 1 | 001 |
最後留在方格裡的是001，和直式計算的餘數相同。CRC-32只是方格變成32個，XOR的位置也配合生成多項式的項而增加。
CRC一定能發現的錯誤
CRC的強項，在於能說「這種錯誤一定能發現」。只要生成多項式同時有最高次項和x⁰項（+1），以下性質就會成立。這是Peterson和Brown在1961年的論文中證明的性質。
- 只有1個位元的錯誤，不論發生在哪裡，都一定能發現
- 範圍不超過CRC位元數的叢發錯誤，不論其中有幾個位元出錯，都一定能發現（CRC-32為32位元以內）
- 更長的錯誤也幾乎都能發現。假設各種錯誤樣式發生的機會相同，32位元的CRC漏掉的比例約為43億次中1次（2的32次方分之1）
在各種資料長度下，幾個位元以內的錯誤能全部發現，取決於生成多項式的選擇。卡內基美隆大學的Koopman在2002年，調查了所有32位元的生成多項式。乙太網路的CRC-32，在最大長度的訊框中，能發現3個位元以內的所有錯誤。不過他也發現，還有更強的多項式。
反過來說，CRC會漏掉的，是錯誤樣式（哪些位元出錯）能被生成多項式整除的情況。以剛才的1101001為例，若左起第1、3、4個位元一起出錯，錯誤樣式就是1011000。它能被1011整除，所以餘數仍是000，無法察覺。這是跨越4個位元的錯誤，超出了3位元CRC的保證範圍。實際上會使用16位元或32位元的CRC。
CRC做不到的事
無法更正錯誤
CRC能知道錯誤「存在」，但通常無法告訴你錯誤在「哪裡」。發現錯誤之後，只能丟掉資料請對方重送，或通知資料已損毀。
要更正錯誤，就得增加檢查用的位元，設計成連哪個位元出錯都能知道。這稱為錯誤更正碼（ECC）。漢明在1950年發表的漢明碼，在4位元資料上加3位元，能更正1個位元的錯誤。伺服器用的ECC記憶體，每64位元加上8位元，能更正1位元的錯誤，並發現2位元的錯誤。
能更正更多錯誤的編碼，有里德和所羅門在1960年發表的里德－所羅門碼。它用於CD和QR碼，QR碼即使有一部分弄髒也能讀取，就是這個緣故。它和CRC一樣，使用多項式的計算。
能更正錯誤的編碼，檢查用的位元較多，計算也較重。在可以重送的通訊中，用輕量的CRC發現錯誤再重送，往往比較有效率。在無法重送的廣播、與太空之間的通訊等，則使用能更正錯誤的編碼。這稱為前向錯誤更正（FEC）。
無法識破蓄意的竄改
CRC的計算方法公開在規格中，也不使用祕密金鑰。竄改的人只要用新的資料重新算出CRC並換上即可。CRC發現的是偶然的錯誤，而不是惡意的竄改。
實際上，早期無線區域網路的加密方式WEP，曾用CRC-32來確認內容。2001年，Borisov等人證明，可以不解開加密就竄改內容，還能讓CRC也對得上。因為WEP的加密和CRC都只用XOR計算，所以能算出反轉哪些位元，會讓CRC的哪裡改變。
要發現竄改，要使用以祕密金鑰計算的訊息鑑別碼或數位簽章（「加密是什麼？」）。密碼學使用的雜湊函數，也設計成實際上無法做出相同值的另一份資料。而CRC卻能輕易做出這樣的資料。
同位檢查、檢查碼、CRC、ECC的差異
| 方法 | 能發現的錯誤 | 能否更正 | 使用場合的例子 |
|---|---|---|---|
| 同位檢查 | 奇數個位元的錯誤 | 無法更正 | 序列通訊（UART） |
| 檢查碼 | 多數的錯誤（會漏掉互換等） | 無法更正 | IP、TCP |
| CRC | 1位元錯誤和短的叢發錯誤一定能發現，其他也幾乎都能 | 通常不更正（重送） | 乙太網路、Wi-Fi、USB、檔案 |
| ECC（錯誤更正碼） | 一定數量以內的錯誤 | 能更正 | ECC記憶體、SSD、QR碼、CD |
常見的誤解
誤解：有了CRC，損毀的資料會自動修好
實際上，CRC只負責到發現錯誤為止。通訊中看起來像是修好了，是因為請對方重送了丟掉的資料。如果只有1個位元出錯，有時能從餘數的值推算出位置。名為ATM的通訊方式，就是這樣更正簡短標頭中的1位元錯誤。但2個位元以上的錯誤，可能被誤認為1位元的錯誤，所以通常只用來發現錯誤。
誤解：CRC對得上，就證明沒有被任何人竄改
實際上，竄改的人只要換上新的CRC，CRC就會對得上。能知道的只有「混入偶然錯誤的可能性很低」。要發現竄改，需要使用金鑰的訊息鑑別碼或數位簽章。因為名稱裡有「檢查」二字，看起來就像是安全的保證。
誤解：CRC越長，任何錯誤都能發現
實際上，不論CRC多長，都會漏掉能被生成多項式整除的錯誤。若是隨機的錯誤，32位元的CRC約43億次會漏掉1次。此外，CRC保護的只有從附上到檢查之間的區間。在附上CRC之前，就已在設備內損毀的資料，會被當成正確的資料通過。
從數字來看
| 數字 | 代表什麼 |
|---|---|
| 4位元組（32位元） | 乙太網路訊框最後附上的CRC（FCS）的大小 |
| 約43億次中1次 | 32位元的CRC漏掉隨機錯誤的大約比例 |
| 約每17分鐘1個 | 在1兆位元錯1個的傳輸路徑上，每秒傳送10億位元時的錯誤間隔 |
進一步學習
- 名詞的詳細解說：CRC（循環冗餘檢查）／同位位元／漢明碼／位元錯誤率
- 用數字試試看：CRC 計算工具／漢明碼計算工具／位元運算計算工具（試試XOR）
- 相關的解說：「網際網路怎麼傳送資料？」／「密碼為什麼會被破解？」