题
我想记住的数学是如何制定出计算在循环冗余校验的XOR算法的剩余部分,以验证网络消息的其余位。
我不应该抛出该文本的书。
这是很容易在代码中完成的,但它是如何通过手工制定出来的?
我知道它看起来像一个标准的除法算法,但我不记得在哪里从那里得到的余数。
___________
1010 | 101101000
注意:强>我做了谷歌,但没能找到他们映射盘算其余的步骤的地方
解决方案
有长除以二进制11上有维基百科的一个例子。
其他提示
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
不隶属于 StackOverflow