計算機體系結構：循環冗餘校驗 CRC 原理與多項式編碼

CRC 定義與特色

最常用差錯校驗碼。資訊欄位與校驗欄位長度可任意選定。廣泛應用於網路通訊與磁碟儲存。

多項式表示法

二進制數對應多項式：1011 → x³ + x¹ + x⁰。最高次冪 n 對應長度 n+1 二進制數。

CRC 編碼結構

K 位資訊碼 + R 位校驗碼 = N 位編碼。稱為 (N, K) 碼。

編碼流程 (概念)

1. 選定產生多項式 G(x) (雙方協定)
2. 資訊多項式 M(x) 左移 R 位 (乘 x^R)
3. 以模 2 除法 (XOR) 除以 G(x)，餘數為校驗碼 C(x)
4. 傳送碼字：M(x)·x^R + C(x)

接收端驗證

接收碼字除以 G(x)，餘數為 0 視為無錯誤，非 0 則有錯誤。

常見產生多項式

• CRC-16: x¹⁶ + x¹⁵ + x² + 1
• CRC-32 (Ethernet/ZIP/PNG): x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1