Не полный ответ, но мой spoof code может быть адаптирован к этой проблеме.
Чтобы определить, что вы не удовлетворяли требованию расстояния Хэмминга 4 для заданной длины сообщения, вам нужно найти только одно кодовое слово с расстоянием Хэмминга 3. Если вы даете подмену набор местоположений бит в сообщение, он определит, какой из этих битов инвертировать, чтобы оставить CRC неизменным. Spoof просто решает набор линейных уравнений над GF (2), чтобы найти места бит для инвертирования.
Это быстро сократит длину сообщений, которые будут работать. Как только у вас есть длина кандидата, n, для которого вам не удалось найти кодовое слово расстояния 3, доказав, что есть no таких кодовых слов будет немного больше работы. Вам нужно будет сгенерировать все возможные 3-битные шаблоны, из которых n (n-1) (n-2)/6, и посмотрите, есть ли у них CRC нуля. В зависимости от n, это может быть не слишком сложным. Быстрый способ сделать это - генерировать CRC всех сообщений с помощью одного набора бит и исключать из всех выбранных трех CRC из этого набора, чтобы увидеть, является ли какой-либо из них нулевым.
Я предполагаю, что существует более быстрый способ сделать этот последний шаг, грамотно отбраковывая строки, используемые в решателе линейных уравнений, что позволяет использовать все позиции бит. Однако для меня это не достаточно, чтобы выразить доказательство.