Easyelectronics.ru

Электроника для всех
Текущее время: 24 апр 2018, 02:16

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



    • JLCPCB - Платы прототипов всего за 2$ c бесплатной доставкой (при первом заказе)
    • 10 PCBs за $2 для 2 слоев, $15 для 4 слойной, $74 для 6 слойной платы.
    • Крупнейший китайский производитель прототипных плат. 290000+ клиентов & 8000+ заказов в день!
    • LCSC - Крупнейший китайский онлайн магазин радиодеталей.

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

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 197
есть число которое должно быть уникальным кодом
Код:
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
Сообщения: 340
Откуда: дальнее надмосковье
32-битная хеш функция? CRC32 или FNV-1a.


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

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

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


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

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

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


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

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

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


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

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

не знаю такое


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

Зарегистрирован: 17 фев 2016, 17:31
Сообщения: 197
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
Сообщения: 340
Откуда: дальнее надмосковье
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
Сообщения: 197
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
Сообщения: 2409
Откуда: Санкт-Петербург
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
Сообщения: 197
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
Сообщения: 4681
Я так понимаю лепиться шифрование прошивки ...


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

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

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


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

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

Изображение

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


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

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

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

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


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

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


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

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

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


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

Зарегистрирован: 11 сен 2012, 11:19
Сообщения: 4681
Вот те раз ... А это 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
Сообщения: 197
dosikus_2 писал(а):

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


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

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


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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

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