2、将信息码左移R位,相当于对应的信息多项式C(X)*2R。
3、用生成多项式(二进制数)对信息码做除,得到R位的余数。
4、将余数拼到信息码左移后空出的位置,得到完整的CRC码。
【例】假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010,求编码后的报文。
解:
1、将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。
2、此题生成多项式有4位(R+1)(注意:4位的生成多项式计算所得的校验码为3位,R为校验码位数),要把原始报文C(X)左移3(R)位变成1010 000
3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除(高位对齐),相当于按位异或:
1010000
1011
------------------
0001000
1011
------------------
011
得到的余位011,所以最终编码为:1010 011
* CRC.C——CRC程序库 */
#define CRCCCITT 0x1021
#define CCITT-REV 0x8408
#define CRC16 0x8005
#define CRC16-REV 0xA001
#define CRC32-POLYNOMIAL 0xEDB88320L
/* 以上为CRC除数的定义 */
#define NIL 0
#define crcupdate(d,a,t)*(a)=(*(a)<<8)^(t)[(*(a)>>8)^(d)]
#define crcupdate16(d,a,t)*(a)=(*(a)>>8^(t)[(*(a)^(d))&0x00ff])
/* 以上两个宏可以代替函数crcupdate和crcrevupdate */
#include #include #include /* 函数crchware是传统的CRC算法,其返回值即CRC值 */ unsigned short crchware(data,genpoly,accum)
unsigned short data/* 输入的数据 */
unsigned short genpoly/* CRC除数 */
unsigned short accum/* CRC累加器值 */
{
static int i
data<<=8
for(i=8i>0i--)
{
if((data^accum)&0x8000)
accum=(accum<<1)^genpoly
else
accum<<=1
data<<=1
}
return (accum)
}
/* 函数mk-crctbl利用函数crchware建立内存中的CRC数值表 */
unsigned short *mk-crctbl(poly,crcfn)
unsigned short poly/* CRC除数--CRC生成多项式 */
R>unsigned short (*crcfn)()/* 指向CRC函数(例如crchware)的指针 */
{
/* unsigned short */malloc()*/
unsigned short *crctp
int i
if((crctp=(unsigned short*)malloc(256*sizeof(unsigned)))==0)
return 0
for(i=0i<256i++)
crctp=(*crcfn)(i,poly,0)
return crctp
}
/* 函数mk-crctbl的使用范例 */
if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL)
{
puts("insuff memory for CRC lookup table.\n")
return 1*/
/* 函数crcupdate用以用查表法计算CRC值并更新CRC累加器值 */
void crcupdate(data,accum,crctab)
unsigned short data/* 输入的数据 */
unsigned short *accum/* 指向CRC累加器的指针 */
unsigned short *crctab/* 指向内存中CRC表的指针 */
{
static short comb-val
comb-val=(*accum>>8)^data
*accum=(*accum<<8)^crctab[comb-val]
}
/* 函数crcrevhware是传统的CRC算法的反序算法,其返回值即CRC值 */
unsigned short crcrevhware(data,genpoly,accum)
unsigned short data
unsigned short genpoly
unsigned short accum
{
static int i
data<<=1
for(i=8i>0i--)
{
data>>=1
if((data^accum)&0x0001)
accum=(accum>>1)^genpoly
else
accum>>=1
}
return accum
}
/* 函数crcrevupdate用以用反序查表法计算CRC值并更新CRC累加器值 */
void crcrevupdate(data,accum,crcrevtab)
unsigned short data
unsigned short *accum
问问首页 问题库 问问之星| 问问团队 全部问题 >教育/科学>理工科>问题页 “我的问问 我的2009”活动奖品发放通知! 已解决问题 收藏 转载到QQ空间 假设CRC的生成多项式G(x)=x3+x+1转换成对应的2进制除数1011是如何转换成二进制的 [ 标签:crc 多项式,crc,二进制 ] 假设CRC的生成多项式G(x)=x3+x+1,信息码为11001校验码是多少,码字多少是CRC错误。 /wx梦想 回答:1 人气:1 解决时间:2009-04-29 18:27 满意答案在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。CRC也是给信息码加上几位校验码,以增加整个编码系统的码距和查错纠错能力。 CRC的理论很复杂,一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关,只能根据书上的结论死记。 循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为:假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2R,这样C(x)的右边就会空出R位,这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。 几个基本概念 1、多项式与二进制数码 多项式和二进制数有直接对应关系:x的最高幂次对应二进制数的最高位,以下各位对应多项式的各幂次,有此幂次项对应1,无此幂次项对应0。可以看出:x的最高幂次为R,转换成对应的二进制数有R+1位。 多项式包括生成多项式G(x)和信息多项式C(x)。 如生成多项式为G(x)=x4+x3+x+1, 可转换为二进制数码11011。 而发送信息位 1111,可转换为数据多项式为C(x)=x3+x2+x+1。 2、生成多项式 是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。 在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 应满足以下条件: a、生成多项式的最高位和最低位必须为1。 b、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时,应该使余数不同。 d、对余数继续做模2除,应使余数循环欢迎分享,转载请注明来源:内存溢出
评论列表(0条)