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