你如何计算在CRC中使用的XOR余？

Question

我想记住的数学是如何制定出计算在循环冗余校验的XOR算法的剩余部分，以验证网络消息的其余位。

我不应该抛出该文本的书。

这是很容易在代码中完成的，但它是如何通过手工制定出来的？

我知道它看起来像一个标准的除法算法，但我不记得在哪里从那里得到的余数。

      ___________
1010 | 101101000

注意：我做了谷歌，但没能找到他们映射盘算其余的步骤的地方

Answer 1

有长除以二进制11上有维基百科的一个例子。

Answer 2

1010 | 101101000
       1010
       0001 this result is 1011 XOR 1010 = 0001
          1010
          1010
          0000  thus no remainder. 

因此101101000是完美的，且在发生在传输/接收无差错

Answer 3

在我的经验更容易通过手工计算的时候，尤其是当有是有很多零的将其转换为一个多项式。

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