天天看點

CRC(Cyclic Redundancy Check)-循環備援校驗 學習筆記

作者:蛋蛋二少爺

CRC 是對資料包或者儲存檔案的一種資料校驗和資料糾錯算法;是利用除法和餘數原理,計算擷取校驗資料,并組成新的資料包。資料發送端通過CRC計算得到備援資料,并打包形成新的資料包發送;資料接收端對接收資料包進行CRC校驗,餘數為0則證明傳輸資料無誤。

如下圖為CRC資料處理示意圖,即在原始資料(K bit)後面再增加校驗資料(R bit),構成新的資料包((K+R) bit);而校驗資料是原始資料做除法運算後的餘數。

CRC(Cyclic Redundancy Check)-循環備援校驗 學習筆記

發送端資料CRC主要包括下述5個過程:

1. 确認CRC對應的多項式

既然是基于除法運算,就肯定有除數;而除數也是基于二進制的方式實作的,采用模2除法;

二進制除數與多項式之間存在對應關系,比如:

二進制除數為: 1101.

對應的多項式為: G(x)=X^3+X^2+1

多項式一般是由接收端和發送端協商确認,标準的CRC算法的多項式如下表所示:

CRC(Cyclic Redundancy Check)-循環備援校驗 學習筆記

是以,确認了CRC标準後,也就得知了CRC對應的除數。

2. 确認CRC校驗資料的位數

校驗資料實際是除法運算後的餘數,是以需要确認餘數的位數;

而多項式與餘數位數的對應關系為: 多項式的最高次幂為對應的餘數位數;

比如多項式G(x)=X^3+X^2+1 最高為3次幂,是以餘數位數為3,即校驗資料的位數為3。

3. 移位,補充校驗位

将原始資料左移R bit,低位補0

比如:

原始資料為:10011010,校驗資料位數為3;則左移3位,形成新的資料:10011010_000

4. 計算CRC校驗資料

用除數,對移位後資料做模2除法運算,得到的餘數即為CRC校驗資料;

比如:

原始資料: 10011010,

移位後資料:10011010_000

多項式為G(x)=X^3+X^2+1

模2除法運算,實際是異或運算,得到餘數為:0101,實際要求餘數位數為3bit,是以校驗資料為101

CRC(Cyclic Redundancy Check)-循環備援校驗 學習筆記

5. 組成新的資料包

新的資料包為: 原始資料+校驗資料(餘數),即為:10011010_101

接收端接收到資料包後,理論上該資料包已經加上了餘數,是以正常情況下應該能夠被除數整除而餘數為0,是以接收端需要做的事情就是用協商的多項式(G(x)=X^3+X^2+1)對接收到的資料(10011010_101)進行異或運算,餘數為0則說明資料傳輸無誤。

CRC還可以實作對資料的糾錯功能,以及CRC深入的原理,這個還沒學會,學會了再分享。

繼續閱讀