【電子技術】什麼是循環冗餘碼CRC

0 前言

現實的通信鏈路都不會是理想的。這就是說，比特在傳輸的過程中可能會產生差錯：1可能會變成0，0可能會變成1，這就叫做比特差錯。因此，為了保證數據傳輸的可靠性，在計算機網絡傳輸數據時，必須采用各種差錯檢測措施。
目前在數據鏈路層廣泛使用了循環冗餘檢測CRC的檢測技術。

1 CRC的原理

CRC運算實際上就是在數據長為k的後面添加供差錯檢測用的n比特冗餘碼，然後構成幀k+n比特發送出去。

選擇一個生成多項式，作為對接收的幀進行除法運算時的除數，生成多項式可以寫為二進制形式；生成多項式的要求：
①最高比特和最低比特必須為1；
②當CRC碼的任何一比特發生錯誤時，新幀除生成多項式後餘數不為0；
③不同比特發生錯誤時，餘數應該是不同的；

計算n比特冗餘碼
現假定待傳輸的數據M = 101001(k = 6)，除數p = 1101 (n = 3，p比n多一比特)
這n比特冗餘碼可以用下面的方法得出。
(1)用二進制的模2運算進行(2^n)乘M的運算,相當於在M後面添加n個0。
即M後面添加3個0
(2)現在得到M = 101001000(k+n = 9)比特的數除以除數p(n = 3)比特，
得到餘數R =001（n比特），R就是冗餘碼FCS

現在加上CRC後發送的幀是101001001

在接收端把接收到的數據M = 101001001以幀為單比特進行CRC檢驗：把收到的每一個幀都除以相同的除數p(模2運算)，然後檢查得到的餘數R。
如果在傳輸過程中沒有差錯，那麼經過檢驗後得到餘數R肯定是0。
(讀者可以自己檢驗下，被除數現在是M = 101001001,除數P= 1101，看餘數是否為0)
總之，在接收端對接收到的每一個幀經過CRC檢驗後，有兩種情况：
(1)餘數R = 0，則判斷這個幀沒有問題，就接受
(2)餘數R != 0,則判斷這個幀有差錯，就丟弃。

2 CRC的實例

假設CRC生成多項式G(X)=X5+X4+X+1，要發送的二進制數據幀為100101110，求CRC校驗碼:

①把生成多項式轉換為二進制數：110011；

②由生成多項式的比特數為6可知，CRC校驗碼的比特數為5，所以在數據幀後加5個0，變為10010111000000，將這個數使用模2除法除以生成多項式110011，得到餘數即CRC校驗碼11010；

③用得到的CRC校驗碼替換掉數據幀中的5個0，形成新的幀10010111011010，將這個新幀發送給接收端；

④接收端收到新幀後，用新幀除以上面的多項式110011（模2除法），如果餘數為0，該數據幀在傳輸過程中沒有出錯，否則出錯；（經驗證餘數為0）