Эмуляция 1801ВП1-128 в ПЛИС

[Patron]

А перед сдвигом достаточно проверить 15-й бит, поэтому старший 16-й бит регистра обычно не реализовывают ни в софте, ни в железе.

Вообще, аппаратная реализация стандартного алгоритма CRC-16 выглядит несложной - кроме сдвигового регистра CRC там надо только 4 логических элемента.

[Vslav]

Все, привел я к обычному делению на полином. Нужно просто было понять что же реально делится и подавать фактическую последовательность делимого:

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);

где - crc16_m2() - обычное деление на полином, с вдвиганием бита данных в младший разряд. Контрольные суммы совпадают, все выкладки полностью подтвердились.

[Patron]

где - crc16_m2() - обычное деление на полином, с вдвиганием бита данных в младший разряд

А как выглядит на C исходный код функции crc16_m2() ?

[Vslav]

А как выглядит на C исходный код функции crc16_m2() ?

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;
}

[Patron]

crc16_m2() - обычное деление на полином, с вдвиганием бита данных в младший разряд

Насколько я понимаю - деление бита на полином 16 степени требует сдвигания бита на 16 разрядов влево.

Из-за этого, для получения правильного результата деления всех добавленных справа битов - после обрабатываемой последовательности битов приходится пропускать через обработчик ещё 16 "проталкивающих" нулевых битов:

crc = crc16_m2(crc, 0x00);
crc = crc16_m2(crc, 0x00);

В результате - все добавленные в регистр CRC биты данных делятся на полином именно там, где и должны - в 17-ом бите CRC.

[Vslav]

Насколько я понимаю - деление бита на полином 16 степени требует сдвигания бита на 16 разрядов влево.

Есть два отдельных понятия - операция полиномиальной арифметики "нахождение остатка при делении на полином" и набор действий называемый "алгоритм CRC". Это разные вещи, относящиеся к разным категориям. Часто просто говорят - "CRC это нахождение остатка от деления на полином" и при этом не вдаются в подробности. И мало кто в подробности вникает, незачем - в Сети полно программных и аппаратных реализаций на любой вкус.

Операция деления на полином - можно показать как простое деление в столбик. Выполняется точно так же как школьная операция деления десятичных чисел в столбик, только с двоичными цифрами и операции сложения/вычитания реализованы как XOR. В том же руководстве Виллиамсa по CRC есть банальный пример как оно выполняется (правда там пририсовали нули в конце сообщения, поэтому вероятно народ заблуждается насчет операции деления).

Алгоритм CRC - находит остаток именно при помощи этой операций деления и никакой другой. Вопрос только в том что делится. Алгоритму CRC-16 надо чтобы на проверяющем конце в итоге получился 0 (или другая константа). Поэтому сообщение умножают на 0x10000 и вычитают из него вычисленную на передающем конце сумму - в нашем случае это выглядит просто как два добавленных байта суммы в конце. Математическое обоснование почему надо умножать и вычитать я писал выше - это свойство остатков. Умножить же сообщение на 0x10000 можно либо добавлением двух нулевых байтов, либо встроить это умножение в саму процедуру деления, что и сделано в ВП1-128 - в ней вдвигание по факту производится в виртуальный 16-ый бит.

Таким образом утверждение "деление бита на полином 16 степени требует сдвигания бита на 16 разрядов влево" неверно, потому что сдвигания требует оптмизированный алгоритм вычисления CRC, а не собственно операция деления.

[Advertiser]

[Patron]

Алгоритму CRC-16 надо чтобы на проверяющем конце в итоге получился 0 (или другая константа). Поэтому сообщение умножают на 0x10000 и вычитают из него вычисленную на передающем конце сумму - в нашем случае это выглядит просто как два добавленных байта суммы в конце.

Даже если не требовать "проверочного нуля" ( или другой константы ) - алгоритм функции 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.

[Vslav]

Функция 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 ----------

Функция crc16_m2 даст такой результат только для сообщения "10000000000000000", т.е. для бита "1", умноженного на 0x10000.

Правильно, только умножение на 0x10000 это есть этап алгоритма CRC, а НЕ свойство собственно функции полиномиального деления. Я выделил чистую операцию деления и показал как алгоритм CRC его использует. Без всяких вводящих в заблуждение оптимизаций.

[Patron]

Моя функция crc16_m2() - это НЕ алгоритм CRC. Это итеративная функция полиномиального деления, как оно понимается в математике. Она умножает аргумент crc на 0x100, добавляет data и находит остаток от деления на полином 0x11021.

Но нужен остаток от деления именно бита данных на полином, а не остаток от деления 17-го бита CRC на полином.

Какой смысл делить 17-й бит CRC на полином, если деление бита данных на полином при этом не происходит и приходится дополнительно вызывать функцию 16 раз, чтобы бит данных наконец поделился на полином и сформировал остаток..

---------- Post added at 15:33 ---------- Previous post was at 14:58 ----------

Насколько я понимаю, функция crc16_m2 - это не итеративная функция полиномиального деления CRC, а функция полиномиального деления 17-го бита CRC для каждого бита данных:

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;
}

Когда в 17-м бите CRC находится текущий бит данных - это именно то, что надо, но когда текущий бит данных находится на 16 битов правее - функция даёт корректный результат только после 17-го вызова, с задержкой выдачи результата для текущего бита данных на 16 вызовов. Т.е. чтобы учесть корректный результат полиномиального деления для последнего бита данных - после передачи в функцию последнего бита данных нужно вызвать функцию crc16_m2 ещё 16 раз.

[Vslav]

Какой смысл делить CRC на полином, если деление бита данных на полином при этом не происходит и приходится дополнительно вызывать функцию 16 раз, чтобы бит данных наконец поделился на полином и сформировал остаток..

Делится не 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.