AVR单片机CRC校验码的查表与直接生成
摘要：循环冗余码校验CRC是常用的重要校验方法之一。AVR高速嵌入式单片机功能强大，在无线数据传输应用方面具有很大优势。本文基于Atmega128高速嵌入式单片机，实现32位CRC校验码的直接生成法和查表生成法；根据实验结果，分析两种方法的特点。
关键词：Atmega128CRC校验码CRC生成表数据段
引言
随着技术的不断进步，各种数据通信的应用越来越广泛。由于传输距离、现场状况、干扰等诸多因素的影响，设备之间的通信数据常会发生一些无法预测的错误。为了降低错误所带来的影响，一般在通信时采用数据校验的办法，而循环冗余码校验是常用的重要校验方法之一。
AVR高速嵌入式单片机是8位RISCMCU，执行大多数指令只需一个时钟周期，速度快（8MHzAVR的运行速度约等于200MHz80C51的运行速度），32个通用寄存器直接与ALU相连，消除了运算瓶颈；内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。
本文采用Atmel公司的Atmega128高速嵌入式单片机，依照IEEE1999年公布的802.11无线局域网协议标准，采用32位循环冗余校验码（CyclicRedundancyCheck）实现无线传输数据时的差错校验。
1CRC循环冗余校验码原理
1.1数据传输的帧格式
根据IEEE制定的802.11无线局域网络协议，在数据传输时都应按照帧传输。这里，我们采用了信息处理系统－数据通信－高级数据链路控制规程－帧结构，它的每个帧由下列字段组成（传输顺序自左至右）：
地址控制信息CRC校验位
地址——数据站地址字段；
控制——控制字段。
信息——信息字段；
CRC校验位——根据前面三个字段生成的CRC校验位。
由地址、控制、信息三个字段组成的总的字段统称为数据段。
1.2CRC校验码的理论生成方法
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建议：2048Kb/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://fanwen.oyaya.net收集整理）。
2.2查表法生成32位CRC校验码
和直接计算法相反，查表法生成32位CRC校验码的优点是运算量小，速度快；缺点是可移植性较差。这种算法首先要求得到32位CRC生成表，由于1个字节有8位，所以这个表总共有256项。但是，由于AVR高速嵌入式单片机中的寄存器是以1个字节为单位的，所以在编程实现中，这个CRC 《AVR单片机CRC校验码的查表与直接生成》
本文链接地址：http://www.oyaya.cn/fanwen/view/175666.html
关键词：Atmega128CRC校验码CRC生成表数据段
引言
随着技术的不断进步，各种数据通信的应用越来越广泛。由于传输距离、现场状况、干扰等诸多因素的影响，设备之间的通信数据常会发生一些无法预测的错误。为了降低错误所带来的影响，一般在通信时采用数据校验的办法，而循环冗余码校验是常用的重要校验方法之一。
AVR高速嵌入式单片机是8位RISCMCU，执行大多数指令只需一个时钟周期，速度快（8MHzAVR的运行速度约等于200MHz80C51的运行速度），32个通用寄存器直接与ALU相连，消除了运算瓶颈；内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。
本文采用Atmel公司的Atmega128高速嵌入式单片机，依照IEEE1999年公布的802.11无线局域网协议标准，采用32位循环冗余校验码（CyclicRedundancyCheck）实现无线传输数据时的差错校验。
1CRC循环冗余校验码原理
1.1数据传输的帧格式
根据IEEE制定的802.11无线局域网络协议，在数据传输时都应按照帧传输。这里，我们采用了信息处理系统－数据通信－高级数据链路控制规程－帧结构，它的每个帧由下列字段组成（传输顺序自左至右）：
地址控制信息CRC校验位
地址——数据站地址字段；
控制——控制字段。
信息——信息字段；
CRC校验位——根据前面三个字段生成的CRC校验位。
由地址、控制、信息三个字段组成的总的字段统称为数据段。
1.2CRC校验码的理论生成方法
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建议：2048Kb/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://fanwen.oyaya.net收集整理）。
2.2查表法生成32位CRC校验码
和直接计算法相反，查表法生成32位CRC校验码的优点是运算量小，速度快；缺点是可移植性较差。这种算法首先要求得到32位CRC生成表，由于1个字节有8位，所以这个表总共有256项。但是，由于AVR高速嵌入式单片机中的寄存器是以1个字节为单位的，所以在编程实现中，这个CRC 《AVR单片机CRC校验码的查表与直接生成》
★读了本文的人也读了：