CRC除数计算

Question

我正在努力理解循环冗余校验（CRC），但是计算“除数”时感到困惑。

在维基百科上的示例中，输入为11010011101100，除数为11（1011）。

11010011101100 000 <--- input left shifted by 3 bits
1011               <--- divisor (4 bits) = x³+x+1
------------------
01100011101100 000 <--- result

如何计算除数？在这个例子中（x³+x+1）x是2吗？那么这个2从哪里来？

- tMC

---

在二进制中，除数就是其多项式的系数。x^3 + x + 1 等于 1*x^3 + 0*x^2 + 1*x + 1*1；读取系数得到1-0-1-1。 - Nemo

Answer 1

从同一维基百科的“CRC的数学”部分开始，“对这个类似除法的过程进行数学分析可以揭示如何选择一个保证良好误差检测性能的除数。” 这就是关键。 有些除数比其他除数更好，因此您只需找到标准除数并通常使用它。

该页面底部描述了使用的不同CRC以及定义其除数的多项式。

- Chris

---

给定一个 n 位的输入数据，如何找出除数的位？ - Sabito stands with Ukraine

Answer 2

在维基百科的下一句话中写道：

如果左侧除数位上方的输入位为0，则不执行任何操作。如果左侧除数位上方的输入位为1，则将除数异或到输入中。

这意味着：

1101 xor 1011 => 0110

- duedl0r

Answer 3

二进制中的除数就是其多项式的系数。x^3 + x + 1 = 1x^3 + 0x^2 + 1x +11；读取系数即可得到 1 0 1 1。

- user3387268