Деление в алгоритме CRC Опции

[Костян]

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

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

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

CODE

11010001
100101
--------
100010
100101
------------
      1111

остаток 1111 = 0xF


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


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

[blackfin]

Итак дано:
CRC-5 x^5+x^2+1
Исходные данные: 0xB1
Делю в столбик

Код

11010001
100101
--------
100010
100101
------------
      1111

В чем ошибка ?

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

[Костян]

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

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

[blackfin]

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

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

[Костян]

Вот так ещё забавнее: 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) не верна. Это первое.
Второе: перед делением полиномов делимое сдвигается влево на кол-во разрядов делителя.
И тогда все сходится:

CODE

11010001000000
100101
--------
100010
100101
    111100
    100101
     110010
     100101
      101110
      100101
        10110

[Костян]

Поэтому формула CRC = 0xD1 % (x^5+x^2+1) не верна. Это первое.

согласен

Второе: перед делением полиномов делимое сдвигается влево на кол-во разрядов делителя.

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

[MrYuran]

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

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

[blackfin]

На самом деле это называется умножением в поле Галуа

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

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

[MrYuran]

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

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

[Костян]

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

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

[MrYuran]

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

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

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

[Костян]

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

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

[i-mir]

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

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

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

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

[ADA007]

В продолжение данной темы....
Может ли кто-нибудь представить здесь матиматическое решения даной задачи?
т.е. как бы это решалось в виде формулы
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 ?

[=GM=]

Можно вычислить по формуле

CRC5*b5 ^ CRC4*b4 ^ CRC3*b3 ^ CRC2*b2 ^ CRC1*b1 ^ CRC0*b0,

где
CRCi - определённые 6-ти битные коэффициенты
bi - текущие биты полинома-делимого
* - операция "умножение" (на bi=1 или bi=0)
^ - операция "исключающее или"

[Dmitry Dubrovenk...]

А я вот хочу про онлайн-калькуляторы спросить.
Вроде же существуют различные варианты подсчёта CRC, а в в/у калькуляторах только полином меняется.
Или, при разных алгоритмах, CRC всё-равно одинаковой получается?

[fontp]

В продолжение данной темы....
Может ли кто-нибудь представить здесь матиматическое решения даной задачи?
т.е. как бы это решалось в виде формулы
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 ?

Так и делить, уравновешиванием... как числа мы делим уголком, уравновешивая старший разряд, в данном случае старший разряд полинома
Например, (x^7+x^2+1) - (x^5+x^2+1)*(x^2) = -x^4 +1 = x^4 + 1 остаток
0xD1 - это другое - x^7 + x^6 + x^4 + 1

Но как верно замечено выше - обычно делить не надо, достаточно умножать, поскольку у каждого элемента X в конечном поле существует обратный элемент 1/X, вот на него достаточно и умножить , чтобы разделить на Х. А умножение на полином - это свертка