CRC工作原理及算法研究

《CRC工作原理及算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、CRC工作原理及算法研究在数字通信系统屮可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)o在传输过程误码率比较低时，用FEC方式比较理想。在传输过

2、程误码率较高时，采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中，广泛采用ARQ方式,此吋的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。循环冗余校验CRC(CyclicRedundancyCh

3、eck)是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。一、循环兀余校验码(CRC)CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式，由。如一个8位二进制数10110101可以表示为：。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算-•致。采用CRC校验吋，发送方和接收方用同一个生成多项式g(x)，并且g(X)的首位

4、和最后一位的系数必须为1。CRC的处理方法是：发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。CRC校验可以100%地检测岀所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048kbit/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式g(x)二o采用16位CRC校验，可以保证在bit码元中只含有一位未被检测出的错误。在IBM的同步数据链路

5、控制规程SDLC的帧校验序列FCS屮，使用CRC-16,其生成多项式g(x)二；而在CC1TT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式g(x)二oCRC-32的生成多项式g(x)二oCRC-32出错的概率比CRC-16低倍。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SI0)内,都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解

6、码芯片屮，也采用CRC-32进行差错控制。二、CRC校验码的算法分析CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下：设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(X)o在数据块的末尾添加r个0,数据块的长度增加到m+r位，对应的二进制多项式为。用生成多项式g(X)去除，求得余数为阶数为T-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。用以模2的方式减去y(x)，得到

7、二进制多项式。就是包含TCRC校验码的待发送字符串。从CRC的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式，所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由t(x)和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。为了更清楚的了解CRC校验码的编码过程，下面用一

8、个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。设待发送的数据t(x)为12位的二进制数据100100011100；CRC-4的生成多项式为g(x)二，阶数r为4,即10011c首先在t(x)的末尾添