CRC的算法分析和程序实现通信的目的是把信息及时可靠地传送给对方.doc

CRC的算法分析和程序实现 通信的目的是把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，但在数字通信系统中可靠与快速往往是一对矛盾。 若要求快速，则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误地可能性增加，传送信息地可靠性下降。若是要求可靠，则使得传送消息地速率变慢。因此，如何合理地解决可靠性也速度这一对矛盾，是正确设计一个通信系统地关键问题。 为保证传输过程的正确性，需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ) 、 向前纠错方式 (FEC) 和混合纠错 (HEC)。 在传输过程误码率比较低时，用FEC方式比较理想。在传输过程误码率较高时，采用 FEC 容易出现“乱纠”现象。 在许多数字通信中，广泛采用 ARQ 方式，此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多，传统的有：奇偶校验、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法误判的概率都比较高。 循环冗余校验 CRC(Cyclic Redundancy Check)编码简单且误判概率很低，在通信系统中得到了广泛的应用.下面重点介绍了 CRC校验的原理及其算法实现。 CRC 校验采用多项式编码方法。被处理的数据块可以看作是一个 n 阶的二进制多项式: 。可以表示为：， 多项式的加减法运算以 2 为模，加减时不进、错位，和逻辑异或运算一致。 CRC 校验可以 100％地检测出所有奇数个随机错误和长度小于等于 k(k为 g(x)的阶数)的突发错误。所以 CRC 的生成多项式的阶数越高，那么误判的概率就越小。CCITT建议：2048 kbit/s的 PCM 基群设备采用 CRC-4 方案，使用的 CRC 校验码生成多项式；采用 16位 CRC 校验，可以保证在 1014 bit 码元中只含有一位未被检测出的错误。在 IBM 的同步数据链路控制协议 SDLC 的帧校验序列 FCS 中，使用 CRC-16，其生成多项式 而在 CCITT推荐的高级数据链路控制规程 HDLC 的帧校验序列 FCS中，使用 CCITT-16，其生成多项式。CRC-32 的生成多项式g (x)。 由于 CRC-32 的可靠性，把 CRC-32 用于重要数据传输十分合适，所以在通信、 计算机等领域运用十分广泛。 在一些UART通信控制芯片 (如MC6582、 Intel8273和Z80-SIO)内，都采用了 CRC 校验码进行差错控制；以太网卡芯片、MPEG 解码芯片中，也采用 CRC-32 进行差错控制。 CRC 校验码的编码方法是用待发送的二进制数据 t(x)除以生成多项式 g(x) ，将最后的余数作为 CRC 校验码。其实现步骤如下： (1) 设待发送的数据块是 m 位的二进制多项式 t(x) ，生成多项式为 r 阶的 g(x) 。在数据块的末尾添加 r个 0，数据块的长度增加到 m+r位，对应的二进制多项式为 xrt(x)。 (2) 用生成多项式 g(x)去除 xrt(x)，求得余数为阶数为 r-1 的二进制多项式 y(x) ,此即 t(x)经过生成多项式 g(x)编码的 CRC 校验码。 (3) 用 xrt(x)以模 2 的方式减去 y(x) ，得到二进制多项式 xrt’(x),就是包含了 CRC校验码的待发送字符串。 从 CRC 的编码规则可以看出，CRC编码实际上是将代发送的 m位二进制多项式 t(x)转换成了可以被 g(x)除尽的 m+r位二进制多项式 xrt’(x)，所以解码时可以用接受到的数据去除 g(x) ，如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC 的硬件解码电路就是按这种方式进行检错的。同时 xrt’(x)可以看做是由 t(x)和 CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的 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