#1 16.09.11 21:32
Определение алгоритма контрольной суммы
имеется пакет из 49 бит. первые 2 (1 точно) бита постоянны, в конце 6 бит контрольной суммы.
задача определить алгоритм подсчета этой контрольной суммы.
примеры пакетов:
Код::
1001100000111111110000010010101010010001000 000010 1001011010111111110000001010100011110001000 010001 1001100000111111110000001100000010010001000 110100
по идее можно получить очень много таких последовательностей (с известной контрольной суммой)
перепробовал все варианты CRC6, пытался инвертировать, переворачивать результат и исходные данные, начинать подсчет не с самого начала, забивать последнии 6 бит нулями или еденицами и от этого считать... в общем безрезультатно((
используется это в ИК управлении.
есть ли какиенить алгоритмы получения формулы из большого количества примеров?
Исправлено Fire Stream (16.09.11 21:33)
Offline
#4 16.09.11 22:52
Re: Определение алгоритма контрольной суммы
эмм... мне надо определить используемый алгоритм, не я его выбираю, он уже есть.
у меня есть устройство управляемое с помощью ИК пульта, я хочу с компа посылать команды, для этого мне надо уметь считать контрольную сумму, а то устройство меня не поймет.
Offline
#5 16.09.11 23:05
Re: Определение алгоритма контрольной суммы
еще похоже это алгоритм обладает лавинным эффектом, так как при изменении пары бит контрольная сумма значительно меняется.
вот думаю прогнать парочку вариантов CRC8, в них вырезать 6 бит с конца или с начала...
Исправлено Fire Stream (16.09.11 23:06)
Offline
#6 16.09.11 23:18
Re: Определение алгоритма контрольной суммы
А что за интерфейс общения? Почему 6-bit формат?
Устройство инфракрасного интерфейса подразделяется на два основных блока: преобразователь (модули приемника-детектора и диода с управляющей электроникой) и кодер-декодер. Блоки обмениваются данными по электрическому интерфейсу, в котором в том же виде транслируются через оптическое соединение, за исключением того, что здесь они пакуются в кадры простого формата – данные передаются 10bit символами, с 8bit данных, одним старт-битом в начале и одним стоп-битом в конце данных.
Сам порт IrDA основан на архитектуре коммуникационного СОМ-порта ПК, который использует универсальный асинхронный приемо-передатчик UART (Universal Asynchronous Receiver Transmitter) и работает со скоростью передачи данных 2400–115200 bps.
Источник
Если все же стандартные 8-bit, то задачу можно быстро решить методом подбора.
Пишешь цикл инкремента для полинома начиная с нуля заканчивая 0хFF (задачу можно сузить если почитать вики на стандартные протоколы и стандартные полиномы), внутри цикла стандартными XOR операциями прогоняешь весь пакет данных совместно с контрольной суммой и тот полином, который даст тебе в конце нули будет твоим ответом. Надо будет только еще с начальным значением повозиться, но тут обычно либо 0х00 либо 0хFF
Offline
#7 16.09.11 23:52
Re: Определение алгоритма контрольной суммы
интерфейс китайский) это не irda, думаю он даже не лицензирован. и все таки 6 бит.
ну да, я так и поступлю, загоню все полиномы для 8 бит в цикл (все полиномы для 6 бит уже прогнал...) но тут не факт что CRC, вообще фиг знает, что тут китайцы намудрили... конечно наиболее вероятно что CRC, но не факт... например такую как тут кодировку нулей и единиц в пакете я не встречал, роясь в инете. (имею ввиду представления двоичного числа сигналом)
Исправлено Fire Stream (16.09.11 23:57)
Offline
#8 17.09.11 00:07
Re: Определение алгоритма контрольной суммы
в алгоритме CRC не так много ручек за которые можно покрутить. К вариациям с начальным значением и полиномом можно добавить разве что либо сдвиг влево либо вправо после исключающего или.
И если 6-битный формат то может там еще есть и бит четности и даже больше, 1.5ный стоповый бит))))
(при всем уважении к китайским разработчикам)
Исправлено [D}|{]-a-z-Z (17.09.11 00:08)
Offline
#9 17.09.11 00:17
Re: Определение алгоритма контрольной суммы
чет еще возникают подозрения что я CRC неправильно реализовал((
Offline
#10 17.09.11 00:30
Re: Определение алгоритма контрольной суммы
Код::
byte calcCRC(byte[] str, int size)
{
byte i, j;
byte crc = 'начальное значение';
for(j=0;j<size;j++)
{
crc ^= str[j];
for(i=8;i>0;i--) //тут наверно 6 надо поставить и можно
//попробывать с нуля до 6 считать с i++
{
if((crc & 0x01) != 0)
{
crc >>= 1; //вот тут можно попробовать влево
crc ^= 'полином';
}
else
crc >>= 1; //ну и тут соответственно
}
}
return crc;
}Ну и все же я бы посоветовал с осциллографом посмотреть что на выходе UART`a, при 6-битном формате сложно получить 49 бит.
Исправлено [D}|{]-a-z-Z (17.09.11 00:31)
Offline
#11 17.09.11 07:58
Re: Определение алгоритма контрольной суммы
это не UART.
там 2 блока по 8 бит, а остальные по 6 бит, и еще типа стартбитов - 3 штуки.
собственно с помощью ик приемника я и разбирал сигнал, по сути почти осциллограф.
в приведенном варианте меня смущает представление массивом байтов, у меня то биты, то есть надо переделать алгоритм, а при этом могу какнить неправильно сделать)
Offline
#12 17.09.11 16:34
#13 19.09.11 18:07
Re: Определение алгоритма контрольной суммы
Укроп написал(а):
CRC - частный случай же.
ну эт понятно, но думал что это самое вероятное...
Укроп написал(а):
если ты пытаешься "восстановить" алгоритм нахождения контрольной суммы, то слишком мало данных.
ну я пытаюсь угадать его, по некоторым оценкам можно очень сузить количество вариантов (правда их все равно бесконечность).
Похоже я все таки ошибся с CRC. прогнал все возможные полиномы со всеми возможными стартовыми и конечными данными, для 6 и 8 бит, и еще кучка фишек, расширяющих поиск. Максимум совпадений - 19 из 23, прога весь день считала, так до конца и не дошло, но там вроде не много осталось. то есть очень вероятно что это не CRC.
решил глазами посмотреть на пакет)) нашел парочку закономерностей, несколько коллизий и тд. с лавинным эффектом я ошибся. короче там что-то простое (это конечно все равно сложно)) ). думаю решение близко)
Offline

