OpenVINOTM,给你看得见的未来!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » FPGA » 循环冗余校验 CRC的算法分析和程序实现

共1条 1/1 1 跳转至

循环冗余校验 CRC的算法分析和程序实现

助工
2014-12-21 10:34:24    评分

在数字通信系统中可靠与快速往往是一对矛盾。若要求快速,则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误地可能性增加,传送信息地可靠性下降。若是要求可靠,则使得传送消息地速率变慢。因此,如何合理地解决可靠性也速度这一对矛盾,是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时,用FEC方式比较理想。在传输过程误码率较高时,采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中,广泛采用ARQ方式,此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多,传统的有:奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接受到的校验码比较,如果二者一致则认为传输正确。但这些方法都有各自的缺点,误判的概率比较高。


循环冗余校验CRC(Cyclic Redundancy Check)是由分组线性码的分支而来,其主要应用是二元码组。编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法实现。


一、循环冗余校验码(CRC


CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式,由 。如一个8位二进制数10110101可以表示为: 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。


采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。


CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。CCITT建议:2048 kbit/s的PCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式g(x)= 。采用16位CRC校验,可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式g(x)= ;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式g(x)= 。CRC-32的生成多项式g(x)= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。


二、CRC校验码的算法分析


CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:


(1) 设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为 。


(2) 用生成多项式g(x)去除 ,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。


(3) 用 以模2的方式减去y(x),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。


从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式 ,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。


为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。


设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)= ,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成 ,数据块就成了1001000111000000。然后用g(x)去除 ,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。

































除数次数


被除数/ g(x)/结果


余数


0


1 001000111000000


100111000000


1 0011


0 000100111000000


1


1 00111000000


1000000


1 0011


0 00001000000


2


1 000000


1100


1 0011


0 001100



从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:


//reg是一个5 bits的寄存器


把reg中的值置0.


把原始的数据后添加r个0.


While (数据未处理完)


Begin


If (reg首位是1)


reg = reg XOR 0011.


把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。


End


reg的后四位就是我们所要求的余数。


这种算法简单,容易实现,对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。


为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:


由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0(reg的0位),同时reg3的数据移出reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和g(x)进行XOR运算;移出的数据为0时,reg不与g(x)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下,


//reg是一个4 bits的寄存器


初始化t[]={0011,0000}


把reg中的值置0.


把原始的数据后添加r个0.


While (数据未处理完)


Begin


把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。


reg = reg XOR t[移出的位]


End


上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0(reg的0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit,所以有 种选择。上述算法可以描述如下:


//reg是一个4 Byte的寄存器


初始化t[]={…}//共有 =256项


把reg中的值置0.


把原始的数据后添加r/8个0字节.


While (数据未处理完)


Begin


把reg中的值左移一个字节,读入一个新的字节并置于reg的第0个byte的位置。


reg = reg XOR t[移出的字节]


End


算法的依据和多项式除法性质有关。如果一个m位的多项式t(x)除以一个r阶的生成多项式g(x), ,将每一位 (0=<k<m)提出来,在后面不足r个0后,单独去除g(x),得到的余式位 。则将 后得到的就是t(x)由生成多项式g(x)得到的余式。对于CRC-32,可以将每个字节在后面补上32个0后与生成多项式进行运算,得到余式和此字节唯一对应,这个余式就是上面算法种t[]中的值,由于一个字节有8位,所以t[]共有 =256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节,通过查表法进行运算,大大提高了处理速度,故为大多数应用所采用。


三、CRC-32的程序实现。


为了提高编码效率,在实际运用中大多采用查表法来完成CRC-32校验,下面是产生CRC-32校验吗的子程序。


unsigned long crc_32_tab[256]={


0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d


};//事先计算出的参数表,共有256项,未全部列出。


unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)


{


unsigned long oldcrc32;


unsigned long crc32;


unsigned long oldcrc;


unsigned int charcnt;


char c,t;


oldcrc32 = 0x00000000; //初值为0


charcnt=0;


while (len--) {


t= (oldcrc32 >> 24) & 0xFF; //要移出的字节的值


oldcrc=crc_32_tab[t]; //根据移出的字节的值查表


c=DataBuf[charcnt]; //新移进来的字节值


oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中


oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor运算


charcnt++;


}


crc32=oldcrc32;


return crc32;


}


参数表可以先在PC机上算出来,也可在程序初始化时完成。下面是用于计算参数表的c语言子程序,在Visual C++ 6.0下编译通过。


#include <stdio.h>


unsigned long int crc32_table[256];


unsigned long int ulPolynomial = 0x04c11db7;


unsigned long int Reflect(unsigned long int ref, char ch)


{ unsigned long int value(0);


// 交换bit0和bit7,bit1和bit6,类推


for(int i = 1; i < (ch + 1); i++)


{ if(ref & 1)


value |= 1 << (ch - i);


ref >>= 1; }


return value;


}


init_crc32_table()


{ unsigned long int crc,temp;


// 256个值


for(int i = 0; i <= 0xFF; i++)


{ temp=Reflect(i, 8);


crc32_table= temp<< 24;


for (int j = 0; j < 8; j++){


unsigned long int t1,t2;


unsigned long int flag=crc32_table&0x80000000;


t1=(crc32_table << 1);


if(flag==0)


t2=0;


else


t2=ulPolynomial;


crc32_table =t1^t2 ; }


crc=crc32_table;


crc32_table = Reflect(crc32_table, 32);


}


}


结束语


——回复可见内容——



共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]