CRC循环冗余校验码ppt课件.ppt

《CRC循环冗余校验码ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、循环冗余校验法发送端给定一个k位的数据包，发送端产生nk位序列，称之为校验位这样组成一个可被预定数除尽的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=余数下一页上一页

2、回目录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将结果除以

3、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可变，校验

4、位长度n-k固定，符合(n-i,k-i)缩短循环码的特点。以一个选定的(n,k)循环码为基础，改变i值，得出任意信息长度的码字，而纠检错能力保持不变。循环冗余校验码（(CRC-CyclicRedundancyCheck)）是系统的缩短循环码。例6－10某CRC码的生成多项式g(x)=x4+x+1。如果想发送一串信息110001…的前6位并加上CRC校验，发码应如何安排？收码又如何检验？解：本题信息多项式m(x)=x5+x4+1,即k=6，因此n=10，deg[g(x)]=4=n-k。将xn-km(x)除以g(x),得余式r(x)=xn-km(x)modg(x)=

5、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)多項式:CRC–12X12+X11+X3+X2+X+1CRC–16X16+X15+X2+1CRC–CCITTX16+X12+X5+1CRC–32X32+X26+X23+X22+X16+X12+X11+X10+X8+

6、X7+X5+X4+X2+X+1下一页上一页CRC使用数字逻辑分析逻辑门和移位寄存器所组成的除法电路来描述和实现：XOR逻辑门至多(n-k)个XOR逻辑门根据除数多项式P(X)的系数项決定逻辑门使用与否，但1和Xn-k两项除外移位寄存器串列信息一次一个比特地输入移位寄存器至多(n-k)个移位寄存器,等于FCS的长度下一页上一页移位寄存器除法電路(a)移位寄存器实现图8.3多项式的移位寄存器除法电路1位元移位寄存器XOR电路输入(10位元)输出(15位元)开关1开关2移位寄存器除法电路(续)(b)以输入1010001101为例图8.3多项式的移位寄存器除法电路下一页

7、上一页数字逻辑实现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个位元)的資訊和产生一个固定的长度

8、的查核位元(n-k个位元