Binary/CRCdivision 余数

Question

我试图创建一个代码来计算 Java 中 CRC 错误 detection/correction 的余数，但我不知道它和二进制除法有什么区别。

时间：

    BigInteger G = new BigInteger("1001", 2);
    BigInteger M = new BigInteger("101110", 2);
    BigInteger R = M.remainder(G);

R 值将为：1
但是当我手动计算 CRC 余数时，它将是：011

这里有什么区别，有没有计算CRC余数的方法或算法？

Answer 1

CRC 的余数是 多项式 除法的余数。您将被除数和除数的位视为 Galois Field of two elements (called GF(2)) 上的多项式系数。在该字段中，加法变为 exclusive-or，乘法变为 and。 1+1是0​​，不是2，因为没有2，只有0和1。

如果你做你应该从高中记住的多项式除法，你就会得到答案。只需这些位就可以轻松完成 GF(2):

          101
      --------
1001 / 101110
       1001
       ------
         1010
         1001
         ----
           11

所以我们得到商 101 和余数 11。