这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » MCU » CRC

共1条 1/1 1 跳转至

CRC

工程师
2014-09-29 20:11:57     打赏

今天和SD卡的CRC7可谓是斗争了一天, 到处找这个CRC-7的生成资料, 几乎千篇一律, 这个说不明白,那个也说不明白, 估计都是ctrt+c, ctrl+v.
 
我总结一个清晰的吧(自我感觉啊).
 
先说CRC的基本运算规则吧. 
 
注意: 要在二进制的条件下考虑问题, 这样会理解容易, 况且最终要用计算机实现, 二进制是合适的.
 
信息多项式: M(x), 
CRC升成多项式: G(x), 阶数为r
CRC校验码多项式: R(x), 阶数为r-1, 就是CRC校验码的位数
 
R(x) =取余{ [(x的r次方)*M(x)]/G(x) } =取余{ [M(x)对应的码字左移r位][/G(x)对应的码字] };
 
以上是CRC的生成规则, 这个东西是数学家搞出来的, 无需讨论为什么.
 
乍看起来, 上面的运算也没什么, 只有实践之后, 才知道玄机很深.  
 
这个除法< [(x的r次方)*M(x)]/G(x) >, 不是按照普通除法规则进行的.


  普通除法规则: 从高位逐位截取被除数, 当被除数不小于除数的时候, 商1,  然后商乘以除数得一个
                积, 被除数减去这个积(左对齐减法, 积的右边补0), 得到的差做为新的被除
                数.
 
                重复上面的过程, 直到被除数用尽, 最后得到的那个差就是余数。


  
   CRC除法规则: 从高位逐位截取被除数, 当被除数最高bit与除数的最高bit
                相等且两者位数相同的时候, 商1,然后商
                乘以除数得一个积,被除数 “异或” 这个积(左对齐, 积的右边补0), 
                所得的结果作为新的被除数。
                
                重复上面的过程,直到被除数用尽, 最后“异或”出的那个数就是余数.


 


看个例子:


信息多项式:M(x) =x6 + x4 +x3 +1, 对应信息码 =1011001
CRC生成多项式:G(x) =x4+x3+1,阶数r =4 对应生成码字 =11001


根据CRC规则:CRC校验码字 =取余[(1011001左移4位)/11001]
                         =取余[(10110010000)/11001],   保留低 r =4 =4 位



用普通除法规则计算的 CRC校验码字 =1000, 过程不给出, 因为普通除法大家都熟悉



用CRC除法规则计算的 CRC校验码字 =1010, 下面是具体过程:


截取被除数 1,0110010000, 不够商1,继续截取
截取被除数 10,110010000, 不够商1,继续截取
截取被除数 101,10010000, 不够商1,继续截取
截取被除数 1011,0010000, 不够商1,继续截取
截取被除数 10110,010000, 够商1,做异或


10110,010000 异或 =11001 000000 =01111010000


去掉高位连0,形成新被除数 1111010000,


截取被除数 11110,10000, 够商1,做异或


11110,10000 异或 11001 00000 =00111 10000


去掉高位连0,形成新被除数 1111 0000


截取被除数11110,000, 够商1,做异或


11110,000 异或 11001 000 =00111 000


去掉高位连0,形成新被除数 111 000


截取被除数 11100,0, 够商1,做异或


11100,0 异或  11001 0 =001010


去掉高位连0,形成新被除数 1010


这个被除数1010无论怎样截取,都不够商1了,因此,它就是最后的余数,就是结果。



可见,CRC规则的除法取余就是 移位,异或操作, 用数字电路 或者 编写程序是非常容易实现的。


共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]