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

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

8 голосов
/ 13 октября 2009

Как эффективно генерировать случайные числа в микроконтроллере? Существуют ли общие рекомендации или какой-либо конкретный быстрый метод?

Ответы [ 8 ]

11 голосов
/ 13 октября 2009

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

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

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

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

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

10 голосов
/ 03 декабря 2012

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

7 голосов
/ 13 октября 2009

Вы можете генерировать псевдослучайные числа, манипулируя битами, имитируя LINEAR FEEDBACK SHIFT REGISTER

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

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

4 голосов
/ 13 октября 2009

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

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

2 голосов
/ 13 октября 2009

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

1 голос
/ 13 октября 2009

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

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

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

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

0 голосов
/ 16 ноября 2013

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

// 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

}

РЕДАКТИРОВАТЬ: Я обнаружил, что мой ответ может быть плохим. Подробнее о том, почему не следует использовать плавающий цифровой штифт: https://electronics.stackexchange.com/questions/50476/random-number-generators-using-a-gpio-pin

0 голосов
/ 06 января 2010

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

...