CRCA

CRCA

CRCA（CyclicRedundancyCodeAccumulator），即循環冗餘碼累加器。在數據存儲和數據通訊領域，為了保證數據的正確，就不得不採用檢錯的手段。在諸多檢錯手段中，CRCA是最著名的一種。CRCA的全稱是循環冗餘校驗，其特點是:檢錯能力極強，開銷小，易於用編碼器及檢測電路實現。從其檢錯能力來看，它所不能發現的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優於奇偶校驗及算術和校驗等方式。因而，在數據存儲和數據通訊領域，CRCA無處不在:著名的通訊協定X.25的FCS(幀檢錯序列)採用的是CRC-CCITT，ARJ、LHA等壓縮工具軟體採用的是CRC32，磁碟驅動器的讀寫採用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。

CRCA的本質是模-2除法的餘數，採用的除數不同，CRCA的類型也就不一樣。通常，CRC的除數用生成多項式來表示。由於CRCA在通訊和數據處理軟體中經常採用，在實際工作中對其算法進行了研究和比較，總結並編寫了一個具有最高效率的CRC通用程式庫。該程式採用查表法計算CRC，在速度上優於一般的直接模仿硬體的算法，可以套用於通訊和數據壓縮程式。

通常的CRCA算法在計算一個數據段的CRC值時，其CRC值是由求解每個數值的CRC值的和對CRC暫存器的值反覆更新而得到的。這樣，求解CRC的速度較慢。通過對CRC算法的研究，我們發現:一個8位數據加到16位累加器中去，只有累加器的高8位或低8位與數據相作用，其結果僅有256種可能的組合值。因而，我們可以用查表法來代替反覆的運算，這也同樣適用於CRC32的計算。本文所提供的程式庫中，函式crchware是一般的16位CRC的算法；mk-crctbl用以在記憶體中建立一個CRC數值表；crcupdate用以查表並更新CRCA累加器的值；crcrevhware和crcrevupdate是反序算法的兩個函式.

CRCA的工作方法：在傳送端產生一個循環冗餘碼，附加在信息位後面一起傳送到接收端，接收端收到的信息按傳送端形成循環冗餘碼同樣的算法進行校驗，若有錯，需重發。

2.循環冗餘碼的產生與碼字正確性檢驗例子。

例1.已知：信息碼:110011　信息多項式:K(X)=X5+X4+X+1

生成碼:11001　生成多項式:G(X)=X4+X3+1(r=4)

求：循環冗餘碼和碼字。

解：1)(X5+X4+X+1)*X4的積是X9+X8+X5+X4對應的碼是1100110000。

2)積／G(X)(按模二算法)。

由計算結果知冗餘碼是1001，碼字就是1100111001。

__________100001←Q(X)

G(x)→11001)1100110000←F(X)*Xr　

11001　，

　10000

　11001

1001←R(X)(冗餘碼)

例2.已知：接收碼字:1100111001　多項式:T(X)=X9+X8+X5+X4+X3+1

生成碼　:11001生成多項式:G(X)=X4+X3+1(r=4)

求：碼字的正確性。若正確，則指出冗餘碼和信息碼。

解：1)用字碼除以生成碼，餘數為0，所以碼字正確。

100001←Q(X)

11001)1100111001←F(X)*Xr＋R(x)　

G(x)11001　，

　11001

　11001

　0←S(X)(餘數)

2)因r=4，所以冗餘碼是：1001，信息碼是:110011

循環冗餘碼的工作原理:循環冗餘碼CRC在傳送端編碼和接收端校驗時，都可以利用事先約定的生成多項式G(X)來得到，K位要傳送的信息位可對應於一個(k-1)次多項式K(X),r位冗餘位則對應於一個(r-1)次多項式R(X)，由r位冗餘位組成的n=k+r位碼字則對應於一個(n-1)次多項式T(X)=Xr*K(X)+R(X)。

循環冗餘校驗碼的特點:

1)可檢測出所有奇數位錯；

2)可檢測出所有雙比特的錯；

3)可檢測出所有小於、等於校驗位長度的突發錯。