2020年10月31日 星期六

CRC 生成多項式 計算方法與專有名詞紀錄(一)

 

最近的工作需要計算CRC的檢查碼,所以在google上找了一些資料,找資料的過程中,把找到的資料記錄下來,免得以後要再次計算時,又要重新找資料。

CRC 是Cyclic redundancy check的縮寫,所以在google的時候,可以用完整的名詞去找可以找到比較正確的資料。

在找資料的時候,會看到一些專有名詞,某些網站有解釋,但有些網站沒有去解釋這些名詞,所以這邊簡單紀錄一下我找到的東西。這裡不做學術上的探討,只是記錄我怎麼看懂這些東西的方式。

生成多項式: 

用來對資料做檢查的pattern,例如 CRC-8/MAXIM的生成多項式是X^8+X^5+X^4+1 ,用位元表示就是100110001,如果把最後的那個bit拿掉,就是10011000,可以看到X^8代表最左邊的位元是1,X^5代表第五個位元是1(由右往左算,base為1開始算),X^4代表第四個位元是1,那生成多項式X^8+X^5+X^4+1,最後的那個+1就是在原本8個bit最左邊加上一個bit的1。所以如果有一個生成多項式是X^16+X^12+X^5+1,他的2位元pattern就是10001000000100001,全部就有16+1個bit

Poly: 

生成多項式的簡易寫法,假設生成多項式是 X^8+X^5+X^4+1,他的2位元pattern就是100110001,16進位的寫法為131,又因為通常最左邊的那個位元都是1,所以為了表示方便,當我們把最左邊的那個bit為1的部分拿掉以後,就是00110001,而00110001就是16進位的31,3這個值就是Poly表示法,所以X^16+X^12+X^5+1的2位元表示法為10001000000100001,16進位表示法為11021,把最左邊的那個bit拿掉,就會是0001000000100001,16進位為1021,1021就是X^16+X^12+X^5+1這個生成多項式的poly表示法。

Width: 

指的就是檢查碼的長度,像是CRC-8/MAXIM這個模式,就是8個bit的寬度。CRC-16/CCITT就是16個bit。只是我們實際使用的時候會在最右邊加上一個bit為1的位元。

refin:

refin就是指我們要被檢查的資料要怎麼排列來開始做運算,例如我們要驗算一組資料,以16進位HEX表示為 0x01 0xA0,2進位表示為00000001 10100000,如果refin=true,代表我們需要把每一個位元組(byte)內的bit順序做反轉,但是位元組(byte)順序不做反轉,如果0x01 0x0A在refin=true的時候,計算時就要反轉成 100000000 00000101  這樣的順序下去做計算。如果refin=false時,代表不用做任何反轉,直接計算。

refout:

若為true,計算結果必須反轉才是答案,若為false就直接是答案。例如: 在refout為true的情況下,我們取得一個計算結果是11011011001000,那答案就是 00010011 011011,那因為這是用CRC16/CCITT模式運算的結果,所以應該會有2個byte的結果,但因為結果只有14bit,所以最後捕兩個0給他就是完整答案了,完整答案就是00010011 01101100,16進位表示法就是0x13 0x6C這兩個Byte。



參考資料:

https://www.lammertbies.nl/comm/info/crc-calculation

https://www.scadacore.com/tools/programming-calculators/online-checksum-calculator/

https://reveng.sourceforge.io/crc-catalogue/all.htm

http://www.ip33.com/crc.html

https://blog.csdn.net/pl0020/article/details/82760761





沒有留言:

張貼留言