3

我试图记住数学是如何计算出循环冗余检查中 XOR 算法的剩余部分以验证网络消息的剩余位的。

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

这在代码中很容易完成，但它是如何手工完成的呢？

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

      ___________
1010 | 101101000

注意：我确实谷歌了它，但无法找到他们在计算剩余部分时映射步骤的地方。

4

4 回答 4

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

因此 101101000 是完美的，并且在传输/接收中没有发生错误

于 2011-05-12T11:40:03.787 回答
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^3x^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。

于 2014-01-06T10:32:43.460 回答
1

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

于 2008-12-05T20:14:08.960 回答
0

假设我们要将 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。

于 2022-01-09T16:16:15.703 回答