Подтверждение результата контрольной суммы обнаружения ошибок CRC

Question

Говорят, что CRC (Cyclic Redundancy Checksum) может обнаруживать пакетные ошибки менее чем r + 1 бит, где r - степень полинома. Кроме того, пакет с длиной больше r + 1 битов обнаруживается с вероятностью 1 - 2^-r.

Может ли кто-нибудь направить меня к тому же доказательству?

Answer 1

Не совсем верно. R- битный CRC обнаружит все последовательности импульсов длиной r+1, за исключением одного шаблона, самого полинома. Смотрите эти лекционные заметки для доказательства.

Просто для того, чтобы сообщение не обнаруживало ошибки, полином CRC должен делить полином ошибки. Если многочлен ошибки имеет длину r битов, то многочлен степени r+1, у которого нет x в качестве множителя (т. Е. Имеет 1 член), не может делить многочлен степени r и единственный многочлен r+1 степени, который он может разделить это само по себе. Все полиномы CRC имеют 1 член.

Ваше другое утверждение является свойством любого хеша r- бита, который распределяет сообщения с равной вероятностью по всем возможным значениям хеша r- бита, что делает CRC. 2^-r - это просто вероятность того, что примененная ошибка просто приведет к тому же CRC, для которого существует 2^r возможностей. Это то же самое, что сказать, что вероятность выпадения того же числа, которое вы только что выпали на шестигранном кубике, равна 1/6.