用C语言实现CRC校验计算_信息技术论文

用c语言实现crc校验计算

<?xml:nmespce prefix = o ns ="urn:schems-microsoft-com:office:office" />clcul

tes crc quickly using the tble-lookup method

作　　者：董云 yun dong

工作单位：黄埔海关技术处工程师

通讯地址：广州市经济技术开发区志诚大道海关大楼

电话号码：020-82130556

邮政编码：510730

电子邮件： dy168@163.net

摘要：

简述crc算法原理，给出一种新颖快速的查表计算方法，并给出用c语言编写的算法源程序。关键词：crc、多项式、查表法　　在编写数据传输程序时，数据容错是一个非常重要的问题。循环冗余位校验（cyclicl redundncy check简称crc）是目前运用非常广泛的一种数据容错方法，在数据传输，数据压缩等领域运用极其广泛。crc的实现分为硬件和软件两种方法，其中软件实现的关键在于计算速度。如果单纯模拟硬件实现方法，则计算速度较慢。笔者在编制一个数据通讯软件中，运用了一种新颖的查表法计算crc，速度很快，效果极佳。

　　首先介绍其原理，如果每次参与crc计算的信息为一个字节，该信息字节加到16位的累加器中去时，只有累加器的高8位或低8位与字节相互作用（异或），相互作用（异或）的结果记为组合值，那么累加器中的新值等于组合值加上（按模2异或）累加器中未改变的那一半即为新的crc值。

　　组合值只有256种可能，因此可利用硬件模拟算法先算好它们的crc值预先填入一张表中，该表的每一单元对应相对值的crc。这样就可以通过查表法来计算crc值，以便大大提高crc运算的速度。下面给出用Ｃ语言编制的计算程序。

　　首先将crc生成多项式及crc值表定义为一个头文件crc.h：

　　#define crc_ccitt 0x1021 //ccitt多项式

#define rev_ccitt 0x8408 //反转ccitt多项式

#define crc16 0x8005 //crc16多项式

#define rev_crc16 0x

001 //反转crc16多项式

unsigned short crc_tble[256];　//crc值表

注：16位ccitt多项式（x16 +x12 +x5 +1）和16位crc16多项式（x16 +x15 +x2+1）为两种最常用的crc多项式。反转多项式是指在数据通讯时，字节先传送或接收低位字节，如重新排位影响crc计算速度，故设反转多项式。

　　造表和查表法crc计算函数。

#include "crc.h"

void mk_crctble(unsigned short genpoly)

unsigned short crc_tble[256];

unsigned short

ccnum=0;

unsigned short i,j,k;

for(i=0,k=0;i<256;i++,k++)

　　　i<<=8;

for(j=8;j>0;j--)

　　　　　　　if((i^ccnum)&0x8000)

ccnum=(

ccnum<<=1)^genpoly;

　　　　　　　else

ccnum<<=1;

　　　i<<=1; 　　　

crc_tble[k]=

ccnum;　　　

void crc_upd

te(unsigned short d

,unsigned short

ccnum)

ccnum=(

ccnum<<=8)^crc_tble[(

ccnum>>8)^d

];　

注：genpoly为crc多项式，

ccnum为累加器值（即为新的crc值），d

为参与crc计算的。

参考文献：

【１】顾慰文，《纠错码及其在计算机系统中的应用》，人民邮电出版社，1980。

【２】j.p.roth,w.g.bouricius: progrmmed

lgorithms to compute tests todetect nd nd distinguish between filures in logic circuits, ieeetrns. electron. comput.,ec-16,no.5,pp.567-580(1977)

【３】joe c

mpell:c progr

mmer's guide to seri

l communic

tion.(1988)

主页 > 实用文摘 > 教育文摘_04 > > 详细内容

用C语言实现CRC校验计算_信息技术论文