循環冗余校驗碼的軟件實現


　　在遠距離數據通信中，為確保高效而無差錯地傳送數據，必須對數據進行校驗即差錯控制。循環冗余校驗CRC(Cyclic Redundancy Check)是對一個傳送數據塊進行校驗，是一種高效的差錯控制方法。

1　循環冗余校驗碼原理

　　CRC校驗采用多項式編碼方法，如一個8位二進制數(B7B6B5B4B3B2B1B0)可以用7階二進制碼多項式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。
　　例如11000001可表示為
　　1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0
　　一般說，n位二進制數可用(n-1)階多項式表示。它把要發送的數據位串看成是系數只能為“1”或“0”的多項式。一個n位的數據塊可以看成是從Xn-1到X0的n項多項式的系數序列，位于數據塊左邊的最高位是Xn-1項的系數，次高位是Xn-2項的系數，依此類推，位于數據塊右邊的最低位是X0項的系數，這個多項式的階數為n-1。
　　多項式乘除法運算過程與普通代數多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進、錯位，如同邏輯異或運算。
　　采用CRC校驗時，發送方和接收方事先約定一個生成多項式G(X)，并且G(X)的最高項和最低項的系數必須為1。設m位數據塊的多項式為M(X)，生成多項式G(X)的階數必需比M(X)的階數低。CRC校驗碼的檢錯原理是：發送方先為數據塊生成CRC校驗碼，使這個CRC校驗碼的多項式能被G(X)除盡，實際發送此CRC校驗碼；接收方用收到的CRC校驗碼除以G(X)，如果能除盡，表明傳輸正確，否則，表示有傳輸錯誤，請求重發。
　　生成數據塊的CRC校驗碼的方法是：
　　(1) 設G(X)為r階，在數據塊末尾添加r個0，使數據塊為m+r位，則相應的多項式為XrM(X)；
　　(2) 以2為模，用對應于G(X)的位串去除對應于XrM(X)的位串，求得余數位串；
　　(3) 以2為模，從對應于XrM(X)的位串中減去余數位串，結果就是為數據塊生成的帶足夠校驗信息的CRC校驗碼位串。
　　例如，設要發送的數據為1101011011，G(X)=X4+X+1，則首先在發送數據塊的末尾加4個0，得到11010110110000，然后用G(X)的位串10011去除，再用11010110110000減去余數位串1110，得到的即為CRC位串11010110111110，將對應多項式稱為T(X)，顯然，T(X)能被G(X)除盡。這樣，一旦接收到的CRC位串不能被同樣的G(X)的位串除盡，那么一定有傳輸錯誤。
　　當使用CRC校驗碼進行差錯控制時，除了為G(X)的整數倍的差錯多項式不能被檢測外，其它差錯均能被查出。CRC校驗碼的差錯控制效果取決于G(X)的階數，階數越高，效果越好。目前，常用的有兩種生成多項式G(X)的方法，分別是：
　　CRC-16　　X16+X15+X2+1
　　CCITT　　X16+X12+X5+1
　　CRC校驗碼實際上是一種線性碼，將任意CRC校驗碼循環移位后仍然是一個CRC校驗碼。由于它有良好的結構，檢錯能力強，易于實現硬件編、譯碼，因此在數據通信系統中得到廣泛的應用。

2　CRC校驗碼生成和校驗程序

　　對于某些不宜用硬件實現CRC校驗而又需要用CRC校驗碼進行差錯控制的系統中，須用軟件方法實現CRC校驗，即實現編碼、檢錯和譯碼功能。
　　從CRC校驗碼編碼規則可以看出，CRC校驗碼實際上是由原始數據位串和緊跟其后的與G(X)位串等長的冗余位串組成，只要求出此冗余位串，發送方即可將原始數據和冗余位串裝配成一CRC位串序列后再發送。CRC校驗碼譯碼非常簡單，只需從接收到正確CRC校驗碼尾部截掉與G(X)位串等長冗余位串，余下的部分即為原始數據位串。CRC校驗碼錯誤檢測按模2除法運算，用接收到的CRC位串除以G(X)位串，看是否能夠除盡即可確定。
　　下面的C語言模塊實現了CRC校驗碼編碼和檢錯功能，程序中的G(X)使用CRC-16，相應的位串為1100000000000101，用十六進制表示為0xc005。函數CrcGen以待發送的原始數據緩沖區地址和緩沖區長度(字節數)為入口參數，產生并返回遵循CRC校驗碼編碼規則的且與G(X)位串等長的2字節冗余位串。函數CrcErr以接收到的CRC校驗碼緩沖區地址和緩沖區長度(字節數)為入口參數，返回CRC校驗結果，若有錯，返回1(真)，否則，返回0(假)。函數代碼如下：
　　unsigned short crcgen(unsigned char* databuf,short len)
　　｛
　　　　　register unsigned short crc=0,ch,i;
　　　　　unsigned short gx=0xc005；
　　　　　while(--len＞=0)
　　　　　｛
　　　　　　ch=*databuf++;ch＜＜=8;
　　　　　　for(i=0;i＜8,i++)
　　　　　　｛
　　　　　　　crc＜＜=1;
　　　　　　　if((ch&0x8000)!=0)crc｜=1;
　　　　　　　if(crc＞=gx)crc∧=gx;
　　　　　　　ch＜＜=1;
　　　　　　｝
　　　　｝
　　　　for(i=0;i＜16;i++)
　　　　｛
　　　　　　crc＜＜=1;
　　　　　　if(crc＞=gx)crc∧=gx;
　　　　　｝
　　　　return(crc);
　　　　｝
　　　　int crcerr (unsigned char*crcbuf,short len)
　　　　｛
　　　　　register short short crc=0,ch,i;
　　　　　unsigned short gx=0xc005;
　　　　　while(--len＞=0)
　　　　　｛
　　　　　　ch=*crcbuf++;ch＜＜=8;
　　　　　　for(i=0;i＜8;i++)
　　　　　　｛
　　　　　　　crc＜＜=1;
　　　　　　　if((ch&0x8000)!=0)crc｜=1;
　　　　　　　if(crc＞=gx)crc∧=gx;
　　　　　　　ch＜＜=1;
　　　　　　｝
　　　　　｝
　　　　　return((crc==0)?0∶1)
　　　　｝
　　以上CRC編碼和校驗函數結構良好，調用接口清晰，執行效率很高，且具有良好的可移植性。需使用CRC校驗碼機制的通信軟件，均可調用這兩個函數高效地實現CRC校驗碼軟件編碼和校驗功能。