为什么框架必须比发电机多项式更长？

Question

这里是Andrew S. Tanenbaum，计算机网络，第5版，第3章（数据链路层）的摘录，第213页：

当采用多项式代码方法时，发件人和接收器必须在生成多项式， $ g（x）$ 时达成一致。提前。发电机的高级和低位位也必须是 $ 1 $ 。要使用 $ m $ 比对应于多项式 $ m（x）$ 来计算CRC ，框架必须长于发电机多项式。该想法是以这样的方式将CRC附加到框架的末尾，使得由Checksummed帧表示的多项式由 $ g（x）$ 可分离。当接收方获取CheckSummed帧时，它会尝试将其除以 $ g（x）$ 。如果存在剩下的，则存在传输错误。

我的问题是为什么用 $ m $ 比特对应于多项式 $ m（ x）$ ，框架必须长于发电机多项式？

我试图搜索原因，但实际上无法找到确切的答案，所以在我看来，如果发电机多项式比框架长，它将创建一个比数据位多的检查位，因为CRC用于错误检测代码和错误检测代码在发生更少错误时使用。但这是真的吗？

Answer 1

看到这一点的最简单方法来自接收器侧。就像在摘录中一样，“如果有剩下的话，还有一个传输错误。”隐含地，如果没有剩余状态，则没有传输错误。

没有传输错误的情况，没有余数意味着如果校验帧是 $ m'（x）$ ，则存在非零多项式 $ a（x）$ 这样

$$ m'（x）= g（x）a（x）$$

其中

$$ \ hbox {d}（m'（x））=hbox {d}（g（x））+ \ hbox {d}（a（x））$$

和 $ \ hbox {d}（）$ 表示多项式的程度（它是“长度”）。 由于<跨越类=“math-container”> $ \ hbox {d}（a（x））\ ge 1 $ ，然后

$$ \ hbox {d}（m'（x））> \ hbox {d}（g（x））$$

这意味着框架比发电机多项式更长。

Answer 2

如果crc多项式是 $ m $ -bit long，那么为创建 $ m'$ 从 $ m $ ，您需要添加 $ m $ 位（或者可能 $ M-1 $ 比特）。特别地，最终消息 $ m'$ 至少 $ m $ -bit long。