📄 subject_27115.htm
字号:
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：bb 回复日期：2003-01-09 10:16:16
<br>内容：<BR>循环冗余校验 CRC的算法分析和程序实现<BR>西南交通大学计算机与通信工程学院 刘东 <BR>摘要 通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其算法实现。<BR><BR>关键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4 <BR><BR>概述<BR>在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。<BR>循环冗余校验CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。<BR><BR>一、循环冗余校验码（CRC）<BR>CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式，由 。如一个8位二进制数10110101可以表示为： 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。<BR>采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。<BR>CRC校验可以100％地检测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048 kbit/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式g（x）= 。采用16位CRC校验，可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16，其生成多项式g（x）= ；而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式g（x）= 。CRC-32的生成多项式g（x）= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。<BR>二、CRC校验码的算法分析<BR>CRC校验码的编码方法是用待发送的二进制数据t（x）除以生成多项式g（x），将最后的余数作为CRC校验码。其实现步骤如下：<BR>（1） 设待发送的数据块是m位的二进制多项式t（x），生成多项式为r阶的g（x）。在数据块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为 。<BR>（2） 用生成多项式g（x）去除 ，求得余数为阶数为r-1的二进制多项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC校验码。<BR>（3） 用 以模2的方式减去y（x），得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。<BR>从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式 ，所以解码时可以用接受到的数据去除g（x），如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t（x）和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。<BR>为了更清楚的了解CRC校验码的编码过程，下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。<BR>设待发送的数据t（x）为12位的二进制数据100100011100；CRC-4的生成多项式为g（x）= ，阶数r为4，即10011。首先在t（x）的末尾添加4个0构成 ，数据块就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余数y（x）。下表为给出了除法过程。<BR>除数次数 被除数/ g（x）/结果 余数<BR>0 1 001000111000000 100111000000<BR> 1 0011 <BR> 0 000100111000000 <BR>1 1 00111000000 1000000<BR> 1 0011 <BR> 0 00001000000 <BR>2 1 000000 1100<BR> 1 0011 <BR> 0 001100 <BR><BR>从上面表中可以看出，CRC编码实际上是一个循环移位的模2运算。对CRC-4，我们假设有一个5 bits的寄存器，通过反复的移位和进行CRC的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：<BR>//reg是一个5 bits的寄存器<BR>把reg中的值置0. <BR>把原始的数据后添加r个0. <BR>While (数据未处理完) <BR>Begin <BR>If (reg首位是1) <BR>reg = reg XOR 0011. <BR>把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。 <BR>End<BR>reg的后四位就是我们所要求的余数。<BR>这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一位数据，效率太低。为了提高处理效率，可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理，所以一次处理8位比较合适。<BR>为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。在上面例子中，可以将编码过程看作如下过程：<BR> 由于最后只需要余数，所以我们只看后四位。构造一个四位的寄存器reg，初值为0，数据依次移入reg0（reg的0位），同时reg3的数据移出reg。有上面的算法可以知道，只有当移出的数据为1时，reg才和g（x）进行XOR运算；移出的数据为0时，reg不与g（x）进行XOR运算，相当与和0000进行XOR运算。就是说，reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit，所以有 种选择。上述算法可以描述如下，<BR>//reg是一个4 bits的寄存器<BR>初始化t[]={0011,0000}<BR>把reg中的值置0. <BR>把原始的数据后添加r个0. <BR>While (数据未处理完) <BR>Begin <BR>把reg中的值左移一位，读入一个新的数据并置于register的0 bit的位置。<BR>reg = reg XOR t[移出的位]<BR>End<BR>上面算法是以bit为单位进行处理的，可以将上述算法扩展到8位，即以Byte为单位进行处理，即CRC-32。构造一个四个Byte的寄存器reg，初值为0x00000000，数据依次移入reg0（reg的0字节，以下类似），同时reg3的数据移出reg。用上面的算法类推可知，移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit，所以有 种选择。上述算法可以描述如下：<BR>//reg是一个4 Byte的寄存器<BR>初始化t[]＝{…}//共有 ＝256项<BR>把reg中的值置0. <BR>把原始的数据后添加r/8个0字节. <BR>While (数据未处理完) <BR>Begin <BR>把reg中的值左移一个字节，读入一个新的字节并置于reg的第0个byte的位置。<BR>reg = reg XOR t[移出的字节]<BR>End<BR>算法的依据和多项式除法性质有关。如果一个m位的多项式t（x）除以一个r阶的生成多项式g（x）， ，将每一位 （0=<k<m）提出来，在后面不足r个0后，单独去除g（x），得到的余式位 。则将 后得到的就是t（x）由生成多项式g（x）得到的余式。对于CRC-32，可以将每个字节在后面补上32个0后与生成多项式进行运算，得到余式和此字节唯一对应，这个余式就是上面算法种t[]中的值，由于一个字节有8位，所以t[]共有 ＝256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节，通过查表法进行运算，大大提高了处理速度，故为大多数应用所采用。<BR>三、CRC-32的程序实现。<BR>为了提高编码效率，在实际运用中大多采用查表法来完成CRC-32校验，下面是产生CRC-32校验吗的子程序。<BR>unsigned long crc_32_tab[256]={<BR>0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d<BR>};//事先计算出的参数表，共有256项，未全部列出。<BR><BR>unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)<BR>{<BR> unsigned long oldcrc32;<BR> unsigned long crc32;<BR> unsigned long oldcrc;<BR> unsigned int charcnt;<BR> char c,t;<BR> oldcrc32 = 0x00000000; //初值为0<BR> charcnt=0;<BR> while (len--) {<BR> t= (oldcrc32 >> 24) & 0xFF; //要移出的字节的值<BR> oldcrc=crc_32_tab[t]; //根据移出的字节的值查表<BR> c=DataBuf[charcnt]; //新移进来的字节值<BR> oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中<BR> oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor运算<BR> charcnt++;<BR> }<BR> crc32=oldcrc32;<BR> return crc32;<BR>}<BR>参数表可以先在PC机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c语言子程序，在Visual C++ 6.0下编译通过。<BR>#include <stdio.h><BR>unsigned long int crc32_table[256];<BR>unsigned long int ulPolynomial = 0x04c11db7;<BR>unsigned long int Reflect(unsigned long int ref, char ch)<BR>{ unsigned long int value(0);<BR> // 交换bit0和bit7，bit1和bit6，类推<BR> for(int i = 1; i < (ch + 1); i++)<BR> { if(ref & 1)<BR> value |= 1 << (ch - i);<BR> ref >>= 1; }<BR> return value;<BR>}<BR>init_crc32_table()<BR>{ unsigned long int crc,temp;<BR> // 256个值<BR> for(int i = 0; i <= 0xFF; i++)<BR> { temp=Reflect(i, 8);<BR> crc32_table[i]= temp<< 24;<BR> for (int j = 0; j < 8; j++){<BR> unsigned long int t1,t2;<BR> unsigned long int flag=crc32_table[i]&0x80000000;<BR> t1=(crc32_table[i] << 1);<BR> if(flag==0)<BR> t2=0;<BR> else<BR> t2=ulPolynomial;<BR> crc32_table[i] =t1^t2 ; }<BR> crc=crc32_table[i];<BR> crc32_table[i] = Reflect(crc32_table[i], 32);<BR> }<BR>}<BR>结束语<BR> CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段。<BR>参考文献<BR>[1] 王新梅 肖国镇. 纠错码－原理与方法.西安：西安电子科技大学出版社，2001<BR>[2] 罗伟雄 韩力 原东昌 丁志杰 通信原理与电路. 北京：北京理工大学出版社，1999<BR>[3] 王仲文 ARQ编码通信.北京：机械工业出版社，1991<BR>[4] Ross Williams, A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS. Document url: http://www.repairfaq.org/filipg/ ,1993<BR><BR><BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：ufx@tzzxoi 回复日期：2003-06-20 13:35:41
<br>内容：我在uva上作过一个关于crc的题目<BR>贴出来<BR><BR><BR> Software CRC <BR><BR>You work for a company which uses lots of personal computers. Your boss, Dr Penny Pincher, has wanted to link the computers together for some time but has been unwilling to spend any money on the Ethernet boards you have recommended. You, unwittingly, have pointed out that each of the PCs has come from the vendor with an asynchronous serial port at no extra cost. Dr Pincher, of course, recognizes her opportunity and assigns you the task of writing the software necessary to allow communication between PCs. <BR><BR><BR>You've read a bit about communications and know that every transmission is subject to error and that the typical solution to this problem is to append some error checking information to the end of each message. This information allows the receiving program to detect when a transmission error has occurred (in most cases). So, off you go to the library, borrow the biggest book on communications you can find and spend your weekend (unpaid overtime) reading about error checking. <BR><BR><BR>Finally you decide that CRC (cyclic redundancy check) is the best error checking for your situation and write a note to Dr Pincher detailing the proposed error checking mechanism noted below. <BR><BR><BR>CRC Generation <BR>The message to be transmitted is viewed as a long positive binary number. The first byte of the message is treated as the most significant byte of the binary number. The second byte is the next most significant, etc. This binary number will be called ``m'' (for message). Instead of transmitting ``m'' you will transmit a message, ``m2'', consisting of ``m'' followed by a two-byte CRC value. <BR><BR>The CRC value is chosen so that ``m2'' when divided by a certain 16-bit value ``g'' leaves a remainder of 0. This makes it easy for the receiving program to determine whether the message has been corrupted by transmission errors. It simply divides any message received by ``g''. If the remainder of the division is zero, it is assumed that no error has occurred. <BR><BR>You notice that most of the suggested values of ``g'' in the book are odd, but don't see any other similarities, so you select the value 34943 for ``g'' (the generator value). <BR><BR>Input and Output<BR>You are to devise an algorithm for calculating the CRC value corresponding to any message that might be sent. To test this algorithm you will write a program which reads lines (each line being all characters up to, but not including the end of line character) as input, and for each line calculates the CRC value for the message contained in the line, and writes the numeric value of the CRC bytes (in hexadecimal notation) on an output line. Each input line will contain no more than 1024 ASCII characters. The input is terminated by a line that contains a # in column 1. Note that each CRC printed should be in the range 0 to 34942 (decimal). <BR><BR><BR>Sample Input<BR><BR>this is a test<BR><BR>A<BR>#<BR><BR><BR>Sample Output<BR><BR>77 FD <BR>00 00<BR>0C 86<BR><BR>程序：<BR>/* @JUDGE_ID: xxxxxx 128 C++ */<BR><BR>/* Author: Reuber Guerra Duarte(reuber@dcc.ufmg.br) */<BR><BR>#include <stdio.h><BR>#include <string.h><BR><BR>int compute() {<BR> char line[1500];<BR> int len, last = 0, i = 0;<BR> unsigned long value = 0, s1, s2;<BR> char ch;<BR> while (gets(line)) {<BR> if (line[0] == '#') break;<BR> len = strlen(line);<BR> value = 0;<BR> for (i = 0; i < len; i++) {<BR> value = value << 8; <BR> value += line[i];<BR> value = value % 34943L;<BR> }<BR> value = value << 16; <BR> value = value % 34943L;<BR> if (value) value = 34943L - value;<BR> s1 = value >> 8;<BR> s2 = value - (s1 << 8);<BR> printf("%.2lX %.2lX\n", s1, s2);<BR> }<BR> return 0;<BR>}<BR><BR>int main() {<BR> while (compute());<BR> return 0;<BR>}<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：LiXueHui 回复日期：2003-07-22 04:14:25
<br>内容：下面是我已经使用了很多次的包装好的一个函数。<BR><BR>static const unsigned short CRC16_Table[ 256 ] =<BR>{<BR> 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,<BR> 0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,<BR> 0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,<BR> 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,<BR> 0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,<BR> 0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,<BR> 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,<BR> 0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,<BR> 0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,<BR> 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,<BR> 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,<BR> 0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,<BR> 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,<BR> 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,<BR> 0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,<BR> 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,<BR> 0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,<BR> 0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,<BR> 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,<BR> 0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,<BR> 0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,<BR> 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,<BR> 0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,<BR> 0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,<BR> 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,<BR> 0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,<BR> 0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,<BR> 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,<BR> 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,<BR> 0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,<BR> 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,<BR> 0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0<BR>};<BR><BR><BR>unsigned short Crc16CalcBlock(unsigned char *Buffer,unsigned short Count,unsigned short CRC)<BR>{<BR> unsigned char *BuffPtr=Buffer;<BR><BR> // Calculate the 16 bit CRC using the table lookup method.<BR> while(Count)<BR> {<BR> CRC=(CRC<<8)^CRC16_Table[(unsigned char)((CRC>>8)^*BUffPtr++)];<BR> Count--;<BR> }<BR> return( CRC & 0xffff );<BR>}<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -