《循环冗余校验码(CRC)》由会员分享，可在线阅读，更多相关《循环冗余校验码(CRC)（10页珍藏版）》请在金锄头文库上搜索。
1、CRC32算法学习笔记以及如何用java实现一：说明二：基本概念及相关介绍2.1什么是CRC在远距离数据通信中，为确保高效而无差错地传送数据，必须对数据进行校验即差错控制。循环冗余校验CRC(CyclicRedundancyCheck/Code)是对一个传送数据块进行校验，是一种高效的差错控制方法。CRC校验采用多项式编码方法。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，如同逻辑异或运算。2.2CRC的运算规则CRC加法运算规则：0+0=00+1=11+0=11+1=0(注意：没有进位)CRC减法运算规则：0-0=00-1=11-0=11-1
2、=0CRC乘法运算规则：0*0=00*1=01*0=01*1=1一、循环冗余校验码（CRC）CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式，由。如一个8位二进制数10110101可以表示为：。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。CRC校验可以100地检
3、测出所有奇数个随机错误和长度小于等于k（k为g（x）的阶数）的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048kbit/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-1
4、6低倍。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。二、CRC校验码的算法分析CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下：(1) 设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位，对应的二进制多项式为
5、。(2) 用生成多项式g(x)去除，求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。(3) 用以模2的方式减去y(x)，得到二进制多项式。就是包含了CRC校验码的待发送字符串。从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式，所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由t(x)和CRC校验码的组合，
6、所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。为了更清楚的了解CRC校验码的编码过程，下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。设待发送的数据t(x)为12位的二进制数据100100011100；CRC-4的生成多项式为g(x)=，阶数r为4，即10011。首先在t(x)的末尾添加4个0构成，数据块就成了1001000111000000。然后用g(x)去除，不用管商是多少，只需要求得余数y(x)。下
7、表为给出了除法过程。除数次数被除数/g(x)/结果余数010010001110000001001110000001001100001001110000001100111000000100000010011000001000000210000001100100110001100从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4，我们假设有一个5bits的寄存器，通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：以太网CRC32的生成多项式和查找表生成多项式：CRC-32码:G(x)=X32+X26
8、+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+查找表：CRC-32Table00h0000000077073096EE0E612C990951BA04h076DC419706AF48FE963A5359E6495A308h0EDB883279DCB8A4E0D5E91E97D2D9880Ch09B64C2B7EB17CBDE7B82D0790BF1D9110h1DB710646AB020F2F3B9714884BE41DE14h1ADAD47D6DDDE4EBF4D4B55183D385C718h136C9856646BA8C0FD62F97A8A65C9EC
9、1Ch14015C4F63066CD9FA0F3D638D080DF520h3B6E20C84C69105ED56041E4A267717224h3C03E4D14B04D447D20D85FDA50AB56B28h35B5A8FA42B2986CDBBBC9D6ACBCF9402Ch32D86CE345DF5C75DCD60DCFABD13D5930h26D930AC51DE003AC8D75180BFD0611634h21B4F4B556B3C423CFBA9599B8BDA50F38h2802B89E5F058808C60CD9B2B10BE9243Ch2F6F7C8758684C11C
10、1611DABB6662D3D40h76DC419001DB710698D220BCEFD5102A44h71B1858906B6B51F9FBFE4A5E8B8D43348h7807C9A20F00F9349609A88EE10E98184Ch7F6A0DBB086D3D2D91646C97E6635C0150h6B6B51F41C6C6162856530D8F262004E54h6C0695ED1B01A57B8208F4C1F50FC45758h65B0D9C612B7E9508BBEB8EAFCB9887C5Ch62DD1DDF15DA2D498CD37CF3FBD44C6560h4D
11、B261583AB551CEA3BC0074D4BB30E264h4ADFA5413DD895D7A4D1C46DD3D6F4FB68h4369E96A346ED9FCAD678846DA60B8D06Ch44042D7333031DE5AA0A4C5FDD0D7CC970h5005713C270241AABE0B1010C90C208674h5768B525206F85B3B966D409CE61E49F78h5EDEF90E29D9C998B0D09822C7D7A8B47Ch59B33D172EB40D81B7BD5C3BC0BA6CAD80hEDB883209ABFB3B603B6E2
12、0C74B1D29A84hEAD547399DD277AF04DB261573DC168388hE3630B1294643B840D6D6A3E7A6A5AA88ChE40ECF0B9309FF9D0A00AE277D079EB190hF00F93448708A3D21E01F2686906C2FE94hF762575D806567CB196C36716E6B06E798hFED41B7689D32BE010DA7A5A67DD4ACC9ChF9B9DF6F8EBEEFF917B7BE4360B08ED5A0hD6D6A3E8A1D1937E38D8C2C44FDFF252A4hD1BB67F
13、1A6BC57673FB506DD48B2364BA8hD80D2BDAAF0A1B4C36034AF641047A60AChDF60EFC3A867DF55316E8EEF4669BE79B0hCB61B38CBC66831A256FD2A05268E236B4hCC0C7795BB0B4703220216B95505262FB8hC5BA3BBEB2BD0B282BB45A925CB36A04BChC2D7FFA7B5D0CF312CD99E8B5BDEAE1DC0h9B64C2B0EC63F226756AA39C026D930AC4h9C0906A9EB0E363F72076785050
14、05713C8h95BF4A82E2B87A147BB12BAE0CB61B38CCh92D28E9BE5D5BE0D7CDCEFB70BDBDF21D0h86D3D2D4F1D4E24268DDB3F81FDA836ED4h81BE16CDF6B9265B6FB077E118B74777D8h88085AE6FF0F6A7066063BCA11010B5CDCh8F659EFFF862AE69616BFFD3166CCF45E0hA00AE278D70DD2EE4E0483543903B3C2E4hA7672661D06016F74969474D3E6E77DBE8hAED16A4AD9D6
15、5ADC40DF0B6637D83BF0EChA9BCAE53DEBB9EC547B2CF7F30B5FFE9F0hBDBDF21CCABAC28A53B3933024B4A3A6F4hBAD03605CDD7069354DE572923D967BFF8hB3667A2EC4614AB85D681B022A6F2B94FChB40BBE37C30C8EA15A05DF1B2D02EF8D例如：g(x)=x4+x3+x2+1,(7,3)码,信息码110产生的CRC码就是：10111101|110,00001110110100111011001余数是1001，所以CRC码是110,1001标准的CRC码是，CRC-CCITT和CRC-16,它们的生成多项式是:CRC-CCITT=x16+x12+x5+1CRC-16=x16+x15+x2+1
