EEPW论坛

今天和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规则的除法取余就是 移位，异或操作， 用数字电路 或者 编写程序是非常容易实现的。