CRC16-CCITT

(內文如有算錯請多包涵)
為了寫實驗室的通訊協定(Modbus)，學長要求要寫CRC，還特別指定CRC16的CCITT，聽都沒聽過，所以就先來了解一下CRC是什麼好了。

以我這種外行人來說，我只要知道它的規則和大致的原理就好~ CRC簡單來說就是把一筆資料加上一定數量的0，讓資料可以被規定的CRC函數除，留下一個餘數就是CRC了。

CRC16 CCITT的函數就是 X^16+X^12+X^5+1; 那麼用二進位看它的係數可以看成 17'b10001000000100001(當成除數); 啊如果一筆資料進來要怎麼辦呢？

以正常來說，假設一筆資料是 8'b11111111; 那麼就會補跟函數最高次方一樣多的0，CCITT的是16次方，所以資料後面要加上16個0。

就變成了 24'b111111110000000000000000。為什麼要加上16個0呢？因為除數是17位的話，餘數最長就是16位。來看看要怎麼算好了！

這個除法不是一般的除法，一般的除法是用減的，可是這邊是用XOR來做運算。 XOR就是 11 = 0，00 = 0，01=1，10=1。

111111110000000000000000 被除數(資料)

10001000000100000 除數

================== 做XOR運算(上下)

01110111000100000 得到了餘數，扣去MSB不看，只剩下十六位，除數有十七位呢！所以在抓一個0下來補吧。

11101110001000000 加一個0之後又是十七位了，又可以跟除數做運算了。%%% 如果第十六位也是0的話，就要抓兩個0哦~以此類推%%%

10001000000100000 除數

================== 做XOR運算(上下)

01100110001100000 這裡又得到一個餘數，第十七位還是0，那就繼續抓0做下去。理論上這樣做下去，做到被除數(原本有24位)只剩下17位的話，再跟除數做一次運算得到的餘數，那就是我們要的CRC碼了。

人家的文章也寫得不錯，奇偶校檢位也是一種很簡單的CRC，它的函數就是X+1。所以除數就是2'b11。資料如果是8'b10110101

運算結果應該是 101101010

011

00010

000011

000000010

1 結果是1 所以有奇數個1在資料裡。

當然理論上是這樣啦，實際上是什麼？？？我查了很久，終於在一個有CRC-CCITT的device中的datasheet找到真正的算法（或是演算規則）

第一步：先假設我們要算的CRC = 16'hFFFF ; 然後我們要的除數是16'h1021;(CCITT的函數)

第二步：先把資料的後端加上8個0，讓資料變成16位，然後把CRC跟資料做XOR，會得到一組新的CRC;

第三步：如果上一步新的CRC如果最高位是1(也就是data[15]是1)，那就把資料先左移一位，然後跟除數16'h1021做XOR，得到的結果再跟16'hFFFF做AND。

否則，就直接左移一位，再跟16'hFFFF做AND。如此這個規則重複"八次"之後，就會把一個byte(8個bit)的資料都跟除數演算過了。得到的結果就是CRC碼嘍。

如果有很多個byte怎麼辦？第三步的結果只會得到一個byte的CRC，那就就把第三步得到的CRC帶回第一步去，所以第一步的CRC不在是FFFF了，而是你算出第一筆資料的CRC，

然後第二步再放新的資料進來跟第一步新的CRC做XOR，接著再做第三步。就是這樣！

便當的部落格