Easyelectronics.ru

Электроника для всех
Текущее время: 21 янв 2019, 19:14

Часовой пояс: UTC + 5 часов




Начать новую тему Ответить на тему  [ Сообщений: 19 ] 
Автор Сообщение
 Заголовок сообщения: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 18:40 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
есть число которое должно быть уникальным кодом
Код:
uint32_t code;

есть массив данных который я обрабатываю
Код:
uint32_t result;
for (int i = 0; i < BITS_COUNT; i++)
{
     result = captures[i] / WIDTH; 
     // code |= (1<<result);   ???
}

result может быть в пределах 0-4. и на основе result я хочу модифицировать code в каждой итерации.
я думал делать так
Код:
data |= (1<<result);

но если result все время 4 то на i = 8 мы вылетим за пределы uint32_t.
есть какие нибудь простые алгоритмы позволяющее создать уникальное число(ключ)?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:18 
Старожил

Зарегистрирован: 07 авг 2014, 17:15
Сообщения: 383
Откуда: дальнее надмосковье
32-битная хеш функция? CRC32 или FNV-1a.


Последний раз редактировалось arm999 03 окт 2017, 19:18, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:18 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 3087
LFSR


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:22 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:39 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
arm999 писал(а):
32-битная хеш функция? CRC32 или FNV-1a.

а как я в CRC32 увяжу result?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:40 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
_pv писал(а):
LFSR

не знаю такое


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 19:41 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
aamonster писал(а):
См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 20:13 
Старожил

Зарегистрирован: 07 авг 2014, 17:15
Сообщения: 383
Откуда: дальнее надмосковье
jenya77 писал(а):
а как я в CRC32 увяжу result?

А в чем проблема? Или может я не правильно понимаю задачу? Если нужно на каждое уникальное значение result получить другой уникальный "код" то можно и просто за-ксорить (xor) result с каким-нибудь ключем. А если нужно учесть и предыдущие значения result то можно использовать хеш функцию, вот пример использования этой библиотеки:
Код:
#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, FNV1_32A_INIT);

// в последующие разы
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, code);


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 20:38 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
arm999 писал(а):
jenya77 писал(а):
а как я в CRC32 увяжу result?

А в чем проблема? Или может я не правильно понимаю задачу? Если нужно на каждое уникальное значение result получить другой уникальный "код" то можно и просто за-ксорить (xor) result с каким-нибудь ключем. А если нужно учесть и предыдущие значения result то можно использовать хеш функцию, вот пример использования этой библиотеки:
Код:
#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, FNV1_32A_INIT);

// в последующие разы
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, code);

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 03 окт 2017, 22:00 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
jenya77 писал(а):
aamonster писал(а):
См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3

Потому что у вас 5 разных значений. Вашу последовательность result'ов можно рассматривать, как число в 5-ричной системе (цифры от 0 до 4), просто переводим в число...
Для 20 итераций для гарантированной уникальности надо 47 бит, меньше - есть какая-то вероятность коллизий.
(А ещё благодаря тому, что 5 взаимно простое с 2 - пришедшие в число цифры при переполнении 32-битного числа не будут потеряны, а "размажутся" по всему числу).

1 3 1 3 ==> 1*5^3 + 3*5^2 + 1*5 + 3 = 208
3 1 3 1 ==> 3*5^3 + 1*5^2 + 3*5 + 1 = 416
Числа разные.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 10:14 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
aamonster писал(а):
jenya77 писал(а):
aamonster писал(а):
См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3

Потому что у вас 5 разных значений. Вашу последовательность result'ов можно рассматривать, как число в 5-ричной системе (цифры от 0 до 4), просто переводим в число...
Для 20 итераций для гарантированной уникальности надо 47 бит, меньше - есть какая-то вероятность коллизий.
(А ещё благодаря тому, что 5 взаимно простое с 2 - пришедшие в число цифры при переполнении 32-битного числа не будут потеряны, а "размажутся" по всему числу).

1 3 1 3 ==> 1*5^3 + 3*5^2 + 1*5 + 3 = 208
3 1 3 1 ==> 3*5^3 + 1*5^2 + 3*5 + 1 = 416
Числа разные.

понял. спасибо.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 10:58 
Старожил

Зарегистрирован: 11 сен 2012, 11:19
Сообщения: 5304
Я так понимаю лепиться шифрование прошивки ...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 11:28 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
dosikus_2 писал(а):
Я так понимаю лепиться шифрование прошивки ...

нет. расшифровка протокола RC5. таймер считает каждое падение фронта. полученные значения делю на ширину пульса и создаю уникальный код на основе результата. с учетом веса бита уникальность должна быть соблюдена по идее. по крайней мере на бумаге работает. достаточно что где то есть переход 0-1 или 1-0 и получается уникальный паттерн.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 11:41 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2546
Откуда: Санкт-Петербург
Простите, не могу удержаться...

Изображение

RC5 - это же манчестерское кодирование, которое расшифровывается просто, дёшево и без таких сложностей... И на выходе сразу 12-битное число, а не 20 интервалов от 0 до 4, которое ещё надо преобразовывать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 12:00 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
aamonster писал(а):
Простите, не могу удержаться...

RC5 - это же манчестерское кодирование, которое расшифровывается просто, дёшево и без таких сложностей... И на выходе сразу 12-битное число, а не 20 интервалов от 0 до 4, которое ещё надо преобразовывать.

ну самый простой вариант считать на таймере интервалы. не заморачиваясь отслеживанием переходов 1-0 0-1. ну потом надо придать уникальность полученному результату.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 12:07 
Старожил

Зарегистрирован: 11 сен 2012, 11:19
Сообщения: 5304
jenya77, а пробежаться поиском? НА стм32 здесь уже было аппаратное...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 12:38 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
dosikus_2 писал(а):
jenya77, а пробежаться поиском? НА стм32 здесь уже было аппаратное...

поиск меня не удовлетворил. у ST есть пример реализации декодирования RC5. но там такая простыня, я просто не понимаю как они умудрились сделать такого слона из RC5.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 13:02 
Старожил

Зарегистрирован: 11 сен 2012, 11:19
Сообщения: 5304
Вот те раз ... А это http://ziblog.ru/2013/05/14/distantsion ... pulta.html
http://ziblog.ru/2011/07/31/rabotaem-s-ik-pultom.html

http://we.easyelectronics.ru/ZiB/rabota ... ultom.html


Последний раз редактировалось dosikus_2 04 окт 2017, 13:09, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Создать уникальное число из результата вычислений.
СообщениеДобавлено: 04 окт 2017, 13:08 
Старожил

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 216
dosikus_2 писал(а):

о! спасибо! это интересное решение.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ] 

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: woroba


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB