如何计算用于CRC的XOR余数？

Question

我试图回忆一下如何计算循环冗余校验中XOR算法的余数，以验证网络消息的余位。

我不应该扔掉那本教科书。

在代码中很容易实现，但是如何手工计算呢？

我知道它看起来像标准除法算法，但我不记得从哪里开始得到余数了。

      ___________
1010 | 101101000

注意：我已经谷歌过了，但是没有找到一个地方可以映射出计算余数的步骤。

- Jeremiah

Answer 1

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

因此，101101000是完美的，传输/接收过程中没有发生错误。

- Anant Rao

Answer 2

根据我的经验，在手动计算时，将其转换为多项式更容易，特别是当有很多零时。

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

对于每个项执行异或操作，然后得到新的被除数：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。

- Marcus

Answer 3

这是二进制11的长除法。在维基百科上有一个例子。

- Rasmus Faber

Answer 4

假设我们想把101110000除以1001。

101110000
1001
--------- XOR the 1011 and 1001
0010

现在我们将从顶部滑动数字，并且删除XOR结果开头的零，该结果为0010。

101110000
1001
--------- 
  1010

将结果与XOR 1001继续进行。

101110000
1001
--------- 
  1010
  1001
---------
  0011
--------- Remove zeros at the beginning
    1100
    1001
---------
    0101
--------- Remove zeros at the beginning
     1010
     1001
---------
     0011

答案是0011。

- Elvis23