差錯檢測 — 循環備援校驗CRC

　　現實中通信鍊路都不會是理想的，比特在傳輸的過程中可能會出現差錯，1可能變成0，0也可能變成1，這就叫做比特差錯。比特差錯是傳輸差錯的一種，是以為了保證資料傳輸的可靠性，在計算網絡傳輸資料時，必須采用各種檢驗措施來處理比特差錯。目前在資料鍊路層廣泛使用了循環備援的CRC的檢錯技術。

• 幀檢驗序列FCS（Frame Check Sequence）：為了進行差錯檢驗而添加的備援碼。
• 模2運算：即按位異或運算，不考慮進位與借位，相同為0，不同為1（做除法時每一步餘數的首位逢一商一 逢零商零）
• 發送方和接收方事先商定的長度為（n+1）位的除數P，用多項式 P(x) 表示更為友善，又稱生成多項式。
• 由（k-1）次多項式表示的 k 位比特消息 M(X)，每一比特位的值為 對應其每項多項式的系數，且從為高位比特開始。如一個8比特10011010對應的多項式為 M(x)=x^7 +x^4 +x^3 +x^1。
• n位備援碼：用二進制的模2運算進行2^n乘以M 的運算，相當于在M的後面添加n個0。

循環備援檢驗的原理：在發送端，先把資料劃分成組，假定每組k個比特并作為M，CRC運算就是在資料M的後面添加供差錯檢測用的n位備援碼，然後構成一個幀（k+n）位 并發送出去。将得到的（k+n）位的數除以收發雙方事先商定的（n+1）位的除數P，得出的商是Q，而餘數是R（n位，比P少一位）。在接收端把接受到的資料以幀為機關進行CRC檢驗：即把收到的每一個幀都除以P（模2運算），然後檢查得到的餘數R，如果傳輸無差錯，那麼R肯定是0，就接受；如果R≠0，則判定這個幀有差錯（無法确定是哪幾位出現差錯），就丢棄。

有效資訊為1010001101，生成多項式p(x)=110101 , 求其CRC編碼? 

答：如圖所示（模2運算）

餘數為01110，CRC編碼為101000110101110