代码之家 › 专栏 › 技术社区 › Jeremiah

如何计算CRC中使用的异或余数?

polynomial-math crc xor

3

Jeremiah · 技术社区 · 16 年前

我试图记起数学是如何计算XOR算法的剩余部分的,通过循环冗余检查来验证网络消息的剩余部分。

我不该把那本教科书扔了。

这很容易在代码中完成,但是如何手工完成呢?

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

      ___________
1010 | 101101000

我用谷歌搜索了一下,但没能找到一个地方,在那里他们绘制了计算剩余部分的步骤。

3 回复 | 直到 16 年前

1

5

Himanshu THE ONLY ONE 12 年前

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

因此,101000是完美的,在传输/接收中没有发生错误

2

Marcus Åukasz Ostrowski 11 年前

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

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。

3

1

Rasmus Faber 16 年前

Wikipedia .