循環冗余校驗

循環冗余校驗，是一種為數據確定校驗值的方法，以便能夠在傳輸或存儲過程中檢測錯誤。 理想情況下，該過程甚至可以獨立糾正接收到的數據以避免重傳。

在存儲或傳輸數據之前，以所謂的 CRC 值的形式將附加冗余添加到用戶數據的每個數據塊。 這是根據特定程序計算的測試值，可用于識別在存儲或傳輸過程中可能發生的任何錯誤。 為了驗證數據，將相同的計算方法應用于包括附加的 CRC 值的數據塊。 如果結果為零，則可以假定數據塊未損壞。 然而，各種技術應用都偏離了該方案，例如通過使用特定值初始化計算或通過在傳輸之前反轉CRC值。

CRC 的設計方式使得數據傳輸中的錯誤（例如由線路上的噪聲引起的錯誤）很有可能被檢測到。 串行數據傳輸的 CRC 可以很容易地在硬件中實現。 例如，以太網上的數據傳輸和大多數硬盤驅動器傳輸都使用 CRC 程序進行檢查。

CRC 方法僅設計用于檢測隨機錯誤。 它不適用于確認數據的完整性。 也就是說，通過有意修改創建與給定消息具有相同 CRC 值的數據流相對容易。 如果需要這種安全性，則必須使用加密散列函數（例如 SHA）或簽名函數（例如 RSA）。

該方法的名稱來源于這樣一個事實，即附加值沒有不包含在底層數據塊中的信息內容。 因此它是多余的。 CRC 基于循環碼。 這些是塊代碼，具有有效代碼字的比特的每個循環移位也是有效代碼字的屬性。

CRC 值的計算基于多項式除法：要傳輸的位序列被視為二進制多項式。

數據的代碼表示的位串除以預定的生成多項式（CRC 多項式）模 mod(2)，留下余數。 這個余數就是 CRC 值。 傳輸數據塊時，CRC 值附加到原始數據塊并同時傳輸。

為了驗證數據不包含任何錯誤，將接收到的帶有附加 CRC 值的數據塊解釋為二進制序列，再次除以 CRC 多項式模并確定余數。 如果沒有余數，則要么沒有錯誤發生，要么發生（非常不可能的）錯誤，該錯誤將 CRC 多項式作為多項式表示中的一個因素。

需要注意的是，與 CRC 通信的 ones 和 zeros 并不是數字的表示，而是多項式。 這意味著例如用袖珍計算器對二進制數（或一般數字）進行模除法不會得出正確的結果。

數據傳輸需要某些必要的協議。 一方面，接收者必須意識到原始數據的安全傳輸是完全發生的。 僅從傳入數據流的類型無法識別這一點。 另一方面，接收方必須使用與發送方相同的CRC多項式和計算方法。 最后，接收方必須知道除了數據之外傳輸的校驗和在數據流中的位置。

CRC 方法既可以在簡單的硬件組件中實現，也可以在軟件中實現。 一個被使用

• n位的移位寄存器，其中n是生成多項式的次數（大約是CRC-32中的32位移位寄存器）和a
• 任意長度的位數據流后跟 n 個零位。

算法偽代碼，最高位最左邊，乘以2表示左移一位：

crc := 0000 ...（起始值）對于數據流中的所有位 b：如果 crc 的最左邊位為 1：crc := (crc * 2 + b) xor CRC 多項式 否則：crc := crc * 2 + bcrc包含結果。

在 CRC-8 的情況下，通過使用包含 256 個可能字節中的每一個的關聯 CRC 值的表，上述算法可以加速 8 倍。 這是因為表條目包含 8 位 = 1 字節和基位置 = 2 8 = 256 不同的表條目存在。 速度的提高是通過使用要計算的位序列直接訪問表來實現的，因為所尋求的 CRC-8 計算位于表中具有要計算的位序列的二進制值作為索引的位置.

左移和異或操作使 CRC 非常適合在邏輯電路中使用。 數據流的 CRC 可以逐位（或逐字節等）計算，并由發送方附加到數據中。 數據流的接收方可以采用與發送方相同的方式計算 CRC，但包含 CRC。 包括 CRC 的結果必須等于零，否則流包含位錯誤。

CRC 類型通常通過用作除數的多項式（十六進制格式）來區分。 最常用的 CRC 之一（以太網、FDDI、ZIP 和 PNG 等使用）是 0x04C11DB7 多項式，稱為 CRC-32。 事實證明，一些多項式比其他多項式“保護”得更好。 常用于 CRC 的多項式是廣泛的數學和經驗分析的結果，而不是隨機數，盡管它們看起來很像。

如果 0000... 用作起始值，則該實現執行多項式除法。 您經常會發現其他起始值。 如果數據流的前 n 位被反轉，則這對應于多項式除法。

起始值不等于 0000... 是更可取的，因為否則將無法識別數據流中前導零內丟失的位（就像普通除法一樣，前導零不計入多項式除法）。