循环冗余校验.doc

《循环冗余校验.doc》由会员分享，可在线阅读，更多相关《循环冗余校验.doc（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date循环冗余校验CRC 校验 CRC 校验循环冗余校验 CRC 的算法分析和程序实现 摘要 通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其算法实现。关

2、键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4概述在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错（HEC）。在传输过程误码率比较低时，用FEC 方式比较理想。在传输过程误码率较高时，采用FEC 容易出

3、现“乱纠”现象。HEC 方式则式ARQ 和FEC 的结合。在许多数字通信中，广泛采用ARQ 方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。循环冗余校验 CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了

4、广泛的应用。下面重点介绍了CRC 校验的原理及其算法实现。一、循环冗余校验码（CRC）CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个n 阶的二进制多项式，由1 02211 a x a x x a x annn + + + + 。如一个8 位二进制数10110101 可以表示为：1x7 + 0x6 +1x5 +1x4 + 0x3 +1x2 + 0x +1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2 为模，加减时不进，错位，和逻辑异或运算一致。采用 CRC 校验时，发送方和接收方用同一个生成多项式g（x）_,并且g（x）的首位和最后一位的系数必须为1。C

5、RC 的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC 校验码。校验时，以计算的校正结果是否为0 为据，判断数据帧是否出错。CRC 校验可以100地检测出所有奇数个随机错误和长度小于等于k（k 为g（x）的阶数）的突发错误。所以CRC 的生成多项式的阶数越高，那么误判的概率就越小。CCITT 建议：2048 kbit/s的PCM 基群设备采用CRC-4 方案，使用的CRC 校验码生成多项式g（x）= x4 + x +1。采用16位CRC 校验，可以保证在1014 bit 码元中只含有一位未被检测出的错误2。在IBM 的同步数据链路控制规程SDLC 的帧校验序列FCS中，使用CRC

6、-16，其生成多项式g（x）= x16 + x15 + x2 +1；而在CCITT 推荐的高级数据链路控制规程HDLC 的帧校验序列FCS 中，使用CCITT-16，其生成多项式g （ x ） = x16 + x15 + x5 +1 。CRC-32 的生成多项式g （ x ）= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x +1。CRC-32出错的概率比CRC-16低105 倍4。由于CRC-32 的可靠性，把CRC-32 用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一

7、些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位，对应的二进制多项式为xr t(x)。（2） 用生成多项式g（x）去除xr t(x)，求得余数为阶数为r-1 的二进制多

8、项式y（x）。此二进制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC 校验码。（3） 用xr t(x)以模2 的方式减去y（x），得到二进制多项式xr t(x)。xr t(x)就是包含了CRC校验码的待发送字符串。从 CRC 的编码规则可以看出，CRC 编码实际上是将代发送的m 位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式xr t(x)，所以解码时可以用接受到的数据去除g（x），如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC 的硬件解码电路就是按这种方式进行检错的。同时xr t(x)可以看做是由t（x）和CR

9、C校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r 位数据，得到的就是原始数据。为了更清楚的了解 CRC 校验码的编码过程，下面用一个简单的例子来说明CRC 校验码的编码过程。由于CRC-32、CRC-16、CCITT 和CRC-4 的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4 编码的例子来说明CRC 的编码过程。设待发送的数据 t（x）为12 位的二进制数据100100011100；CRC-4 的生成多项式为g（x）= x4 + x +1，阶数r为4，即10011。首先在t（x）的末尾添加4 个0 构成x4t(x)，数据块就成了10010001110

10、00000。然后用g（x）去除x4t(x)，不用管商是多少，只需要求得余数y（x）。下表为给出了除法过程。从上面表中可以看出，CRC 编码实际上是一个循环移位的模2 运算。对CRC-4，我们假设有除数次数被除数/ g（x）/结果余数1 0010001110000001 001100 0001001110000001001110000001 001110000001 001110 0000100000010000001 0000001 001120 0011001100一个5 bits 的寄存器，通过反复的移位和进行CRC 的除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以

11、将上述步骤用下面的流程描述：/reg 是一个5 bits 的寄存器把 reg 中的值置0.把原始的数据后添加r 个0.While (数据未处理完)BeginIf (reg 首位是1)reg = reg XOR 0011.把reg 中的值左移一位，读入一个新的数据并置于register 的0 bit 的位置。Endreg 的后四位就是我们所要求的余数。这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一位数据，效率太低。为了提高处理效率，可以一次处理4 位、8 位、16 位、32 位。

12、由于处理器的结构基本上都支持8 位数据的处理，所以一次处理8 位比较合适。为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。在上面例子中，可以将编码过程看作如下过程：由于最后只需要余数，所以我们只看后四位。构造一个四位的寄存器reg，初值为0，数据依次移入reg0（reg 的0 位），同时reg3 的数据移出reg。有上面的算法可以知道，只有当移出的数据为1 时，reg 才和g（x）进行XOR 运算；移出的数据为0 时，reg 不与g（x）进行XOR 运算，相当与和0000 进行XOR 运算。就是说，reg 和什么样的数据进行XOR 移出的数据决定。由于只有一个bit，所以有

13、21种选择。上述算法可以描述如下，/reg 是一个4 bits 的寄存器初始化 t=0011,0000把reg 中的值置0.把原始的数据后添加r 个0.While (数据未处理完)Begin把reg 中的值左移一位，读入一个新的数据并置于register 的0 bit 的位置。reg = reg XOR t移出的位End上面算法是以bit 为单位进行处理的，可以将上述算法扩展到8 位，即以Byte 为单位进行处理，即CRC-32。构造一个四个Byte 的寄存器reg，初值为0x00000000，数据依次移入reg0（reg 的0字节，以下类似），同时reg3 的数据移出reg。用上面的算法类推

14、可知，移出的数据字节决定reg 和什么样的数据进行XOR。由于有8 个bit，所以有28种选择。上述算法可以描述如下：/reg 是一个4 Byte 的寄存器初始化 t/共有28256 项把 reg 中的值置0.把原始的数据后添加r/8 个0 字节.While (数据未处理完)Begin把reg 中的值左移一个字节，读入一个新的字节并置于reg 的第0 个byte 的位置。reg = reg XOR t移出的字节End算法的依据和多项式除法性质有关。如果一个m 位的多项式t（x）除以一个r 阶的生成多项式g（x）， 01122221t(x) a 1x a x a x a x a mmmm = +

15、 + + + + ，将每一位kk a x （0=k 24) & 0xFF; /要移出的字节的值oldcrc=crc_32_tabt; /根据移出的字节的值查表c=DataBufcharcnt; /新移进来的字节值oldcrc32= (oldcrc32 8) | c; /将新移进来的字节值添在寄存器末字节中oldcrc32=oldcrc32oldcrc; /将寄存器与查出的值进行xor 运算charcnt+;crc32=oldcrc32;return crc32;参数表可以先在PC 机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c 语言子程序，在Visual C+ 6.0 下编译通过

16、。#include unsigned long int crc32_table256;unsigned long int ulPolynomial = 0x04c11db7;unsigned long int Reflect(unsigned long int ref, char ch) unsigned long int value(0);/ 交换bit0 和bit7，bit1 和bit6，类推for(int i = 1; i (ch + 1); i+) if(ref & 1)value |= 1 = 1; return value;init_crc32_table() unsigned l

17、ong int crc,temp;/ 256 个值for(int i = 0; i = 0xFF; i+) temp=Reflect(i, 8);crc32_tablei= temp 24;for (int j = 0; j 8; j+)unsigned long int t1,t2;unsigned long int flag=crc32_tablei&0x80000000;t1=(crc32_tablei 1);if(flag=0)t2=0;elset2=ulPolynomial;crc32_tablei =t1t2 ; crc=crc32_tablei;crc32_tablei = Reflect(crc32_tablei, 32);结束语CRC 校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段。-