Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Деление в алгоритме CRC
Форум разработчиков электроники ELECTRONIX.ru > Cистемный уровень проектирования > Математика и Физика
Костян
Итак дано:
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
Цитата(Костян @ Sep 7 2012, 15:59) *
Итак дано:
CRC-5 x^5+x^2+1
Исходные данные: 0xB1
Делю в столбик
Код
11010001
100101
--------
100010
100101
------------
      1111

В чем ошибка ?

0xB1 = 10110001, а у Вас делимое: 0xD1 = 11010001
Костян
QUOTE (blackfin @ Sep 7 2012, 10:19) *
0xB1 = 10110001, а у Вас делимое: 0xD1 = 11010001

упс rolleyes.gif описался, 0xD1 конечно. но в делении столбиком и ответ в онлайн калькуляторе я записал для 0xD1.
blackfin
Цитата(Костян @ Sep 7 2012, 16:23) *
упс rolleyes.gif описался, 0xD1 конечно. но в делении столбиком и ответ в онлайн калькуляторе я записал для 0xD1.

Вот так ещё забавнее: http://ghsi.de/CRC/index.php?Polynom=100101&Message=1
Костян
QUOTE (blackfin @ Sep 7 2012, 10:49) *
Вот так ещё забавнее: http://ghsi.de/CRC/index.php?Polynom=100101&Message=1

аппаратный вычислитель crc дает такое же значение , что и этот онлайн по выше приведенной ссылке
http://www.easics.com/webtools/crctool
:-)
Сергей Борщ
QUOTE (Костян @ Sep 7 2012, 14:59) *
В чем ошибка ?
В том, что деление полиномов и деление чисел - несколько разные операции. Деление чисел выполняется сдвигом и вычитанием, деление полиномов - сдвигом и вычитанием по модулю 2, которое идентично сложению по модулю 2 (оно же "Исключающее ИЛИ", XOR). Поэтому формула CRC = 0xD1 % (x^5+x^2+1) не верна. Это первое.
Второе: перед делением полиномов делимое сдвигается влево на кол-во разрядов делителя.
И тогда все сходится:
CODE
11010001000000
100101
--------
100010
100101
    111100
    100101
     110010
     100101
      101110
      100101
        10110
Костян
QUOTE
Поэтому формула CRC = 0xD1 % (x^5+x^2+1) не верна. Это первое.

согласен

QUOTE (Сергей Борщ @ Sep 7 2012, 11:10) *
Второе: перед делением полиномов делимое сдвигается влево на кол-во разрядов делителя.

Спасибо, разобрался beer.gif . Только сдвиг идет не на кол-во разрядов делителя, а на степень полинома, что меньше на 1 сдвиг. В Вашем делении в столбик последний 0 лишний. И этот сдвиг идет только при вычислении CRC.
Классическая схема деления полиномов не предполагает сдвига, если я все правильно понимаю.
MrYuran
На самом деле это называется умножением в поле Галуа sm.gif
А вычисляется сдвигом и сложением по модулю 2 (XOR)

Простейший "аналоговый" кодер/декодер циклических кодов - это сдвиговый регистр с обратными связями, которые "приксориваются" в разрядах, соответствующих образующему полиному.
blackfin
Цитата(MrYuran @ Sep 7 2012, 18:07) *
На самом деле это называется умножением в поле Галуа sm.gif

Что называется "умножением в поле Галуа"? Деление по модулю на простой многочлен так называется?
MrYuran
Цитата(blackfin @ Sep 7 2012, 18:16) *
Что называется "умножением в поле Галуа"? Деление по модулю на простой многочлен так называется?

В данном случае - да.
Причем, и кодирование (умножение) и декодирования (как бы деление) производится одинаково.
Костян
QUOTE (MrYuran @ Sep 7 2012, 12:07) *
На самом деле это называется умножением в поле Галуа sm.gif
А вычисляется сдвигом и сложением по модулю 2 (XOR)

не совсем. Операция нахождения CRC - есть деление на многочлен в поле Галуа. Откуда взялось умножение то ?
А при кодирование и декодировании выполняется только операция деления (при кодировании находится остаток от деления, при декодировании идет проверка, что остаток равен нулю)
MrYuran
Цитата(Костян @ Sep 7 2012, 18:38) *
не совсем. Операция нахождения CRC - есть деление на многочлен в поле Галуа. Откуда взялось умножение то ?
А при кодирование и декодировании выполняется только операция деления (при кодировании находится остаток от деления, при декодировании идет проверка, что остаток равен нулю)

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

А я попутно интересную статью нагуглил, очень может пригодиться.
Костян
QUOTE (MrYuran @ Sep 7 2012, 12:54) *
А я попутно интересную статью нагуглил, очень может пригодиться.

это обшеизвестно, что 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 Dubrovenko
А я вот хочу про онлайн-калькуляторы спросить.
Вроде же существуют различные варианты подсчёта CRC, а в в/у калькуляторах только полином меняется.
Или, при разных алгоритмах, CRC всё-равно одинаковой получается?
fontp
QUOTE (ADA007 @ Jan 5 2013, 16:00) *
В продолжение данной темы....
Может ли кто-нибудь представить здесь матиматическое решения даной задачи?
т.е. как бы это решалось в виде формулы
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, вот на него достаточно и умножить , чтобы разделить на Х. А умножение на полином - это свертка
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.