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

Вы можете генерировать псевдослучайные числа, манипулируя битами, имитируя РЕГИСТР СМЕЩЕНИЯ ЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗИ.

Тогда возникает вопрос: «Сколько битов вы хотите смоделировать?»

В Википедии есть некоторая информация.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// This code was written for 8051 (AT89S52)
unsigned char lfsr = 231; //8 bit shift register, with the seed of 231 or '11100111b'
unsigned char input_bit, i;

void main (void) 
{
    //Setup
    P0_0 = 0; // Leave Pin 0 Port 0 floating
    uart_init(); //Initializing uart/serial communication with pc


    while (1) 
    {
        for (i = 0; i < 255; i++) 
        {
            if (P0_0 == 1) // If Pin 0.0 is HIGH
            {
                input_bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 4)) & 1;
                lfsr = (lfsr >> 1) | (input_bit << 7);
            }
        }
        printf_tiny("%u\n", lfsr); //Send the random number to PC
        soft_delay(65535); //Simple delay function
    } //end while (1) loop

}

EDIT: я обнаружил, что мой ответ может быть плохим. Подробнее о том, почему не следует использовать плавающий цифровой PIN-код: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin