CRC檢查碼編碼

什麼是CRC檢查碼? What is CRC check code?

CRC檢查碼全名為循環冗餘校驗(Cyclic Redundancy Check)，利用數學多項式的概念實作，又稱為多項式碼(Polynomial code)，CRC將待傳輸的區塊視作一堆二進制連續位元，區塊即為上圖為網路七層OSI模型第二層傳送的訊框內部結構SFD到PAD的部分，CRC的工作就是將要傳送的區塊(即傳送的資料)除上一個特定除數，稱之為衍生多項式(Generation Polynomial)，大部分衍生多項式(Generation Polynomial)都由設計硬軟體廠商提供。

常見CRC檢查碼 Common CRC codes

最常見的CRC檢查碼位元數目有8、16、32，一般表示都是CRC-8、CRC-16、CRC-32，CRC編碼越長偵測能力越強大，然而得更多時間傳送更長CRC檢查碼，CRC-16能偵測一個區塊內一或兩個位元錯誤，或是奇數個位元錯誤，當資料位元長度超過17個時，偵錯率可高達99.9969%，而網路七層OSI模型第二層傳送的訊框(Frame)採用則是更高檢查碼位元CRC-32。

CRC碼怎麼算 ? How CRC check code works?

假設我們要傳送的資料為10101010，衍生多項式為X^4+X^2+X+1(10111，tip:多項式中常數項為1二進制填寫1，其餘為0)，CRC碼是由原始資料與檢查碼所組成的，概念和漢明碼相似。

步驟一、多項式最高幂次為4，所以我們在原始資料末端加上4個0，得被除數為101010100000。

步驟二、將步驟一被除數除以衍生多項式(10111)。

步驟三、將最後的餘數1100加到原始資料末端，於是CRC碼為101010101100。

驗證CRC碼 To prove CRC code is correct or not.

驗證方法也很簡單，將剛剛CRC碼（即原始資料+檢查碼）再次除以同樣的衍生多項式，若結果為整除代表，這個區塊的位元無誤。綜合以上，漢明碼、同位元檢查碼法使用checksum所遭遇到的問題，如超過兩個錯誤，就無法偵測，而CRC中，整個區塊任何一個位元發生變動，對於整個區塊之CRC值的影響該位元在區塊中的相對位置而定，換言之，CRC值可以判斷任何一個位元是否有變動，擁有牽一髮而動全生的效果。

參考 Reference

https://isite.tw/2015/03/22/13140

https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97

高點-計算機概論 經典題型解析（下冊）