Вообще, аппаратная реализация стандартного алгоритма CRC-16 выглядит несложной - кроме сдвигового регистра CRC там надо только 4 логических элемента.Сообщение от Vslav
Вообще, аппаратная реализация стандартного алгоритма CRC-16 выглядит несложной - кроме сдвигового регистра CRC там надо только 4 логических элемента.
Все, привел я к обычному делению на полином. Нужно просто было понять что же реально делится и подавать фактическую последовательность делимого:
где - crc16_m2() - обычное деление на полином, с вдвиганием бита данных в младший разряд. Контрольные суммы совпадают, все выкладки полностью подтвердились.Код:crc = 0; crc = crc16_m2(crc, 0xA1 ^ 0xFF); crc = crc16_m2(crc, 0xA1 ^ 0xFF); crc = crc16_m2(crc, 0x30); crc = crc16_m2(crc, 0x31); crc = crc16_m2(crc, 0x32); crc = crc16_m2(crc, 0x33); crc = crc16_m2(crc, 0x00); crc = crc16_m2(crc, 0x00);
А как выглядит на C исходный код функции crc16_m2() ?
Последний раз редактировалось Patron; 15.12.2013 в 11:42.
Код:unsigned short int crc16_m2(unsigned short crc, unsigned char data) { int i; printf("\n %02X ( %04X,", data, crc); for(i=0; i<8; i++) { if (crc & 0x8000) { crc <<= 1; crc |= (data >> 7) & 1; crc ^= 0x1021; } else { crc <<= 1; crc |= (data >> 7) & 1; } data <<= 1; } printf(" %04X )", crc ); return crc; }
Насколько я понимаю - деление бита на полином 16 степени требует сдвигания бита на 16 разрядов влево.
Из-за этого, для получения правильного результата деления всех добавленных справа битов - после обрабатываемой последовательности битов приходится пропускать через обработчик ещё 16 "проталкивающих" нулевых битов:
В результате - все добавленные в регистр CRC биты данных делятся на полином именно там, где и должны - в 17-ом бите CRC.Код:crc = crc16_m2(crc, 0x00); crc = crc16_m2(crc, 0x00);
Последний раз редактировалось Patron; 15.12.2013 в 13:53.
Есть два отдельных понятия - операция полиномиальной арифметики "нахождение остатка при делении на полином" и набор действий называемый "алгоритм CRC". Это разные вещи, относящиеся к разным категориям. Часто просто говорят - "CRC это нахождение остатка от деления на полином" и при этом не вдаются в подробности. И мало кто в подробности вникает, незачем - в Сети полно программных и аппаратных реализаций на любой вкус.
Операция деления на полином - можно показать как простое деление в столбик. Выполняется точно так же как школьная операция деления десятичных чисел в столбик, только с двоичными цифрами и операции сложения/вычитания реализованы как XOR. В том же руководстве Виллиамсa по CRC есть банальный пример как оно выполняется (правда там пририсовали нули в конце сообщения, поэтому вероятно народ заблуждается насчет операции деления).
Алгоритм CRC - находит остаток именно при помощи этой операций деления и никакой другой. Вопрос только в том что делится. Алгоритму CRC-16 надо чтобы на проверяющем конце в итоге получился 0 (или другая константа). Поэтому сообщение умножают на 0x10000 и вычитают из него вычисленную на передающем конце сумму - в нашем случае это выглядит просто как два добавленных байта суммы в конце. Математическое обоснование почему надо умножать и вычитать я писал выше - это свойство остатков. Умножить же сообщение на 0x10000 можно либо добавлением двух нулевых байтов, либо встроить это умножение в саму процедуру деления, что и сделано в ВП1-128 - в ней вдвигание по факту производится в виртуальный 16-ый бит.
Таким образом утверждение "деление бита на полином 16 степени требует сдвигания бита на 16 разрядов влево" неверно, потому что сдвигания требует оптмизированный алгоритм вычисления CRC, а не собственно операция деления.
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Даже если не требовать "проверочного нуля" ( или другой константы ) - алгоритм функции crc16_m2 даёт корректный результат только при умножении входного сообщения на 0x10000. Иначе CRC вообще не вычисляется.
Чтобы коректно вычислять CRC без умножения входного сообщения на 0x10000 - нужен совсем другой алгоритм.
---------- Post added at 14:23 ---------- Previous post was at 14:13 ----------
Корректный алгоритм вычисления CRC должен для сообщения из одного бита "1" давать результат 0x1021.
Функция crc16_m2 даст такой результат только для сообщения "10000000000000000", т.е. для бита "1", умноженного на 0x10000.
Моя функция crc16_m2() - это НЕ алгоритм CRC. Это итеративная функция полиномиального деления, как оно понимается в математике. Она умножает аргумент crc на 0x100, добавляет data и находит остаток от деления на полином 0x11021. Чтобы получить результат алгоритма CRC для одного бита надо эту функцию вызвать трижды - добавить еще два нулевых байта.
И моей задачей было именно показать как алгоритм CRC базируется на канонической операции деления.
---------- Post added at 13:54 ---------- Previous post was at 13:49 ----------
Правильно, только умножение на 0x10000 это есть этап алгоритма CRC, а НЕ свойство собственно функции полиномиального деления. Я выделил чистую операцию деления и показал как алгоритм CRC его использует. Без всяких вводящих в заблуждение оптимизаций.
Последний раз редактировалось Vslav; 15.12.2013 в 15:52.
Но нужен остаток от деления именно бита данных на полином, а не остаток от деления 17-го бита CRC на полином.
Какой смысл делить 17-й бит CRC на полином, если деление бита данных на полином при этом не происходит и приходится дополнительно вызывать функцию 16 раз, чтобы бит данных наконец поделился на полином и сформировал остаток..
---------- Post added at 15:33 ---------- Previous post was at 14:58 ----------
Насколько я понимаю, функция crc16_m2 - это не итеративная функция полиномиального деления CRC, а функция полиномиального деления 17-го бита CRC для каждого бита данных:
Когда в 17-м бите CRC находится текущий бит данных - это именно то, что надо, но когда текущий бит данных находится на 16 битов правее - функция даёт корректный результат только после 17-го вызова, с задержкой выдачи результата для текущего бита данных на 16 вызовов. Т.е. чтобы учесть корректный результат полиномиального деления для последнего бита данных - после передачи в функцию последнего бита данных нужно вызвать функцию crc16_m2 ещё 16 раз.Код:unsigned short int crc16_m2(unsigned short crc, unsigned char data) { int i; printf("\n %02X ( %04X,", data, crc); for(i=0; i<8; i++) // для каждого бита данных { // выполнить деление 17-го бита CRC на полином 0x11021 if (crc & 0x8000) { crc <<= 1; crc |= (data >> 7) & 1; crc ^= 0x1021; } else { crc <<= 1; crc |= (data >> 7) & 1; } data <<= 1; } printf(" %04X )", crc ); return crc; }
Последний раз редактировалось Patron; 15.12.2013 в 16:42.
Делится не CRC. Аргумент crc содержит остаток от деления предыдущих битов сообщения, функция-то итеративная. А додвигание - это и есть умножение, требуемое алгоритмом CRC.
Еще раз, суть алгоритма CRC (хотя уже писал в этой ветке).
У нас есть некоторое число m - сообщение (передаваемый блок полезных данных). Есть некоторая константа p. Есть некоторая операция mod. В-общем случае это может быть необязательно операция нахождения остатка от полиномиального деления, а например остаток от обычного, с переносом (эх, давно я в теорию групп не заглядывал, щаз бы поумничал "кольцом вычетов")
Допустим мы вычисляем значение:
r = m mod p
Если мы найдем значение:
r`= (m - r) mod p,
то это r' будет нулевым потому что:
(m - r) mod p = (m mod p - r mod p) mod p
m mod p = r
r mod p = r
r`= r - r = 0.
На практике такая реализация не очень удобна - при проверке надо хранить m и r, потом вычислять их разность (особенно сложно если арифметика с переносом а не полиномиальная).
Поэтому алгоритмы CRC вычисляют mod не от самого m а умножают его дополнительно на разрядность остатка (назовем s):
crc = (m*s) mod p.
И при отправке данных тупо добавляют после самого m вычисленный crc. Конкатенированная последовательность m | crc эквивалентна значению m*s - crc, поэтому когда мы выполним:
(m*s - crc) mod p,
то это и будет итоговый остаток, который как я выше показал нулевой. Умножение на s - это просто фишка алгоритма CRC, чтобы была более удобна практическая реализация, никакой математики в этом нет.
функция crc16_m2() - это и есть итерация чистой операции mod. Все Ваши функции - просто одновременно c делением умножают аргумент на s.
Последний раз редактировалось Vslav; 15.12.2013 в 16:59.
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)
Ваши права
Ответить с цитированием
