CRC32冗余校验码的计算

...wd......wd......wd...题目：校验码的计算姓名:周小多学号：2013302513班号：10011302时间：2015.11.1计算机学院时间:目录摘要1目的12要求13相关知识14实现原理及流程图35程序代码66运行结果与分析147参考文献14题目：校验码的计算目的计算CRC冗余校验码〔32〕2、要求相关知识百度百科：RC即循环冗余校验码〔CyclicRedundancyCheck[1]

〕：是数据通信领域中最常用的一种过失校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查〔CRC〕是一种数据传输检错功能，对数据进展多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。循环冗余校验码〔CRC〕的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫〔N，K〕码。对于一个给定的〔N，K〕码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位〔可表示成C(x)*2R〕，这样C(x)的右边就会空出R位，这就是校验码的位置。用C(x)*2R

除以生成多项式G(x)得到的余数就是校验码。任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。4、实现原理及流程图CRC校验码的编码方法是用待发送的二进制数据t〔x〕除以生成多项式g〔x〕，将最后的余数作为CRC校验码。其实现步骤如下：〔1〕设待发送的数据块是m位的二进制多项式t〔x〕，生成多项式为r阶的g〔x〕。在数据块的末尾添加r个0，数据块的长度增加到m+r位。〔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校验码的组合，所以解码时将接收到的二进制数据去掉尾部的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〕。下表为给出了除法过程。除数次数被除数/g〔x〕/结果

余数0

1001000111000000100111000000

10011

00001001110000001

100111000000

1000000

10011

0000010000002

10000001100

10011

0001100从上面表中可以看出，CRC编码实际上是一个循环移位的模2运算。对CRC-4，我们假设有一个5bits的存放器，通过反复的移位和进展CRC的除法，那么最终该存放器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：//reg是一个5bits的存放器把reg中的值置0.把原始的数据后添加r个0.While(数据未处理完)BeginIf(reg首位是1)reg=regXOR0011.把reg中的值左移一位，读入一个新的数据并置于register的0bit的位置。Endreg的后四位就是我们所要求的余数。这种算法简单，容易实现，对任意长度生成多项式的G〔x〕都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一位数据，效率太低。为了提高处理效率，可以一次处理4位、8位、16位、32位。由于处理器的构造基本上都支持8位数据的处理，所以一次处理8位比较适宜。为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。在上面例子中，可以将编码过程看作如下过程：由于最后只需要余数，所以我们只看后四位。构造一个四位的存放器reg，初值为0，数据依次移入reg0〔reg的0位〕，同时reg3的数据移出reg。有上面的算法可以知道，只有当移出的数据为1时，reg才和g〔x〕进展XOR运算；移出的数据为0时，reg不与g〔x〕进展XOR运算，相当与和0000进展XOR运算。就是说，reg和什么样的数据进展XOR移出的数据决定。由于只有一个bit，所以有种选择。上述算法可以描述如下，//reg是一个4bits的存放器初始化t[]={0011,0000}把reg中的值置0.把原始的数据后添加r个0.While(数据未处理完)Begin把reg中的值左移一位，读入一个新的数据并置于register的0bit的位置。reg=regXORt[移出的位]End上面算法是以bit为单位进展处理的，可以将上述算法扩展到8位，即以Byte为单位进展处理，即CRC-32。构造一个四个Byte的存放器reg，初值为0x00000000，数据依次移入reg0〔reg的0字节，以下类似〕，同时reg3的数据移出reg。用上面的算法类推可知，移出的数据字节决定reg和什么样的数据进展XOR。由于有8个bit，所以有种选择。上述算法可以描述如下：//reg是一个4Byte的存放器初始化t[]＝{…}//共有＝256项把reg中的值置0.把原始的数据后添加r/8个0字节.While(数据未处理完)Begin把reg中的值左移一个字节，读入一个新的字节并置于reg的第