找到最大。 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是零。

我想通過智能剔除線性方程求解器中使用的行，可以實現最後一步的更快速的方法，從而允許所有位位置。然而，這裏的餘量不足以表達證據。