Примитивность полиномов CRC

Автор сказал: «Обычно примитивные полиномы имеют тенденцию иметь довольно хорошие (то есть, низкие) веса при HD = 2 по сравнению со многими другими полиномами. С тех пор, как я посмотрел, прошло некоторое время, но я думаю, что во всех случаях прямо выше HD = 2 точка останова, полином с наименьшим весом всегда был примитивным. "

Для некоторых реализаций алгоритма малый вес может обеспечить более быстрое вычисление.

... имеет оптимальную длину для HD = 3 и хорошую производительность HD = 2 выше этой длины.

Заявление плохо сформулировано. Я нахожу его в нижней части этой веб-страницы под «Обозначение:»

https://users.ece.cmu.edu/~koopman/crc

В В этой и других статьях, которые я нахожу, аббревиатура «HD» представляет минимальное расстояние Хэмминга для CRC: для HD = k + 1, CRC может обнаруживать любой шаблон из k битовых ошибок в сообщении вплоть до некоторой длины (как показано в столы). Как вы заявили, «все CRC имеют бесконечную длину данных при HD = 2».

Использование фразы «хорошая производительность HD = 2 выше этой длины» сбивает с толку. Веб-сайт выше ссылается на веб-сайт ниже, который включает в себя утверждение «Длина HD = 2 всегда бесконечна и поэтому всегда исключается из этого списка».

https: //users.ece .cmu.edu / ~ koopman / crc / notes.html

---

Расстояние вики Хемминга объясняет взаимосвязь между обнаружением битовых ошибок и расстоянием Хемминга: «код C называется обнаружением ошибок k, если и только если минимальное расстояние Хэмминга между любыми двумя из его кодовых слов составляет не менее k + 1. «Как вы сказали,« все CRC имеют бесконечную длину данных при HD = 2 », то есть все CRC могут обнаружить любую ошибку в одном бите независимо от длины сообщения.

Что касается «оптимальной длины для HD = 3», что означает возможность обнаружения 2-битной ошибки, рассмотрим регистр сдвига с линейной обратной связью на основе полинома CRC, инициализированный любым не -нулевое значение, если вы будете циклически повторять регистр достаточно времени, он вернется к исходному значению. Для n-битовой CRC, основанной на n + 1-битном примитивном полиноме, регистр будет циклически перебирать все 2 ^ n - 1 ненулевых значений перед повторением. Максимальная длина сообщения (то есть длина данных плюс длина CRC), при которой невозможно обнаружить 2-битную ошибку, составляет 2 ^ n - 1. Для сообщения длиной 2 ^ n или больше, тогда для любое «i», если бит [0 + i] и бит [(2 ^ n) -1 + i] имеют ошибку, примитивный CRC не сможет обнаружить 2-битную ошибку. Если полином CRC не является примитивным, максимальная длина для отказоустойчивого обнаружения 2 битов будет уменьшена, а не "оптимальной".

Для регистра сдвига с линейной обратной связью, основанного на любом полиноме CRC, инициализированном любым ненулевым значением, независимо от того, сколько раз он его зацикливал, он никогда не будет содержать значение ноль. Это один из способов объяснить, почему «все CRC имеют бесконечную длину данных при HD = 2» (способны обнаруживать однобитовые ошибки).