CRC校验码在单片机中的程序实现及其冗余码表的求取

liyf

  
         
    摘　要：　该文介绍了一种数据传输中的差错检测技术—CRC校验原理，以及CRC校验码的构造过程。给出了CRC码在80C51系列单片机中的实现程序，及其冗余码表的求取程序。
　　关键词：　CRC；80C51；校验
　　由单片机嵌入式系统与微机组成的工业检测和数据采集系统中，计算机与单片机之间经常需要进行数据通信。在数字通信过程中，干扰有可能使接收到的二进制数和发送的不一致，造成“0”和“1”互变的差错。一个实用的通信系统必需能发现这种差错，并加以纠正或给出重新发送信息。CRC（CyclicRedundancy Code循环冗余码），也称多项式编码。是一种检错效率高、原理简单、易于实现的通信编码，是目前在数字通信领域应用最为广泛的一种检验方式。如16位的 CRC—CCITT标准可以检测出所有的单位错、双位错、奇位数错及小于等于16位的突发错，大于17位的突发错检错率为99．9984％［1］。可见， CRC码的检错率要大大高于一般的奇偶校验。因此CRC校验可以应用于重要数据的通信场合，如下位机运行状态的检测、运行模式或参数的在线重设置等。
　　对于8位的单片机系统，要实现CRC通信就必须编写生成CRC码的指令程序，且由于单片机的程序存储器很少、运算速度也比较低，因此要求程序代 码尽量少，算法必须简单。下面将以CRC—CCITT标准为例来介绍CRC通信码的单片机实现过程。

1　CRC校验码的构成　
　　传送一K位信息的数据：M＝（mk－1，mk－2，…，m1，m0），若将其视为一多项式的系数，它对应的多项式为：

m0。将信息码后面添加r个0，可构成多项式xr·

m0 xr。将其作为被除式，选择一个r次的CRC校验式G（x）来除，得到一个商式Q（x）和余式R（x）。
　　


　　之所以要填r个0，是因为G（x）为r次多项式，余式R（x）最多为r－1次多项式，追加在xr·M（x）的后面，不会影响数据信息的系数。
　　CRC码的计算过程为模2除法取余式的过程。 由于采用模除，没有进位和错位，故加减都相当于异
　


　　求得余式R(x)，使等式左端的代数式恰为CRC校验式G（x）的整数倍。则将其与待发送的数据多项式xr·M（x）相加得到的r＋k次多项式的各个系数（mk－1，mk－2，…，m1，m0，rr－1，rr－2，…，r1，r0）作为编码一起发送，其中高k位是信息位，低r位是附加校验位。在数据接收端，再对接收到的信息码进行校验，如能被同 一个G（x）整除，则表明通信正确；若余数不为0，表示数据传输有误，从而达到检错的目的。



　　例如要传送8位数据91H（10010001），可把它看成是7次多项式M（x）＝x7＋x4＋1的系数，CRC校验码为4次多项式G（x）＝x4＋x2＋1，系数为10101。x4·M（x）为100100010000，模2除法的详细计算过程如图1所示。算得的余式R（x）为1011，将其附加于数据信息后面，发送的数据编码为

其中前8位是信号信息，后4位是计算得来的附加校验信息。接收端用G（x）检验正确后，合弃后4位，得到有用的用户数据信息。从图1的计算过程可以看出，虽然每次运算都有5位参与，但最左面的高位总是为1，且运算结果为0。
　　CRC校验虽然不能100％检测出错误，但它的漏检率相当低。漏检概率和所选取的校验标准相关，国际上已有多种CRC校验式标准。其中8位的CRC码标准有CDT约定，其校验式为G（x）＝x8＋x2＋x＋1；16位的标准有CCITT（国际电报电话咨询委员会推荐）标准G（x）＝x16＋x12＋x5＋1，和IBM公司提出的CRC－16标准G（x）＝x16＋x12＋x2＋1；校验错误效率最高的是具有32位CRC校验码的




2　多字节信息序列CRC码的快速算法　　
　　假设需要传送的一组信息码N为k个字节二进制序列：
　　Nk＝［n1 n2……nk］
　　 其中的ni为信息码中的各个字节。
　　以16位校验码的CRC—CCITT标准来说明生成校验冗余码的快速算法。N（x）在计算冗余码的时候应该在后面补充两个零字节，作为待计算的信息码。为方便起见，还统一用N（x）表示。
　　对应的前k－1个字节构成的序列可以表示为：



其中Qk－1（x）是一个整数商的多项式，Rk－1（x）是个最高幂次不超过15的余项。由上两式关系为：
　


关系，若已知算式Nk－1的余项Rk－1，就可以求得Nk的余项Rk，已知Rk－2，就可求得Rk－1，依次类推。因为校验式G（x）的最高项为16次，x8 Rk－1（x）＋nk（x）的最高幂次不超过23，所以最后可归结为求［n1 n2 n3］3字节序列余项的问题，每次递推都进行3字节的求余运算。按照上述的方法，很容易编制单片机上CRC校验码的实现程序。

3　CRC校验码在51单片机上的实现　
　　以CRC－CCITT标准为例，按前面多字节数据CRC冗余码的构造过程，51系列单片机计算多字节数据的CRC码程序如下。其中，从31H开始存放信息字节数据，算得校验码的高8位存于R3，低8位存于R4。
　








4　CRC码的查表方法　　
　　上面的程序中，每次计算一组3字节的CRC余项需要进行8次循环操作，每次循环包括2字节的数据移动，和3次异或操作。对于时间要求严格的 数据采样场合，速度可能跟不上。这时可以把对1字节通信数据的所有取值（共256个）求得CRC码做成一个余项表，用查表的方法来代替余项的循环求取过程。
　　设一普通3字节码为Tabc＝［a b c］，把它分解为一特殊的后2字节为零的3字节序列Ta00＝［a 00］，和一个2字节序列Tbc＝［b c］，可以由多项式表



　　其中Qa00为整数的商式，Ra00和Tbc都是最高次不超过15的余项，它们的和就是Tabc（x）的余项。每次取信息码的3字节序列Tabc，先查表得出其中Ta00（x）的余项Ra00（x），这是一个2字节的多项式，把它和余下的2字节序列Tbc进行异或操作，得到新的3字节序列的高2字节，然后取信息码的下一字节附于其后构成新的3字节序列

再分解为Ta00和

，循环查表计算。运用这种方法可以很快求出多字节信息码Mk的CRC冗余校验码。
　　建立16位CRC的检验码表共需要2×256个字节。对于80C51系列的单片机来说，程序存储器ROM一般都有4KB以上的空间，容量上可以满足要求。
　　下面给出CRC校验码表的求取程序：
　


　


　


　


　　每种校验规则校验码的最高位都为1，为编程方便，将其最高位去掉，把校验码的位数凑成是一个字节的整数倍。CRC—CCITT的校验式为G（x）＝x16＋x12＋x5＋1，去掉高位后，校验码为0001000000100001（1021H）。取一个用来比较的16位数CRC—BYTE＝8000H，逐次比较信息码的最高位是否为1，是则将1记录在暂存单元CRC—Temp的最低位，如果是0，则低位左移入0，每次暂存单元和信息单元循环左移，相当于把信息字节的数据逐位从左移入暂存单元中。当暂存单元的最高位变为1，说明已移入了16位数据，然后把暂存单元再左移一次，和16位校验码做异或操作，也就相当于进行模2除。因为暂存单元被移出的最高位1和校验码被舍去的最高位1异或，其结果必然为零，也就等于进行了17位异或操作。把所得的余式存放在暂存单元中，接着循环，直到将信息码和补充在尾部的零字节都操作结束，把最后的余式复给CRC—Variable输出，完成对一个余项式的处理。
　　这种方法的好处是很容易实现对8位或者32位的校验式求取余项表进行扩展，只需将CRC—MODEL改为8位或32位的校验式模型，比较字节CRC— BYTE改为80H和800000H，追加末尾0字节LAST—BYTE改为1和4个，然后再把对应于16位数据变量CRC—Variable的 unsigned short型，改为un－signed char或unsigned long就可以了。



5　结束语
　　利用CRC实现程序可以计算出各种标准下的CRC校验冗余码表。在单片机容量允许的情况下，可以利用查表进行CRC校验。在对时间要求不高、对存储容量要求严格的场合，可以直接利用循环计算来求得余项。编程使用8051系列单片机汇编语言，可以实现最少和高效的指令代码。该程序算法也可应用于 M68HC和PIC17等系列单片机上。

参考文献

［1］Joe Campbell著．徐国定，廖卫东译．串行通讯C程序员指南［M］．北京：清华大学出版社．1990．
［2］韩炬．CRC算法实现［J］．煤炭科学技术，2000，（2）：11－15．
         
          [/td]
        [/tr]