我想记住算法是如何计算周期性冗余校验中XOR算法的其余部分来验证网络消息的其余位的。如何计算CRC中使用的XOR余数?
我不应该丢掉那本教科书。
这很容易在代码中完成,但是它是如何通过手工完成的?
我知道它看起来像一个标准的划分算法,但我不记得从那里去哪里得到余数。
___________
1010 | 101101000
注:我没有谷歌,但没能找到他们映射盘算其余的步骤的地方。
我想记住算法是如何计算周期性冗余校验中XOR算法的其余部分来验证网络消息的其余位的。如何计算CRC中使用的XOR余数?
我不应该丢掉那本教科书。
这很容易在代码中完成,但是它是如何通过手工完成的?
我知道它看起来像一个标准的划分算法,但我不记得从那里去哪里得到余数。
___________
1010 | 101101000
注:我没有谷歌,但没能找到他们映射盘算其余的步骤的地方。
它是由二进制长分裂11.在Wikipedia上有一个例子。
1010 | 101101000
1010
0001 this result is 1011 XOR 1010 = 0001
1010
1010
0000 thus no remainder.
因此101101000是完美的,没有出现错误的发送/接收
以我的经验更容易通过手工计算时,将其转换为一个多项式,特别是当有是有很多零的。
1010 = 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3 + x = x3 + x
101101000 = x8 + x6 + x5 + x3
-------------------
x3 + x) x8 + x6 + x5 + x3
然后你划分与第一项的规模最大的一届在红利(x^8
)在除数(x^3
),导致x^5
。你把这个数字放在上面,然后乘以它与除数中的每个项。这就产生了第一次迭代如下:
x5
-------------------
x3 + x) x8 + x6 + x5 + x3
x8 + x6
做XOR每个术语,然后产生新的红利:x5 + x3
:
x5
-------------------
x3 + x) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
遵循相同的模式,直到分红的规模最大的一届越小则除数的最大的期限。计算完成后,它会是这样的:
x5 + x2
-------------------
x3 + x) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
x5 + x3
-------------------
0
在这种情况下,提醒为0,这表明,最有可能没有错误的传输过程中发生。
注意:在上面的示例中,我缩短x^y
为xy
以减少答案中的混乱,因为SO不支持数学等式格式。
注2:添加/从被除数中减去除数的倍数也将给予提醒0,因为(P(x) + a*C(x))/C(x) = P(x)/C(x) + a*C(x)/C(x)
给出相同的提醒作为P(x)/C(x)
由于a*C(x)/C(x)
提醒是0