Насколько эффективен алгоритм CRC?

В моей реализации алгоритма CRC в 200 000 сообщений k = 20 бит с использованием 53 (110101) в качестве делителя с частотой ошибок по битам 10 ^ (-3) есть 4987 сообщений с ошибками, и только одно из них остается незамеченным. Это действительные результаты? Может ли алгоритм CRC быть настолько эффективным, или у меня, вероятно, что-то не так в моей реализации? (Я не публикую свой код, потому что мне просто нужны отзывы о результатах, которые я хочу выполнить самостоятельно)

-Редактировать: я использовал алгоритм CRC здесь. Я использую число 53, чтобы разделить двоичное сообщение, а остаток, который я получаю, представляет собой последовательность проверки кадра. Затем эта последовательность добавляется в конец сообщения, после чего сообщение передается. На принимающей стороне переданное сообщение снова делится на 53, но на этот раз остаток должен быть равен 0, если только не произошла битовая ошибка. (Хотя возможны незамеченные битовые ошибки)


person A_Pumpkin    schedule 15.05.2021    source источник
comment
Вы используете 5-битный CRC? Сколько бит в CRC? Каждое сообщение 20 бит? (к само по себе ничего не значит.)   -  person Mark Adler    schedule 15.05.2021
comment
Опять же, каждое сообщение состоит из 20 бит? Добавляете ли вы 5-битный CRC к каждому сообщению?   -  person Mark Adler    schedule 16.05.2021
comment
25 бит извините за опоздание   -  person A_Pumpkin    schedule 16.05.2021
comment
Это то, что? Сообщение 25 бит? Сообщение плюс CRC составляет 25 бит? Хорошо, еще раз. Каждое сообщение состоит из 20 бит? Затем вы добавляете 5-битный CRC к каждому сообщению?   -  person Mark Adler    schedule 17.05.2021


Ответы (1)


Весьма вероятно, что ваша реализация битовых ошибок неверна.

Если я правильно читаю вопрос и каждое сообщение имеет 20 бит, то ожидаемое количество ошибочных сообщений равно 200000 (1 - (1 - 10-3)20) , то есть 3962. Стандартное отклонение примерно равно квадратному корню из этого числа, примерно 63. Ваши 4987 сообщений более чем на 16 стандартных отклонений превышают ожидаемое число! Вероятность того, что это произошло случайно, меньше 10-58. Итак, у вас есть ошибка.

Что касается ложных срабатываний, вы должны ожидать около одного (точнее, 0,982) в среднем на 200 000 20-битных сообщений с такой частотой ошибок по битам и этим конкретным 5-битным CRC.

Намного лучше для указанных вами условий полином x5 + x + 1 (100011). Это дает 0,0071 ложных срабатываний для того же случая.

person Mark Adler    schedule 15.05.2021
comment
Я вычислил тот же результат, 3962. Я не проверял его, но маловероятно, чтобы 5-битный CRC имел 2-битный случай отказа для 20-битного сообщения. CRC Zoo не включает шестнадцатеричный код 35 в качестве одного из 6-битных полиномов для 5-битного CRC. Если я правильно помню, вероятность 3-битной ошибки в 20-битном сообщении будет (0,001 ^ 3) (0,999 ^ 17) (гребенка (20,3)) ~= 0,00000112. - person rcgldr; 15.05.2021
comment
Вы правы, я добавил некоторые разъяснения в свой пост об используемом алгоритме. - person A_Pumpkin; 16.05.2021
comment
Какое минимальное количество битов ошибки приводит к ложному срабатыванию? Возможно, это можно было бы включить в ваш ответ для вероятности 0,0982 ложного срабатывания в 200 000 тестовых сообщений. Все еще жду, пока OP уточнит, составляет ли размер сообщения, включая CRC, 20 бит или 25 бит. - person rcgldr; 16.05.2021
comment
25 бит извините за опоздание - person A_Pumpkin; 16.05.2021