Официальный сайт студ.городка НГТУ
Программирование и БД » Определение алгоритма контрольной суммы 

#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

#2  16.09.11 22:08

Re: Определение алгоритма контрольной суммы

Fire Stream, что-то я не понял - что конкретно тебя не устраивает в существующих алгоритмах?

Offline

#3  16.09.11 22:51

Re: Определение алгоритма контрольной суммы

2^6 = 64. то есть более 64 комбинаций ты не получишь. бери более 6 символов. или не то?

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

Re: Определение алгоритма контрольной суммы

если ты пытаешься "восстановить" алгоритм нахождения контрольной суммы, то слишком мало данных. CRC - частный случай же.

Offline

#13  19.09.11 18:07

Re: Определение алгоритма контрольной суммы

Укроп написал(а):

CRC - частный случай же.

ну эт понятно, но думал что это самое вероятное...

Укроп написал(а):

если ты пытаешься "восстановить" алгоритм нахождения контрольной суммы, то слишком мало данных.

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

Похоже я все таки ошибся с CRC. прогнал все возможные полиномы со всеми возможными стартовыми и конечными данными, для 6 и 8 бит, и еще кучка фишек, расширяющих поиск. Максимум совпадений - 19 из 23, прога весь день считала, так до конца и не дошло, но там вроде не много осталось. то есть очень вероятно что это не CRC.
решил глазами посмотреть на пакет)) нашел парочку закономерностей, несколько коллизий и тд. с лавинным эффектом я ошибся. короче там что-то простое (это конечно все равно сложно)) ). думаю решение близко)

Offline

Программирование и БД » Определение алгоритма контрольной суммы 

ФутЕр:)

© Hostel Web Group, 2002-2025.   Сообщить об ошибке

Сгенерировано за 0.041 сек.
Выполнено 14 запросов.