CRC循环冗余校验码.ppt

循环冗余校验法,发送端给定一个k位的数据包，发送端产生nk位序列，称之为校验位这样组成一个可被预定数除尽的n位数据接收端将接收到的数据除以相同的数如果余数为0则表示没有错误发生,下一页,上一页,回目录,模-2运算,模-2运算使用无进位的二进制加法，相当于异或（exclusive-OR,XOR）运算，无进位的二进制减法也用XOR运算。例如，,下一页,上一页,回目录,参数定义,为方便说明，定义一些参数：T=传送的n位数据。D=k位元的有用信息；即T之前面k位元。F=(n-k)FCS位元；即T之后的(n-k)位元。P=(n-k+1)位元之模式序列；即预定之除数。Q=商R=余数,下一页,上一页,回目录,CRC使用2-模运算分析,希望T/P整除没有余数，下式可清楚地表示T、D和F的关系式中D乘上2n-k的作用是向左移n-k位元且原来的位元补零，再加上F可得到D和F的组合位T将2n-kD除以P表示成余数则相当于FCS，T然后可写成,(8.1),下一页,上一页,回目录,CRC使用模-2运算分析,校验R是否满足T/P没有余数的条件代入(8.1)式可得没有余数,因此T整除以得P,下一页,上一页,回目录,CRC使用模-2运算范例,给定信息(10位元)模式序列(6位元)FCS,R=待计算(5位元)可知n=15、k=10和(n-k)=5将信息乘上25得到101000110100000将结果除以P可得R=01110将余数与25D相加可得到T=101000110101110，然后传送此序列。,下一页,上一页,回目录,CRC使用模-2运算范例(续),假设传输没有错误发生，接收端将完整接收到T，将接收数据除以P,下一页,上一页,CRC使用多項式分析,将所有位元值表时称多项式系数与二进制数种的位元相对应,下一页,上一页,CRC使用多項式分析范例,如前例，将D=1010001101和P=110101分別表示成D(X)=X9+X7+X3+X2+1和P(X)=X5+X4+X2+1，而余数R=01110对应R(X)=X3+X2+X。,下一页,上一页,循环冗余校验(CRC)码,信息位k和码长n可变，校验位长度n-k固定，符合(n-i,k-i)缩短循环码的特点。以一个选定的(n,k)循环码为基础，改变i值，得出任意信息长度的码字，而纠检错能力保持不变。循环冗余校验码（(CRC-CyclicRedundancyCheck)）是系统的缩短循环码。,例610某CRC码的生成多项式g(x)=x4+x+1。如果想发送一串信息110001的前6位并加上CRC校验，发码应如何安排？收码又如何检验？解：本题信息多项式m(x)=x5+x4+1,即k=6，因此n=10，degg(x)=4=n-k。将xn-km(x)除以g(x),得余式r(x)=xn-km(x)modg(x)=x4(x5+x4+1)modg(x)=(x9+x8+x4)modg(x)=x3+x2于是发码C(x)=xn-km(x)+r(x)=x9+x8+x4+x3+x2，对应的码字是(1100011100)。接收端的CRC校验实际上就是做除法。如果收码无误，R(x)除以g(x)应得余式0；反之，如果余式不等于零就说明一定有差错。,CRC常用多項式,四个常用的P(X)多項式:CRC12X12+X11+X3+X2+X+1CRC16X16+X15+X2+1CRCCCITTX16+X12+X5+1CRC32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1,下一页,上一页,CRC使用数字逻辑分析,逻辑门和移位寄存器所组成的除法电路来描述和实现：XOR逻辑门至多(n-k)个XOR逻辑门根据除数多项式P(X)的系数项決定逻辑门使用与否，但1和Xn-k两项除外移位寄存器串列信息一次一个比特地输入移位寄存器至多(n-k)个移位寄存器,等于FCS的长度,下一页,上一页,移位寄存器除法電路,(a)移位寄存器实现,图8.3多项式的移位寄存器除法电路,移位寄存器除法电路(续),(b)以输入1010001101为例,图8.3多项式的移位寄存器除法电路,下一页,上一页,数字逻辑实现CRC,图4实现除法器CRC结构,输入(10位元),输出(n位元),开关1,开关2,下一页,上一页,直接错误更正,图8.5直接错误更正程序,(a)传送器,(b)接收器,信息,字码,信息,FEC编码器,FEC解码器,沒有错误或错误得以更正,检知错误但无法更正,错误标示,下一页,上一页,循环码,容易地使用线性反馈移位寄存器(linerfeedbackshiftregisters,LFSRs)实现假如n位元序列c=(c0,c1,cn-1)是一个有效字码,将字码c循环地向右移一个位置得到的序列(cn-1,c0,c1,cn-2)也是个有效字码输入一个固定长度(k个位元)