Итак дано:
CRC-5 x^5+x^2+1
Исходные данные: 0xD1

Из определения, CRC есть остаток от деления данных на полином. Значит CRC = 0xD1 % (x^5+x^2+1)

Делю в столбик

остаток 1111 = 0xF


Проверяю онлайн калькулятором
http://ghsi.de/CRC/index.php?Polynom=100101&Message=B1
ответ
0x16 (hexadecimal)
10110 (binary)


В чем ошибка ? В онлайн калькуляторе судя по приведенным ими листингам кода начальное значение CRC равно 0

0xB1 = 10110001, а у Вас делимое: 0xD1 = 11010001

упс описался, 0xD1 конечно. но в делении столбиком и ответ в онлайн калькуляторе я записал для 0xD1.

Вот так ещё забавнее: http://ghsi.de/CRC/index.php?Polynom=100101&Message=1

аппаратный вычислитель crc дает такое же значение , что и этот онлайн по выше приведенной ссылке
http://www.easics.com/webtools/crctool
:-)

В том, что деление полиномов и деление чисел - несколько разные операции. Деление чисел выполняется сдвигом и вычитанием, деление полиномов - сдвигом и вычитанием по модулю 2, которое идентично сложению по модулю 2 (оно же "Исключающее ИЛИ", XOR). Поэтому формула CRC = 0xD1 % (x^5+x^2+1) не верна. Это первое.
Второе: перед делением полиномов делимое сдвигается влево на кол-во разрядов делителя.
И тогда все сходится:

согласен


Спасибо, разобрался . Только сдвиг идет не на кол-во разрядов делителя, а на степень полинома, что меньше на 1 сдвиг. В Вашем делении в столбик последний 0 лишний. И этот сдвиг идет только при вычислении CRC.
Классическая схема деления полиномов не предполагает сдвига, если я все правильно понимаю.

На самом деле это называется умножением в поле Галуа
А вычисляется сдвигом и сложением по модулю 2 (XOR)

Простейший "аналоговый" кодер/декодер циклических кодов - это сдвиговый регистр с обратными связями, которые "приксориваются" в разрядах, соответствующих образующему полиному.

Что называется "умножением в поле Галуа"? Деление по модулю на простой многочлен так называется?

Сообщение отредактировал blackfin - Sep 7 2012, 14:22

В данном случае - да.
Причем, и кодирование (умножение) и декодирования (как бы деление) производится одинаково.

не совсем. Операция нахождения CRC - есть деление на многочлен в поле Галуа. Откуда взялось умножение то ?
А при кодирование и декодировании выполняется только операция деления (при кодировании находится остаток от деления, при декодировании идет проверка, что остаток равен нулю)

Ну это смотря с какой стороны зайти.
Ну да ладно, пусть будет деление.

А я попутно интересную статью нагуглил, очень может пригодиться.

это обшеизвестно, что crc не противостоит взлому, достаточно только ход байтов переставить и получим тот же CRC

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

Ближе к истине то, что CRC является обычной хеш-функцией или "сверткой",
не более чем. В процессе работы входной массив данных "перемешивает"
строку фиксированной длины: или по-другому - последовательно сдвигаем
массив данных, если на выходе "1" - делаем XOR со строкой CRC и все !

Декодирование - это не умножение на полином, а точно такое же хеширование.
К сжалению попытка математизировать эту простую функцию привела к хаосу.

Проще понять ее на "железе" - в инете есть примеры сдвиговых регистров CRC.

В продолжение данной темы....
Может ли кто-нибудь представить здесь матиматическое решения даной задачи?
т.е. как бы это решалось в виде формулы
0xD1 = x^7+x^2+1
0x25 = x^5+x^2+1
и это надо поделить друг на друга...
как из (x^7+x^2+1)*x^N mod x^5+x^2+1 получить x^4+x^2+x^1 ?