CRC循环冗余校验码

1、1循环冗余校验循环冗余校验法 发送端 给定一个k位的数据包，发送端产生nk位序列，称之为校验位 这样组成一个可被预定数除尽的n位数据 接收端 将接收到的数据除以相同的数 如果余数为0则表示没有错误发生下一页回目录2模模-2运算运算 模-2运算使用无进位的二进制加法，相当于异或（ exclusive-OR, XOR ）运算，无进位的二进制减法也用XOR运算。例如， 下一页上一页回目录3参数定义参数定义 为方便说明，定义一些参数： T = 传送的n位数据。 D = k位元的有用信息；即T之前面k位元。 F = (n-k) FCS位元；即T之后的(n-k)位元。 P = (n-k+1)位元之模式序列

2、；即预定之除数。 Q = 商 R =余数 下一页上一页回目录4CRCCRC使用使用2-2-模运算分析模运算分析 希望T /P 整除没有余数，下式可清楚地表示T、D和F的关系 式中D乘上2n-k 的作用是向左移n-k位元且原来的位元补零，再加上F可得到D和F的组合位T 将2n-kD 除以P 表示成 余数则相当于FCS，T然后可写成 FDTkn2PRQPDkn2RDTkn2(8.1) 下一页上一页回目录5CRC使用使用模模-2运算分析运算分析 校验R是否满足T/P没有余数 的条件 代入(8.1)式可得 没有余数,因此 T 整除以得 PPRPDPRDPTknkn22QPRRQPRPRQPT下一页上一

3、页回目录6CRC使用模使用模-2运算范例运算范例 给定 信息 (10位元) 模式序列 (6位元) FCS, R = 待计算 (5位元) 可知n = 15、k = 10和(n-k) = 5 将信息乘上25得到 1000 将结果除以P 可得R =01110 将余数与25D相加可得到T = 1110，然后传送此序列。 1010001101D 110101P下一页上一页回目录7CRC使用模使用模-2运算范例运算范例(续续) 假设传输没有错误发生，接收端将完整接收到T，将接收数据除以P 下一页上一页8CRC使用使用多項式分析多項式分析 将所有位元值表时称多项式 系数与二进制数种的位元相对应 XRXDXX

4、TXPXRXQXPXDXknkn下一页上一页9CRC使用多項式分析范例使用多項式分析范例如前例，将D = 1010001101和P = 110101分別表示成D(X) = X9+ X7+ X3+ X2+ 1和P(X)=X5+ X4+ X2+ 1，而余数R = 01110对应R(X) = X3+ X2+ X。 下一页上一页10循环冗余校验(CRC)码 信息位信息位k和码长和码长n可变，校验位长度可变，校验位长度n-k固定，固定，符合符合(n-i , k-i)缩短循环码的特点。缩短循环码的特点。 以一个选定的以一个选定的 (n,k)循环码为基础，改变循环码为基础，改变i值，值，得出任意信息长度的码

5、字，而纠检错能力得出任意信息长度的码字，而纠检错能力保持不变。保持不变。 循环冗余校验码（循环冗余校验码（(CRC-Cyclic Redundancy Check) ）是系统的缩短循环）是系统的缩短循环码。码。 11例例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-k m(x)除以g(x),得余式 r(x)=xn-k m(x) mod g(x) = x4( x5+

6、 x4+1) mod g(x) =(x9+ x8+ x4) mod g(x) = x3+ x2 于是发码C(x)= xn-k m(x) + r (x) = x9+ x8+ x4 +x3 +x2，对应的码字是 (1100011100)。 接收端的CRC校验实际上就是做除法。如果收码无误，R(x)除以g(x)应得余式0；反之，如果余式不等于零就说明一定有差错。 12CRC常用多項式常用多項式 四个常用的P(X)多項式 : CRC12 X12 + X11 + X3 + X2 + X + 1 CRC16 X16 + X15 + X2 + 1 CRC CCITT X16 + X12 + X5 + 1 C

7、RC 32 X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1下一页上一页13CRC CRC 使用数字逻辑分析使用数字逻辑分析逻辑门和移位寄存器所组成的除法电路来描述和实现：XOR 逻辑门 至多(n-k)个XOR逻辑门 根据除数多项式P(X)的系数项決定逻辑门使用与否，但1和Xn-k两项除外 移位寄存器 串列信息一次一个比特地输入移位寄存器 至多(n-k) 个移位寄存器, 等于FCS的长度下一页上一页14移位寄存器除法電路移位寄存器除法電路(a) 移位寄存器实现 图8.3 多项式 的移位寄

8、存器除法电路 1245XXX1位元移位寄存器XOR 电路输入(10位元)输出(15位元)开关1开关215移位寄存器除法电路移位寄存器除法电路( (续续) )(b) 以输入1010001101为例 图8.3 多项式 的移位寄存器除法电路1245XXX下一页上一页16数字逻辑实现数字逻辑实现 CRC图4 实现除法器 CRC结构 knknnXXAXAXA11221.1输入(10位元)输出(n位元)开关1开关2下一页上一页17直接错误更正直接错误更正图8.5直接错误更正程序 (a) 传送器 (b) 接收器 信息字码信息FEC编码器编码器FEC解码器解码器沒有错误或错误得以更正检知错误但无法更正错误标示下一页上一页18循环码循环码 容易地使用线性反馈移位寄存器( liner feedback shift registers, LFSRs )实现 假如n位元序列c c = (c0, c1, cn-1)是一个有效字码 ,将字码c c循环地向右移一个位置得到的序列(cn-1, c0, c1, cn-2)也