Обнаружение одиночного бита с помощью CRC (проверка циклическим избыточным кодом) - PullRequest
Новая
       77

Обнаружение одиночного бита с помощью CRC (проверка циклическим избыточным кодом)

0 голосов
/ 29 декабря 2018

Я сталкивался с некоторыми проблемами, связанными с обнаружением однобитовой ошибки на основе генераторов CRC, и пытался проанализировать, какой генератор обнаруживает однобитовую ошибку, а какой нет.

Предположим, если у меня естьполином CRC-генератора как x 4 + x 2 .Теперь я хочу знать, гарантирует ли он обнаружение однобитовой ошибки или нет?

Согласно ссылкам 1 и 2 ,Я заканчиваю некоторые пункты: -

1) Если k = 1,2,3 для многочлена ошибки x k , то остатки будут x, x 2 ,x 3 соответственно в случае полиномиального деления на полином генератора; x 4 + x 2 и, согласно ссылкам, если генератор имеет более одного члена и коэффициентаЕсли x 0 равен 1, то могут быть обнаружены все ошибки в одном бите.Но это не говорит о том, что если коэффициент x 0 не равен 1, то однобитовая ошибка не может быть обнаружена.Это говорит о том, что «В циклическом коде те e (x) ошибки, которые делятся на g (x), не перехватываются».

2) Я должен проверить остаток от E (x) / g(x) где E (x) (предположим, это x k ), где k = 1,2,3, ... - многочлен ошибки, а g (x) - многочлен генератора.Если остаток равен нулю, я не могу обнаружить ошибку, а когда она не равна нулю, я могу обнаружить ее.

Итак, по моему мнению, полином генератора x 4 + x 2 гарантирует обнаружение однобитовой ошибки на основе вышеуказанных 2 пунктов. Пожалуйста, подтвердите, прав я или нет.

1 Ответ

0 голосов
/ 29 декабря 2018

, если коэффициент x 0 не равен 1, то однобитовая ошибка не может быть обнаружена?

Если коэффициент x 0 не равно 1, это то же самое, что смещение полинома CRC влево на 1 (или более) бит (умножение на некоторую степень x).Сдвиг полинома CRC влево на 1 или более бит не повлияет на его способность обнаруживать ошибки, он просто добавляет 1 или более нулевых битов к концу кодовых слов.

генератор полинома x 4 + x 2 гарантирует обнаружение однобитовой ошибки

Исправить.х 4 + х 2 равен х 2 + 1 сдвинут влево на два бита, х 4 + х 2 = (x 2 ) (x 2 + 1) = (x 2 ) (x + 1) (x + 1), а с x 2 + 1 может обнаружить любую однобитовую ошибку, а затем x 4 + x 2 .Также с термином (x + 1) (два из них) он добавляет проверку четности и может обнаруживать любое нечетное количество битовых ошибок.

В общем, все полиномы CRC могут обнаруживать одинбитовая ошибка независимо от длины сообщения.Все полиномы CRC имеют "циклический" период: если вы используете полином CRC в качестве основы для регистра сдвига с линейной обратной связью , а начальное значение составляет 000 ... 0001, то после некоторого фиксированного числа циклов, он вернется к 000 ... 0001.Самый простой сбой для CRC - это наличие 2-битной ошибки, где 2 бита разделены расстоянием, равным циклическому периоду.Скажем, период равен 255 для 8-битного CRC (9-битный полином), затем 2-битная ошибка, одна в бите [0] и одна в бите [255], приведет к CRC = 0 и не будет обнаружена, этоне может произойти с ошибкой в ​​один бит, он просто продолжит проходить циклы, ни один из которых не содержит значения 0. Если период равен n циклам, то ошибка 2-битового кода не может произойти, если количество битов в сообщении+ CRC равен <= n.Все полиномы CRC, являющиеся произведением любого полиномиального времени (x + 1), могут обнаруживать любое нечетное количество ошибок по битам (поскольку x + 1 по существу добавляет проверку четности).</p>

Сдвиг полинома CRC влево на z битов означает, что каждое кодовое слово будет иметь z завершающих нулевых битов.Есть случаи, когда это делается.Допустим, у вас есть быстрый 32-битный алгоритм CRC.Чтобы использовать этот алгоритм для 16-битного CRC, 17-битный полином CRC смещается влево на 16 бит, так что наименее значимый ненулевой член равен x 16 .После вычисления с использованием 32-битного алгоритма CRC 32-битный CRC сдвигается вправо на 16 бит для получения 16-битного CRC.

...