D-OS-Ch11eb-Cyclic_Redundancy_Check

Cyclic Redundancy Check (CRC)

CRC 是一種利用多項式除法偵測傳輸錯誤的機制。Sender 在資料後附上一段餘數，使得整個 bit string 能被雙方共知的 generator polynomial 整除；receiver 只要驗證整除性，就能判斷傳輸是否出錯。

Generator Polynomial

CRC 的數學基礎是選定一個 generator polynomial $K(x)$（sender 和 receiver 共享）。給定資料 $M(x)$ 和 $K(x)$ 的 degree $n$，可以寫出：

$$M(x)\times x^n=Q(x)\times K(x)-R(x)$$

移項後得 $M(x)\times x^n+R(x)=Q(x)\times K(x)$，表示 $M(x)\times x^n+R(x)$ 可以被 $K(x)$ 整除。Sender 送出的不是 $M(x)$，而是末尾附上餘數的 $M(x)\times x^n+R(x)$。

Modulo-2 arithmetic 中，加法和減法都是 XOR，因此 $-R(x)$ 和 $+R(x)$ 是同一件事。

Sender

給定 generator polynomial（bit string 長度為 $k$）和資料：

1. 在資料末端補 $k-1$ 個 0
2. 用 modulo-2 binary division 除以 $K(x)$，得到餘數 $R$（modulo-2 division 與十進位長除法相同，只是把減法換成 XOR）
3. 將 $R$ 附在原始資料後面送出

以 $M=100100$、$K=1101$（$N=6$，$k=4$）為例：

1. 補 $k-1=3$ 個 0，資料變為 $100100000$
2. $100100000÷1101$，餘數為 $001$
3. 送出 $100100001$

Receiver

Receiver 同樣持有 $K(x)$，對收到的 bit string 做 modulo-2 division：

• 餘數為 $0$：傳輸正確
• 餘數不為 $0$：有 bit 被翻轉，傳輸出錯

承上例，receiver 收到 $100100001$，除以 $1101$ 後餘數為 $0$，判定正確。若資料在傳輸中第 4 bit 遭翻轉變成 $100000001$，餘數變為 $011$，偵測到錯誤。