CRC循環備援檢驗算法

1.為什麼要有CRC循環備援檢驗算法

資料在網絡的傳輸過程中，都是以二進制資料傳輸，即不是0，就是1；資料傳輸過程中，因為各種可能的原因導緻資料0變為1，1變為0。為了保證傳輸資料的可靠性，在計算機網絡傳輸時，必須采用各種差錯檢測措施；

CRC是我們運用在資料鍊路層的差錯檢驗算法；

2.CRC循環備援檢驗算法的原理

舉例說明如何得到幀檢驗序列FCS

• 假設待傳輸的資料M=101001（k=6）,CRC算法就是在資料M後添加供差錯檢測的n位備援碼，構成大小為（k+n）比特的資料幀發送出去；
• 利用模2運算（加法時不進位，減法時不借位，即1+1 = 0,0-1 = 1），2^n乘M，相當于二進制數M左移n位，後面n位補0，得到（k+n）位數除以事先雙方約定好的（n+1）位的除數P，得到的商Q和餘數R（n位），我們将餘數作為幀檢驗序列FCS；
• 例如我們事先約定好P = 1101,則n = 3;則（6+3位）被除數為101001 000，除數p(6位)為1101，利用模2除法，可以得到商Q = 110101，餘數（3位）R = 001，那麼001即為M = 101001的幀檢驗序列FCS，即發送的資料為101001001

當我們收到一個資料幀時，如何利用CRC算法判斷該資料有無傳輸差錯？

将接收到的資料與實作約定好的除數P相除，得到的餘數R

• 若餘數R = 0；則表明該幀沒有傳輸錯誤；
• 若餘數R！=0；則表明該幀有差錯，直接丢棄

3.CRC循環備援檢驗算法解決了資料鍊路層上實作資料比特差錯的控制，單着還不是真正的可靠傳輸，因為資料除比特差錯外，還可能有幀丢失、幀重複或幀失序等問題

4.舉例說明FCS計算過程

【例】假設使用的生成多項式是G(x)=x3+x+1。4位的原始封包為1010，求編碼後的封包。

　　解：

• 将生成多項式G(x)=x3+x+1轉換成對應的二進制除數1011;
• 此題生成多項式有4位（n+1），要把原始封包C(x)左移3（n）位變成1010000 ;

• 用生成多項式對應的二進制數對左移3位後的原始封包進行除：

  　　這裡的除法有兩種方法

  　　一種是把原二進制轉化為10進制，然後進行除法運算得到餘數。将這個餘數再轉化為二進制，就是要填在後面的二進制數了(這個可能有誤……)

  　　如此例

  　　1010000(原始封包移位後)轉換為十進制為80

  　　1011(生成多項式)轉換為十進制為11

  　　11除80，餘數為3

  　　轉化為二進制位011

  　　這個011就是要在後三位的校驗碼

  　　編碼後的封包（CRC碼）：

  　　1010000

  　　+ 011

  　　——————

  　　1010011

  　　

  第二種方法是模二除法