Каково самое маленькое и простое семя для генератора случайных чисел?

Маленький микроконтроллер (8-разрядный Atmel) управляет рядом огней, чтобы представить световое шоу со многими фантастическими рандомизированными световыми последовательностями.

Подходящий псевдо-RNG делает свою работу красиво, но я ищу для этого хорошее семя. Семя будет необходимо, потому что, если кто-то одновременно включит несколько таких устройств, это будет не очень хорошо, если все они будут генерировать одни и те же последовательности эффектов, пока они не будут медленно дрейфовать друг от друга из-за крошечных различий в их отдельных источниках часов.

Очень хороший способ высевать псевдо-RNG, который я часто использовал, возможен в случае устройства, которое должно запускаться нажатием кнопки или переворачиванием переключателя. Как только включается Âμc, можно запустить очень быстрый таймер, и значение этого таймера запустит RNG, как только кнопка будет нажата в первый раз.

Проблема в том, что в этом случае нет кнопок. Программа должна запускаться сразу после включения устройства.

Место на печатной плате ограничено extreme (не более, чем некоторые из самых маленьких частей SMD могут поместиться), поэтому я ищу наименьшее и самое простое решение. Поэтому я исключаю причудливые решения, такие как истинное оборудование RNG, радиоприемники и т. Д.

Все, что у меня есть, - это 16-разрядный таймер-счетчик в CPU и неиспользуемый портп, имеющий доступ к АЦП.

Мое текущее решение состоит в том, чтобы просто использовать резистор (как можно более неточным), чтобы обеспечить примерно половину напряжения питания на выводе АЦП и засеять RNG с первым значением преобразования AD. Однако в настоящее время большинство резисторов 10% имеют погрешность менее 1% (было бы интересно представить себе лицо поставщика, когда я скажу им, что мы хотим, чтобы резисторы SMD наихудшего качества они могли найти), поэтому есть очень высокая вероятность несколько единиц, начинающихся с одного и того же семени.

Лучшей альтернативой было бы сделать несколько преобразований и построить значение из наименее значимых бит этих измерений. Однако раньше я использовал АЦП этого типа Âμc, и я знаю, что это очень точно. Запуск АЦП с максимально возможной скоростью может помочь здесь.

Есть ли у кого-нибудь лучшее предложение? Семя не обязательно должно быть равномерно распределено, но чем более однородным является распределение, тем лучше. 16-битное семя с абсолютно равномерным распределением было бы слишком хорошим, чтобы быть правдой, но я думаю, что достаточно половины допустимого распределения по 5 или 6 бит может быть достаточным.

39 голосов | спросил vsz 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 19:21:55 +0300 2015, 19:21:55

10 ответов


23

Поместите параллельный резистор и конденсатор между контактом A /D и землей. Сделайте резистор довольно высоким, предпочтительно намного выше требования к импедансу входного сигнала для A /D. Сделайте постоянную времени RC, возможно, около 10 мкс. Например, 100 кО и 100 пФ звучат как хорошая комбинация.

Чтобы получить какое-то значение с некоторой случайностью, немного поднимите контактный пин, затем установите его на высокий импеданс и затем прочитайте A /D, прочитав несколько секунд. В частности, если вы должным образом злоупотребляете временем получения A /D, напряжение, которое он увидит, будет зависеть от значений R и C, тока утечки штыря, другого соседнего шума и температуры.

Возьмите младший бит или два младших бита и повторите по мере необходимости, чтобы получить любое количество случайных бит.

Для более случайного шаблона иногда выполняйте эту процедуру и вводите младший бит результата A /D в генератор случайных чисел, который вы уже используете.

ответил Olin Lathrop 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 20:15:22 +0300 2015, 20:15:22
22

Некоторые возможные варианты:

  1. Предварительно запрограммируйте уникальный последовательный адрес для каждого устройства. Если у вас есть достаточно хороший алгоритм RNG, тогда даже последовательный список последовательных адресов будет давать совершенно разные результаты.

  2. В зависимости от вашего MCU /setup у вас могут быть два разных источника синхронизации для системных часов и вход счетчика таймера /таймера. Если один из них имеет значительную дисперсию, вы можете использовать это для создания подходящего семени. Вот пример, который я написал, который использует внутренний сторожевой таймер Arduino и внешние системные часы XTAL .

  3. Используйте транзистор BJT и создавайте сильно бета-зависимый усилитель. Это можно прочитать из АЦП для семени.

  4. Конденсаторы /индукторы обычно указываются на гораздо худший уровень сопротивления, чем резисторы. Вы можете создать какую-то схему фильтра (RC, RL, LC) с этими параметрами и измерить выход с помощью АЦП.

ответил helloworld922 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 20:00:08 +0300 2015, 20:00:08
8

Неинициализированная память

Вы можете попытаться использовать неинициализированную память в микроконтроллере. Трюк состоит в том, чтобы найти биты, которые имеют самые «сбалансированные» триггеры, и на самом деле случайны. Процедура состоит в том, чтобы прочитать всю память, сбросить и повторить несколько раз, чтобы измерить, какие биты действительно случайны. Затем вы используете эту карту для считывания достаточно случайных бит, чтобы засеять ваш PRNG или LFSR!

Этот метод должен давать вам случайные семена, даже с идентичным оборудованием, более подробная информация (и ссылки) доступна в этом hack-a-day статья

Мне нравится этот метод, потому что он не требует каких-либо дополнительных схем или контактов; ваш AVR уже имеет ram, вам просто нужно найти нестабильные (случайные) биты. Также может быть автоматизирована процедура сопоставления; вы можете применить один и тот же код и процедуру к каждому устройству и получить действительно случайные результаты!

ответил esoterik 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 03 Sep 2015 01:19:32 +0300 2015, 01:19:32
7

То, что я сделал для MP3-плеера со случайными возможностями, - это просто использовать разные последовательные семена при каждом включении. Я начал с 1 и сохранил это в EEPROM, чтобы на следующем силовом цикле я использовал 2 и т. Д. Это было на ATMEGA168. Как заметил helloworld922, даже простое последовательное семя генерирует совершенно разные псевдослучайные последовательности.

Я использовал одну из линейных конгруэнтных генераторов случайных последовательностей, что дает равномерное распределение.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Конечно, если вы хотите, чтобы несколько блоков имели разные последовательности, даже если они, возможно, имели одинаковое количество циклов мощности, вам нужно что-то начать в случайном порядке.

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

Есть ли кнопки на устройстве для выбора режима и т. д.? Если это так, вы можете пробовать счетчик в первый раз, когда кнопка будет нажата после того, как MCU запрограммирован, вы можете сначала создать случайное семя и сохранить его в EEPROM. Каждое включение после этой точки будет использовать сохраненное семя.

ответил Kevin White 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 23:04:36 +0300 2015, 23:04:36
5

АЦП является очень хорошим источником случайности.

Вам не нужно полагаться на допуски резисторов. Любой резистор будет генерировать тепловой шум , и тот же физический эффект вызовет шум в АЦП при выполнении всех этапов выборки и преобразования. (Техническое описание сообщит вам о количестве шума и о том, какие настройки конфигурации хуже /лучше.)

Вы не должны оставлять плавающий АЦП; это может позволить напряжению плавать слишком далеко и рискует насытить вход.
(Многие микроконтроллеры позволяют вам использовать что-то наподобие половины напряжения питания в качестве входа АЦП для калибровки, что экономит внешний резистор и все еще дает вам шум. Опять же, см. Техническое описание для наихудшей /лучшей конфигурации.)

Вам не нужно полагаться на одно измерение АЦП; вы можете комбинировать несколько измерений с простой функцией хэша или контрольной суммы (CRC хватит). Если вам нужно немедленно начать использовать RNG, вы можете позже объединить результат АЦП с текущим семенем RNG.

ответил CL. 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 19:59:31 +0300 2015, 19:59:31
2

Можете ли вы сохранить семя от сеанса к сеансу? Если это так, можно ли включить каждую единицу в течение некоторого случайного периода времени при создании? Таким образом, все устройства будут поставляться с предустановленными семенами, которые вряд ли будут одинаковыми.

Другая мысль: как вы связываете несколько единиц вместе, чтобы они включались одновременно? Если они последовательно, добавьте какой-то конденсатор, чтобы (n + 1) -е устройство запускало несколько тактов после n-го устройства. В идеальном случае конденсаторы будут разряжаться очень быстро при выключении устройства, поэтому при каждом запуске /перезапуске происходит больший зазор между последовательностями.

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

Вариант этого заключается в добавлении дисперсии к вашим сигналам часов, если это возможно. Разница в тактовой частоте 0,1% может незначительно повлиять на световое шоу, но при изменении скорости вы быстро перемещаете таблицу PRNG.

ответил MichaelS 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 03 Sep 2015 08:39:30 +0300 2015, 08:39:30
2

Если вы работаете с внутренним «откалиброванным» источником синхронизации. Не могли бы вы сохранить семя через некоторое время, предпочтительнее в EEPROM. Часы будут дрейфовать, и они будут отличаться от единицы к единице. Чтобы сохранить новое значение через некоторое время (возможно, каждые 10 минут или около того, или через некоторое время, достаточное для обычного времени включения устройства). Чем дольше устройство включено, тем вероятнее будет сэкономить «другое» значение в EEPROM.

Также выполняйте скачок один раз каждый раз (а не часто) и повторяйтесь во время включения устройства (сохраните это новое значение в EEPROM).

ответил Mats 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 03 Sep 2015 10:09:28 +0300 2015, 10:09:28
2

Как насчет расширения оригинальной идеи преобразования AD на основе переменного резистора, добавив LDR или термистор? (Первое должно было бы «смотреть» снаружи, я не знаю, возможно ли это, но изменение света может быть выше, чем изменение температуры среди устройств, запущенных примерно в одно и то же время примерно в одном и том же месте. ..)

ответил Hagen von Eitzen 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 05 Sep 2015 19:53:03 +0300 2015, 19:53:03
1

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

  1. Если вы запустите свои устройства по одному на заводе, шестнадцатеричный файл может быть программно модифицирован некоторым промежуточным скриптом в программиста. Если он управляется ПК, вы можете перезаписать инициализацию переменной с датой и временем. Гарантируется быть уникальным для каждого устройства!

  2. Далласские 1-проводные устройства используют только один вывод, каждый из которых имеет уникальный 64-разрядный серийный номер. Вы можете использовать это как семя.

ответил Loganf 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 23:24:35 +0300 2015, 23:24:35
1

Вы можете оставить плавающий контакт ADC для подачи генератора случайных чисел (RNG) с захваченным шумом. Этого должно быть достаточно, чтобы генерировать семя или даже использовать его в качестве генератора RNG.

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

Другим решением может быть генератор шума , примененный к выходу ADC.

ответил jnk0le 2 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 02 Sep 2015 19:35:20 +0300 2015, 19:35:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132