AVR单片机CRC校验码的查表与直接生成

liyf

AVR单片机CRC校验码的查表与直接生成


摘要：循环冗余码校验CRC是常用的重要校验方法之一。AVR高速嵌入式单片机功能强大，在无线数据传输应用方面具有很大优势。本文基于Atmega128高速嵌入式单片机，实现32位CRC校验码的直接生成法和查表生成法；根据实验结果，分析两种方法的特点。    关键词：Atmega128 CRC校验码 CRC生成表 数据段
引 言
　　随着技术的不断进步，各种数据通信的应用越来越广泛。由于传输距离、现场状况、干扰等诸多因素的影响，设备之间的通信数据常会发生一些无法预测的错误。为了降低错误所带来的影响，一般在通信时采用数据校验的办法，而循环冗余码校验是常用的重要校验方法之一。
　　AVR高速嵌入式单片机是8位RISC MCU，执行大多数指令只需一个时钟周期，速度快（8MHz AVR的运行速度约等于200MHz 80C51的运行速度），32个通用寄存器直接与ALU相连，消除了运算瓶颈；内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。
　　本文采用Atmel公司的Atmega128高速嵌入式单片机，依照IEEE 1999年公布的802.11无线局域网协议标准，采用32位循环冗余校验码（Cyclic Redundancy Check）实现无线传输数据时的差错校验。
1 CRC循环冗余校验码原理
    1.1 数据传输的帧格式
　　根据IEEE制定的802.11无线局域网络协议，在数据传输时都应按照帧传输。这里，我们采用了信息处理系统－数据通信－高级数据链路控制规程－帧结构，它的每个帧由下列字段组成（传输顺序自左至右）：

地 址

控  制

信  息

CRC校验位

地址——数据站地址字段；
控制——控制字段。
信息——信息字段；
CRC校验位——根据前面三个字段生成的CRC校验位。
由地址、控制、信息三个字段组成的总的字段统称为数据段。

    1.2 CRC校验码的理论生成方法
　　CRC校验采用多项式编码方法，被处理的数据块可以看作是一个n阶的二进制多项式。这里，假定待发送的二进制数据段为g(x)，生成多项式为 m(x)，得到的CRC校验码为c(x)。
　　CRC校验码的编码方法是用待发送的二进制数据g(x)除以生成多项式m(x)，将最后的余数作为CRC校验码，实现步骤如下。
　　 ① 设待发送的数据块是m位的二进制多项式 g(x)，生成多项式为r阶的m(x)。在数据块的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为G(x) 。
　　② 用生成多项式m(x)去除G(x) ，求得余数为阶数是r-1的二进制多项式c(x)。此二进制多项式 c(x)就是g(x)经过生成多项式m(x)编码的CRC校验码。
　　③ 用模2的方式减去c(x)，得到的二进制多项式就是包含了CRC校验码的待发送字符串。
CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于r（r为m(x)的阶数）的突发错误。所以，CRC的生成多项式的阶数越高，误判的概率就越小。CCITT建议：2048 Kb/s的PCM基群设备采用CRC-4方案，使用的CRC校验码生成多项式m(x)=x4+x+1 。采用16位CRC校验，可以保证在 1014bit码元中只含有1位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中，使用CRC-16，其生成多项式m(x)=x16+x15+x2+1；而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16，其生成多项式m(x)= x16+x15+x5+1。CRC-32的生成多项式m(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。CRC-32出错的概率为CRC-16的10-5。由于CRC-32的可靠性，把CRC-32用于重要数据传输十分合适，所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校验码进行差错控制；以太网卡芯片、MPEG解码芯片中，也采用CRC-32进行差错控制。
　　m(x) 生成多项式的系数为0或1，但是m(x) 的首项系数为1，末项系数也必须为1。m(x) 的次数越高，其检错能力越强。
2 使用Atmega128生成32位CRC校验码
    2.1 直接计算法生成32位CRC校验码
　　直接计算法就是依据CRC校验码的产生原理来设计程序。其优点是模块代码少，修改灵活，可移植性好。这种算法简单，容易实现，对任意长度生成多项式m(x) 都适用。在发送的数据不长的情况下可以使用，但是如果发送的数据块很长，这种方法就不太适合了。因为它1次只能处理1位数据，效率太低，运算量大。
　　计算法生成32位CRC校验码的流程如图1所示。
　　用AVR单片机汇编语言实现CRC-32源程序见本刊网络补充版（http://www.dpj.com.cn）。
    2.2 查表法生成32位CRC校验码
　　和直接计算法相反，查表法生成32位CRC校验码的优点是运算量小，速度快；缺点是可移植性较差。这种算法首先要求得到32位CRC生成表，由于1个字节有8位，所以这个表总共有256项。但是，由于AVR高速嵌入式单片机中的寄存器是以1个字节为单位的，所以在编程实现中，这个CRC生成表总共有1024项，分别从0~1023；每4位对应1个32位CRC生成表的项，每一项都从高到低降幂排列。关于32位CRC生成表的程序详见本刊网络补充版（http://www.dpj.com.cn）。
　　查表法生成32位CRC校验码的流程如图2所示。
　　图2所示的流程图中，在通过异或运算得到CRC生成表的索引时，由于AVR高速嵌入式单片机中的寄存器是以1个字节为单元的，所以在编程实现中应根据所要求生成的CRC校验码的位数乘以相应的系数。例如：在数据传输时要求32位CRC校验码，应该把所得到的索引数乘以系数4，然后再从高到低依次取得32位CRC生成表单元中的内容。
　　使用查表法得到32位CRC校验码的源程序详见本刊网络补充版（http://www.dpj.com.cn）。
3 实验结果
　　为了比较所述两种32位CRC校验码生成方法的特点，分别选取不同字节数的数据段，对两种方法在不同情况下的效果进行比较，如表1所列。

表1 两种算法实验结果对比

	计算法生成32位CRC校验码		查表法生成32位CRC校验码
数据段字节数	程序耗时/μs	周期数	程序耗时/μs	周期数
3	193.67	2324	29.33	352
4	222.50	2670	34.83	418
10	319.58	3835	48.58	583
20	517.92	6215	76.08	913
40	886.25	10635	131.08	1573
80	1582.92	189995	241.08	2893
150	2957.08	35485	433.58	5203
200	3891.25	46695	571.08	6853
220	4267.92	51215	626.08	7513
239	4645.17	55742	678.33	8140
240	4659.58	55915	681.08	8173
250	4872.92	58475	708.58	8503

　　以上所有实验结果均是在AVR Studio4仿真软件上选用Atmel公司的Atmega128高速嵌入式单片机为实验设备平台，在12MHz运行速度下模拟所得。
　　在调用32位CRC生成表程序以得到32位CRC生成表时，耗时3968.33μs，执行了47620个时钟周期。从上述实验结果可得出以下几点结论。
　　① 如果不考虑生成32位CRC生成表的时间，例如直接把32位CRC生成表烧入到Atmega128的可编程闪速存储器Flash中，由表1可清楚地看出，查表法的运行速度比直接计算法要快得多。因此，在类似情况下，在进行数据传输要求生成32位CRC校验码时，应该选择查表法。
　　② 在某些应用中，如果对硬件存储器空间要求很高，并且在一定程度上对时间没有特别高的要求时，可以采用直接计算法，以避免查表法中CRC生成表对存储器空间的占用。
　　③ 虽然实验结果对32位CRC校验码的两种算法进行了对比，但是所得到的结论也适用于8位、16位、24位CRC校验码。
结 语
　　CRC循环冗余校验码是一种方便、有效、快速的校验方法，被广泛应用在许多实际工程中。文中所列的两种算法——查表法和直接计算法，都可以得到CRC校验码；但是它们各有特点，在工程应用中应该根据实际需要选择最适合的方法，以得到最优的效果。

李小路

谢谢分享！