找到最大。 CRC多项式和给定汉明距离的数据长度

Question

我正在寻找一种数值算法来计算给定CRC多项式和给定汉明距离的最大数据长度。

E.g.可以说我有一个8位的CRC与完整多项式0x19b。我想要达到4的汉明距离。现在在这些条件下可以保护多少位数据？

是否有一些数值算法（理想的C或C++代码）可以用来解决这个问题？

Answer 1

不是一个完整的答案，但我的spoof code可以适应这个问题。

要确定你没有满足给定消息长度的汉明距离为4的要求，你只需要找到一个汉明距离为3的单个码字。如果你在一个位置消息，它将确定要反转哪些比特以保持CRC不变。欺骗只是通过GF（2）求解一组线性方程来找到要反转的比特位置。

这将迅速缩小将工作的消息长度。一旦你有一个候选人的长度，n，你一直未能找到距离为3的码字，证明有没有这样的码字将是一个更多的工作。您需要生成所有可能的3位模式，其中有n（n-1）（n-2）/ 6，并查看它们中的任何一个是否具有零CRC。根据n，这可能不太令人生畏。一个快速的方法是使用一个位组来生成所有消息的CRC，并排除该组中所有三个CRC的所有选择，以查看是否有任何这些CRC是零。

我想通过智能剔除线性方程求解器中使用的行，可以实现最后一步的更快速的方法，从而允许所有位位置。然而，这里的余量不足以表达证据。