Обнаружение одиночного бита с помощью CRC(проверка циклическим избыточным кодом)
Я проходил через некоторые проблемы, связанные с обнаружением однобитовой ошибки на основе генераторов CRC, и пытался проанализировать, какой генератор обнаруживает однобитную ошибку, а какой нет.
Предположим, если у меня есть полином CRC-генератора как x4 + x2. Теперь я хочу знать, гарантирует ли это обнаружение однобитовой ошибки или нет?
Согласно ссылкам 1 и 2, я заключаю некоторые пункты:
1) Если k=1,2,3 для многочлена ошибки xk, то остатки будут x, x2, x3 соответственно в случае полиномиального деления на многочлен генератора x4 + x2 и согласно ссылкам, если генератор имеет более одного слагаемого, а коэффициент x0 равен 1, тогда все однобитовые ошибки могут быть перехвачены. Но это не говорит о том, что если коэффициент х0 не равен 1, то однобитовая ошибка не может быть обнаружена. Говорят, что "в циклическом коде те e(x) ошибки, которые делятся на g(x), не улавливаются".
2) Я должен проверить остаток от E(x)/g(x), где E(x)(предположим, это xk), где k=1,2,3,... - многочлен ошибки и g (х) является генератором полинома. Если остаток равен нулю, я не могу обнаружить ошибку, а когда она не равна нулю, я могу обнаружить ее.
Итак, по моему мнению, генератор полинома x4 + x2 гарантирует обнаружение однобитовой ошибки на основе вышеуказанных 2 пунктов. Пожалуйста, подтвердите, прав я или нет.
1 ответ
если коэффициент x 0 не равен 1, то ошибка в одном бите не может быть обнаружена?
Если коэффициент x 0 не равен 1, это то же самое, что смещение полинома CRC влево на 1 (или более) бит (умножение на некоторую степень x). Сдвиг полинома CRC влево на 1 или более битов не повлияет на его способность обнаруживать ошибки, он просто добавляет 1 или более нулевых битов к концу кодовых слов.
генератор полинома х 4 + х 2 гарантирует обнаружение однобитовой ошибки
Правильный. x 4 + x 2 - это x 2 + 1, сдвинутый влево на два бита, x 4 + x 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 по существу добавляет проверку четности).
Сдвиг полинома CRC влево z бит означает, что каждое кодовое слово будет иметь z завершающие нулевые биты. Есть случаи, когда это делается. Допустим, у вас есть быстрый 32-битный алгоритм CRC. Чтобы использовать этот алгоритм для 16-битного CRC, 16-битный полином CRC сдвигается влево на 16 бит, так что наименее значимый ненулевой член равен x 16. После вычисления с использованием 32-битного алгоритма CRC 32-битный CRC сдвигается вправо на 16 бит, чтобы получить 16-битный CRC.