[教學] 循環冗餘碼(Cyclical Redundancy Check)－一個小小工程師的心情抒發天地

循環冗餘碼(Cyclical Redundancy Check)

循環冗餘校驗（英語：Cyclic redundancy check，通稱「CRC」）是一種根據網路資料封包或電腦檔案等資料產生簡短固定位數驗證碼的一種雜湊函式，主要用來檢測或校驗資料傳輸或者儲存後可能出現的錯誤。生成的數字在傳輸或者儲存之前計算出來並且附加到資料後面，然後接收方進行檢驗確定資料是否發生變化。一般來說，循環冗餘校驗的值都是32位元的整數。由於本函式易於用二進制的電腦硬體使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。此方法是由W. Wesley Peterson於1961年發表^[1]。

一樣，我們用一個題目來解釋，並且用程式表達出來。

Ex :Assume that the sender sends the codeword 1101101 , please find

the CRC code and
Codeword for a generator polynomial x^3 + x^2 + 1

Step1. 取得餘數 & 被除數

除數 :

所以，除數為 1101

被除數 : 1101101 (codeword) +最高系數是多少，就補多少個0(就是看最高次方是誰，就補多少個0，在這邊我們最高次方式3次方，所以就得補3個0。

所以，被除數為:1101101000

Step2:使用除法

使用說明: 一般的除法是減法，但是在CRC是需要用XOR，並且遵守下列三個規則。

使用XOR
一次下來三位
遇到第一位為1的時候，就用1去除，反之遇0則用0去除。

Ans :

A)110

B)1101101(codeword)+110(CRC) = 1101101110

接下來，我們寫點code吧 !

#include <iostream>
#include <string>

#define MAX_LENGTH 50

using namespace std;

int main()
{
   cout <<"Assume that the sender sends the codeword 1101101,please find"<<endl
       <<"a) the CRC Code and "<<endl
       <<"b) codeword for a generator polynomial x^3+x^2+1 " <<endl;
   /*
       long type = 4byte = 32 bit
   */
   long lCodeWord = 109 ; //1101101

   /*
       generator polynomial : x^3 + x^2 + 1
       x^3 + x^2 + 1 = 1101(2)->13(10)
   */
   long lGenerate = 13 ;

   char g_add[MAX_LENGTH];
   char s_end[MAX_LENGTH];
   itoa(lCodeWord, s_end, 2);
   itoa(lGenerate, g_add, 2);
   char len_g = strlen(g_add);
   lCodeWord = lCodeWord<<(len_g-1);
   //cout<<generate<<endl;

   itoa(lCodeWord, g_add, 2);
   char len_s = strlen(g_add);
   long temp;
   while(len_s >= len_g)
   {
       temp = lGenerate<<(len_s-len_g);
       lCodeWord = lCodeWord^temp;
       itoa(lCodeWord, g_add, 2);
       len_s = strlen(g_add);
   }
   strcat(s_end, g_add);
   cout <<"------------------------Result------------------------"<<endl;
   cout <<"a) the CRC Code : " <<g_add<<endl
       <<"b) the CodeWord : " <<s_end<<endl;

}