赞
踩
CRC的原理与实现
校验生成多项式是g(x),且g(x)的次数是L,
多项式表示为:g(x)=g0+ g1x1+…+ gLxL,CRC校验用除法电路完成,电路为:
如果寄存器的状态为R={r0,r1,…rL-1},那么在有新的输入的条件下,新的状态R’与R和输入x的关系是:
R’={ r’0,r’1,…r’L-1}
r’L-1=rL-2+rL-1*gL-1
r’L-2=rL-3+rL-1*gL-2
…….
r’1=r0+ rL-1*g1
r’0=x+ rL-1*g0
可以用矩阵表示为:
R’=R*T+[x ,0,0,….0];
T=
0 1 0 ... 0
0 0 1 … 0
………
0 0 0 … 1
g0 g1 g2 … gL-1
所以,对于长为信息长度为K,后面接L个0的序列,计算其CRC校验的方法:
第一步:将除法器寄存器清0。
第二步:将K位信息逐步按时钟拍入除法器做除法。并记住此时寄存器状态R
第三步:由于后面输入信息为0,则最终寄存器的状态为:
Rfinal=R*TL,这说明,如果我们预先知道了TL那么后面
这说明,有两个问题:
第一, 对于任意长度的序列,只需要做K次除法就可以得到余式。
第二, 已知K-1次的余式和第K次的输入,就可以得到两个方面,一是K次输入后的余式,二是如果只有K位信息,就直接可以给出校验。如果信息的长度大于K+1位,那么寄存器的信息即可用于求取第K+1拍时的寄存器信息。
所以我们可以采用迭代的方式得到CRC校验。
第一步:将除法寄存器R清0
第二步:根据寄存器R输入x,推算下一拍寄存器状态,并计算出CRC结果
R’=R*T+[x ,0,0,….0];
CRCout= R’*TL
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。