作者LPH66 (凉宫春日症候群)
看板CSSE
标题Re: [问题] 看不太懂这个 CRC-16 code generation...
时间Sun Oct 29 20:01:36 2006
※ 引述《lg31cm (我住5F)》之铭言:
: if (crc & 0x8000)
: crc = crc << 1 ^ 0x1021;
: else
: crc = crc << 1;
: 手算我已经很熟习,不过看到这段 code 觉得有点神奇,我有把 count 以 1 带入
: 用手算过,跟手算的过程一样,但是用 > 1 带入过程就不一样了,总觉得背後应该
: 有个数学原理可以展开原手算的方法,然後才能写出这样的程式,不知道各位前辈
: 能不能指点一下,thank you!
重点在於这个 (crc << 1)^0x1021
crc&0x8000非0 表示乘上多项式x後出现x^16次项 (因为原式有x^15次项)
而在CRC的计算里 因为是Mod 2 如果出现x^16项一定是1
所以这样的多项式除以x^16+x^12+x^5+1求余就等於原式减去它
在mod 2里减去它又等於对这四项做系数1<-->0的变换 (1-1=0, 0-1=1 (mod 2))
以binary来说就是xor上0x(1)1021 (binary:(1)0001000000100001)
1 111111
次方: 6 5432109876543210
↑
x^16项因为是一定要减掉的, 所以就直接让这一位移出去, 就不用xor
而crc&0x8000是0的话表示原式没有x^15项 所以就直接乘上x
--
実琴:「
河野!你真的就这样被
物质慾望给吸引过去了吗?!」
亨:「只要
穿着女装摆出亲切的样子,所有必要花费就能
全免,似乎一点都不坏啊。」
実琴:「难道你没有
男人的尊严了吗?!」
亨:(断然道)「
没有。在
节衣缩食且
生活吃紧的
学生面前,
没有那种东西。」
--プリンセス・プリンセス 第二话
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 192.192.197.112
1F:推 puzi:这跟我要这星期交的作业好像喔! 11/02 15:31