什麼是 CRC

CRC 錯誤偵測技術 作者:常世勳
即是所謂的循環冗餘檢查碼 (Cyclic Redundancy Check Code) ，簡稱 CRC 碼，它是由待傳輸的資料區塊計算出的，CRC 的計算方式是將待傳 輸的區塊視為一堆連續位元所構成的一整個數值，並將此數值除以一特 定的除數，通常以二進位表示，此除數又稱為衍生多項式 (Generation Polynomial)，該除數一般皆由設計硬體或軟體的廠商所提供，而除數 值位元數目則視欲得到的 CRC 位元數目而定，目前較常使用的 CRC 位 元數目有 8、16 或 32，一般縮寫為 CRC-8、CRC-16、CRC-32，通常， CRC 碼越長，則數據發生干擾卻不反應在 CRC 值的機率也就越低，不 過得多花些時間傳送較長的 CRC 碼。根據理論統計，CRC-16 可完全偵 測資料區塊內單一或兩個位元的錯誤、奇數個位元的錯誤、連續 16 個 位元或少於此數的錯誤，超過 17 個連續位元的錯誤偵測率則有 99.9969% ，其它位元長度的錯誤偵測率則可達 99.9984% 。 底下是一些數學符號所表示的 CRC 碼運算過程。吾人可將待傳送的區 塊資料位元串表示成一個很大的二進位數字，並令此數字等於 F，例如 ，底下是某個區塊的位元串所連成的二進位數字:
F = 1011010111110111101110100100101110101... (區塊資料)
假設目前欲求 F 的 16 位元 CRC 值，並且，廠商所提供的衍生多項式 是:
16 12 5 G(x) = x + x + x + 1 (衍生多項式)
其中，x 是所採的進制，在二進位系統，x = 2，則 G 的值為:
G = 1,0001,0000,0010,0001 (二進位數字)
底下的式子中的餘數 C 即是 F 的 16 位元 CRC 值:
16 F ‧ 2 = A ‧ G + C
由於 C 是此式中的餘式，故稱此值為 Redundancy。 例如，底下即是透過上述的 G(x) 求得 11010101 (D5H) 的 CRC 值: A ┌───────────────── 1,0001,0000,0010,0001│1101,0101 ‧ 1,0000,0000,0000,0000 ╯...... ────────────────── (二進位長除法) 16 位元 CRC 值 → 1001,1011,1101,1000
衍生多項式的數值將影響到所產生的 CRC 值，根據理論計算，當衍生 多項式的數值恰為某些特定值時，所產生的 CRC 值最 "亂" ，換句話 說，它偵測資料受雜訊干擾的能力越高，在上個範例中所採用的多項 式也是 PC/XT 控制卡上μPD765A 所採用，該多項式也是 CRC-CCITT v.41 所制定的標準，而目前在許多通訊上的應用亦採用此值。 理論上，在計算 CRC 時非常簡單，只要一個除法運算即可，運算之後 的餘數即是 CRC 值，但實際上所被除數 F 的位元數目可能以萬為單 位，如何利用程式以最簡易、最快的方式求得該餘數也是技術關鍵所 在。事實上，各式的檢查碼也不僅應用在網路通訊上，和數據的存取 、儲存、傳輸等類似的範疇也會用到，例如磁碟片或磁帶機上資料的 儲存即是，在 Apple 個人電腦的磁碟機即是利用 checksum 驗證所存 取資料的正確性，而 PC 的磁碟機則使用 CRC。