Как я генерирую случайные числа в микроконтроллере эффективно?

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

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

Типичным алгоритмом генератора случайных чисел общего назначения является Mersenne Twister . Существует множество публичных реализаций различных алгоритмов. См. Здесь для одного.

Если MT требует слишком много памяти, более подходящим вариантом является линейный конгруэнтный генератор . (MT не был изобретен до 1997 года.) Этот генератор имеет определенные проблемы, но он почти не требует памяти, почти не требует кода и очень быстр. Реализации есть везде, и это подробно описано в Seminumerical Algorithms Кнута.

Чтобы заполнить любой ГСЧ, вам понадобится источник энтропии, см. http://en.wikipedia.org/wiki/Entropy_ (вычисления) (Примечание: SO путается с () ' s в этой ссылке.) Обычно это происходит из временных событий, которые ЦП может наблюдать, таких как нажатия клавиш, (я полагаю, это не сработает для вас) прерывания и прибытия пакетов. Часы реального времени часто являются приемлемым источником, если они поддерживают свое собственное состояние, поскольку перезагрузки редко выполняются в какой-либо последовательности.

Если у вас есть доступ к АЦП, вы можете прочитать из него самый младший бит и использовать его в качестве начального числа для генератора псевдослучайных чисел, как и другие. Очевидно, вам нужно будет прочитать более одного бита с АЦП, поэтому потребуется несколько операций чтения, что может занять некоторое время. Но вам нужно сделать это только один раз, например, при запуске, а затем использовать более быстрый PRNG для генерации новых случайных чисел.

Многие встроенные устройства имеют встроенный АЦП, например семейство ATMega от Atmel.

Генераторы псевдослучайных чисел, которые являются наиболее быстрыми и наименее требовательными по отношению к набору команд (только сдвиг и xor, без умножения или деления), представляют собой меньшие варианты идеи твистера Мерсенна (так называемый сдвиг с обобщенной линейной обратной связью). регистр). Самому Mersenne Twister требуется слишком много памяти для микроконтроллеров.

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

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

Я однажды разработал такой генератор для небольшого нестандартного процессора с пространством состояний примерно 50 24-битных слов. Я тестировал варианты с помощью набора тестов Diehard, пока не нашел хороший. Приложение генерировало случайные варианты для аппаратного тестирования.

Если на оборудовании есть кнопка для пользователя, простой трюк состоит в том, чтобы подсчитать, как долго была нажата кнопка. С достаточно быстрым коротким счетчиком вы получите «случайное» число.

Чтение таймера и xoring/nanding/etc его с серией битов даст пользователю полупроизвольную величину, так как время между событиями, скорее всего, будет достаточно далеко друг от друга, чтобы пользователь действительно не смог определить корреляцию с таймером.