Функция случайных чисел ардуино. Курс Arduino - Время и Random. Регистр сдвига с линейной обратной связью

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

Для активации этого генератора достаточно использовать функции random() или randomSeed(). В данном материале будет показано, как работать с этими функциями, а также как избавиться от псевдослучайности при генерировании чисел.

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

Итак, функция random для генерирования псевдослучайных чисел может иметь до двух параметров и записываться как random(max) или random(min, max). Здесь параметр max, который является обязательным, задает верхнюю границу диапазона генерации псевдослучайных чисел. С помощью дополнительного параметра min можно задать нижнюю границу диапазона. В итоге функция вернет какое-то псевдослучайное число в промежутке от min до max-1.

Важно понимать, что при использовании функции random() каждый раз будет сгенерирован точно такой же список псевдо случайных чисел. Например, если вы сделаете игровой автомат, и при первом нажатии рукоятки выпадет выигрышная комбинация, то вы можете быть уверены, что если перезагрузите Arduino и нажмете на рукоятку еще раз, этот игровой автомат покажет такую же выигрышную комбинацию. Действительно, на Arduino не просто реализовать игровой аппарат с полностью случайной генерацией чисел, как это, например, реализовано в игровых аппаратах www.igrovye-apparati-vulcan.com/ , но можно частично решить проблему с помощью функции randomSeed().

Эта функция принимает значение (например, целочисленное), и использует число, чтобы изменить случайный список, генерируемый функцией random().Вы можете поместить randomSeed() в функцию настройки setup, а в бесконечном цикле loop использовать функцию random(). Но и в этом случае будет загвоздка, заключающаяся в том, что хотя последовательность случайных чисел будет отличаться при использовании функции randomSeed(),она все равно будет такой же каждый раз, когда будет запускаться скетч.

Единственным решением в таком случае может быть вариант с применением аналоговой периферии (АЦП) и соответствующей функции analogRead(). Если аналоговый ввод ни к чему не подключать, то есть оставить его «висеть» в воздухе, то благодаря шуму на этой линии можно получить действительно случайные числа. Тогда в настройке setup можно записать так randomSeed(analogRead(A0)). При условии, что аналоговый порт A0 никуда не подключен.

Про генераторы случайных чисел написано очень много, но почти всегда, когда дело доходит до реализации, подразумевается (или явно говорится), что речь идет об x86/x64 и других «взрослых» архитектурах. В то же время, форумы, посвященные разработке устройств на микроконтроллерах, пестрят вопросами «как мне сгенерировать случайное число на %controllername%?». Причем диапазон ответов простирается от «смотри гугл/википедию» до «используй стандартную функцию». Далеко не всегда эта «стандартная функция» есть и устраивает разработчика по всем параметрам, чаще наоборот: то числа получаются далеки от случайных, то скорость работы слишком мала, а то полученный код вообще не помещается в свободную память.
Попробуем разобраться, какие бывают алгоритмы генерации случайных чисел, как выбрать подходящий, а главное, в чем особенности реализации этих алгоритмов на контроллерах.

Оценка «случайности»

Применения для ГСЧ могут найтись самые разные, от игрушек до серьезной криптографии. Соответственно, и требования, предъявляемые к генератору, тоже сильно варьируются. Для оценки качества (уровня «случайности») генератора существуют специальные тесты. Вот самые основные из них:

• Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно быть примерно поровну.
• Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000...0 или 111...1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
• Спектральный тест. К исходной последовательности применяется дискретное преобразование Фурье. Полученный спектр не должен иметь значительных пиков, которые говорили бы о наличии периодических свойств последовательности.
• Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.

Существуют специальные наборы, включающие в себя десятки подобных тестов:
NIST - использовался в конкурсе AES для оценки алгоритмов шифрования.
DIEHARD - один из наиболее строгих существующих наборов.

Алгоритмы ГПСЧ

Любая последовательность, сгенерированная по жестко заданному алгоритму, не может считаться истинно случайной, поэтому, ведя речь об алгоритмических генераторах, употребляют термин псевдослучайная последовательность. Любой генератор псевдослучайных чисел (ГПСЧ) рано или поздно зацикливается, другое дело в том, что это «поздно» может наступить через несколько миллисекунд, а может через несколько лет. Длина цикла зависит от размера внутреннего состояния генератора N (фактически, это объем памяти, нужный генератору), и составляет от 2 (N/2) до 2 N бит.
Алгоритмов ГПСЧ придумано огромное множество, но далеко не все они удобны для реализации на микроконтроллерах. Мы сильно ограничены в быстродействии и доступном объеме памяти, многие контроллеры не поддерживают вещественную арифметику и даже команды умножения. Помня о подобных ограничениях, рассмотрим некоторые известные алгоритмы.

Линейный конгруэнтный метод

Очередной член последовательности рассчитывается по формуле
X i+1 = (aX i + c) mod m
Число m определяет максимальный период последовательности, целые числа a и c - «магические» коэффициенты. Число m разумно выбирать равным степени двойки, в таком случае опреация приведения по модулю сводится к отбрасыванию старших битов. Для того, чтобы получить максимальный период, нужно соблюдать следующие условия:
- c и m должны быть взаимно простыми,
- a-1 должно быть кратно p для всех простых делителей p числа m ,
- если m кратно 4 (а в нашем случае оно будет кратно), то и a-1 должно быть кратно 4.
Есть еще одна тонкость: в качестве результата следует брать только старшие биты переменной состояния X, так как для младших бит статистические параметры случайности значительно хуже. Линейный конгруэнтный алгоритм обычно реализован в качестве стандартного rand() во многих библиотеках.

Плюсы:

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

Минусы:

• требуется операция умножения;
• не все биты одинаково случайны.

Резюме: быстрый и простой алгоритм для не очень ответственных применений.

Метод Фибоначчи с запаздываниями

В этом алгоритме используется соотношение
X i = X i-a - X i-b ,
где переменная состояния X - беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывания, тем больше период и лучше спектральные свойства последовательности. С другой стороны, для работы генератора требуется хранить max{a,b} предыдущих чисел, что не всегда приемлемо. Также для запуска генератора нужно max{a,b} чисел, которые обычно получают при помощи более простого ГПСЧ.

Плюсы:

• не требует операций умножения;
• все биты случайного числа равнозначны по статистическим свойствам.

Минусы:

• требует большого объема памяти;
• требует большого массива чисел для запуска.

Резюме: очень качественный, но ресурсоемкий алгоритм.

Регистр сдвига с линейной обратной связью

Переменная состояния хранится в регистре длины N. Генерация следующего состояния включает два шага:

1. Подсчитывается значение бита C = X i1 xor X i2 xor… X ik , где i1, i2… ik - номера битов регистра, называемые отводами .
2. Регистр сдвигается на 1 бит вправо, крайний левый бит принимает значение С .

Выходом генератора является крайний правый (или крайний левый, или любой другой) бит регистра, то есть псевдослучайная последовательность генерируется по одному биту за итерацию. При правильно выбранных номерах отводов период генератора составит 2 N - 1. «Минус один», так как существует запрещенное нулевое состояние регистра. Номера отводов для N от 3 до 168 можно посмотреть в этом документе .
Кроме описанной выше конфигурации, которая, кстати, называется конфигурацией Фибоначчи (не путать с одноименным методом ГПСЧ!), существует т.н. конфигурация Галуа.


Вместо того, чтобы использовать для генерации нового крайнего левого бита сумму битов отводной последовательности, выполняется XOR каждого бита отводной последовательности с крайним правым битом, затем выполняется циклический сдвиг всего регистра вправо. Эта схема сложнее для понимания, но проще в реализации, так как все опрерации XOR можно выполнить одновременно. По длине периода и качеству псевдослучайных чисел схемы Фибоначчи и Галуа эквивалентны.

Плюсы:

• очень простая реализация, не требуется даже арифметики, только битовые операции и сдвиги;
• очень быстрый алгоритм (особенно схема Галуа);
• хорошие статистические свойства.

Минусы:

• нужно проверять начальное значение на неравенство нулю.

Резюме: очень быстрый и довольно качественный алгоритм.

Криптостойкие алгоритмы

Для применения в криптографии к ГПСЧ предъявляется еще одно существенное требование: необратимость . Все перечисленные выше алгоритмы этим свойством не обладают: зная несколько выходных значений ГПСЧ, можно, решив несложную систему уравнений, найти параметры алгоритма (те самые «магические» константы a, b, с и т.д). А зная параметры, можно воспроизвести всю псевдослучайную последовательность.
В качестве криптографически стойкого алгоритма ГПСЧ можно использовать любой достаточно сильный блочный шифр. Выбрав секретный ключ, можно получать блоки псевдослучайных чисел, применяя алгоритм к последовательным натуральным числам. Для N-битного блочного шифра период будет не больше 2 N . Безопасность такой схемы полностью зависит от секретности ключа.
Все современные криптографические алгоритмы проходят проверку на использование в качестве ГПСЧ, то есть, используя сертифицированный алгоритм, не нужно специально заботиться о статистических и спектральных свойствах выходного потока. Переживать нужно только о вычислительной «прожорливости» криптоалгоритмов. Если требуется выполнять большое количество операций шифрования, имеет смысл выбрать контроллер с аппаратными криптографическими блоками. Часто в таких контроллерах есть и весьма неплохой криптостойкий аппаратный ГПСЧ.

Источники энтропии

Как уже было сказано, используя только детерминированные алгоритмы, невозможно сгенерировать истинно случайное число. Поэтому обычно применяется связка ГПСЧ + внешний источник энтропии . Источник энтропии используется для задания начального значения для ГПСЧ, а задача последнего сводится к обеспечению спектральной и статистической чистоты последовательности. Что же можно использовать в качестве источника энтропии? Да практически что угодно.

Активность пользователя

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

Аналого-цифровой преобразователь

Во многих контроллерах есть встроенные АЦП. И во многих контроллерах они весьма посредственного качества, сделанные просто «чтобы было». Младшие биты результата АЦП почти всегда содержат значительный шум, даже если измеряется постоянное напряжение. Это можно использовать: подключите вход АЦП к напряжению питания через делитель, проведите несколько десятков измерений, возьмите младшие биты - вот вам отличное случайное число. Если АЦП содержит встроенный предусилитель, включите его, он тоже шумит.

Асинхронные генераторы

Можно использовать разницу периодов двух несинхронизированных тактовых генераторов. Большинство контроллеров содержат, например, сторожевой таймер. Для повышения надежности он тактируется от отдельного генератора, никак не связанного с основным тактовым сигналом. Достаточно подсчитать число тактов основного тактового сигнала за один период сторожевого таймера. Если подобрать периоды так, чтобы счетчик за время измерения многократно переполнился, можно получить достаточно случайное число. Недостаток этого метода - он требует много времени, до нескольких секунд.

Часы реального времени

Если в схеме есть часы реального времени , можно использовать их текущие показания для инициализации ГПСЧ. Например, преобразовав текущие дату/время в формат Unix time , мы получим сразу 32 бита, которые никогда больше не повторятся, если только не снимать показания чаще одного раза в секунду. Использование реального времени дает уникальность значений, но не дает никакой непредсказуемости, поэтому лучше комбинировать данный способ с другими.

RC-цепь

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

Выводим на этот порт сигнал «0» - конденсатор разряжается. Переключаем порт в режим входа - конденсатор начинает заряжаться. Когда напряжение на нем достигнет порога, вход переключится из состояния «0» в «1». Время заряда сильно зависит от многих факторов: напряжаения питания, дрейфа параметров RC-цепи, нестабильности порога, температуры, утечек, помех. Измеряя его с достаточной точностью и беря младшие биты, можно получить хорошую случайность.

Аппаратный генератор шума

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

Для того, чтобы порог срабатывания компаратора не влиял на статистические свойства полученного сигнала, применяют два генератора шума, работающие на один компаратор:

Заключение

Напоследок расскажу одну историю из жизни. Началась она с очередного заданного на форуме вопроса «как мне сгенерировать случайное число на контроллере?». Автор вопроса пояснил, что делает в качестве курсового проекта устройство, эмулирующее бросание игральной кости. После нескольких безуспешных попыток разобраться в алгоритмах, топикстартер поделился своим решением: он просто бросил 1000 раз настоящий кубик и забил полученными числами всю свободную память контроллера. Генератор с блеском прошел все тесты на «случайность», учитывая то, что за время демонстрации израсходовал меньше трети своего «запаса».
Следовательно, такое решение тоже имеет право на жизнь, особенно если предъявляются очень строгие требования к случайности чисел, но они требуются не слишком часто. Учитывая стремительно падающие цены на память, может быть разумным снабдить устройство флешкой с «запасом хаоса», которого хватит на все время жизни устройства.
Благодарю за внимание!

UPD1: Как было справедливо отмечено в комментариях, если предполагается атака на ГСЧ, и у злоумышленника будет аппаратный доступ к устройству, применять внешние источники энтропии нужно с большой осторожностью, так как не составляет большой сложности подменить сигнал от внешнего источника. Следует использовать внутренние источники, можно в дополнение к внешним.
Также хорошая идея - накапливать энтропию все свободное время, а использовать ее тогда, когда требуется сгенерировать очередное случайное число. Обычно в таких случаях используется т.н. Entropy pool - массив, над которым периодически выполняется одна из функций ГПСЧ, и куда постоянно подмешиваются данные из источников энтропии.

UPD2: Во многих случаях полезно содержимое Entropy pool (извините, не знаю нормального русского перевода) сохранять в EEPROM для того, чтобы после выключения-включения устройства не накапливать его заново. Это отностится, прежде всего, к получению энтропии методом асинхронных генераторов: при достаточно стабильных условиях после каждого включения может генерироваться одна и та же последовательность.
Если ожидается атака, примите меры против подмены содержимого EEPROM. Если позволяет контроллер, заблокируйте чтение/стирание/запись при помощи lock-битов, при включении контролируйте целостность EEPROM, хотя бы с помощью простейших контрольных сумм.

Теги:

• гсч
• гпсч
• микроконтроллеры
• алгоритмы

Добавить метки

Время и рандом. Реакция

В этот раз мы узнаем, что такое «Случайные» значения, а также научимся работать со временем.

Нам понадобятся:

• Кнопка тактовая
• Пищалка
• Провода соединительные «ПАПА- ПАПА»

Реакция

Наша задача на сегодня – собрать схему, которая позволяет узнать быстроту нашей реакции.

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

Кто скилловый – пробует сам, а мы смотрим на схему.

#define BUZ 8 #define START 9 #define STOP 7 int time; //Переменная для синхронизации void setup() { Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); } void loop() { if(digitalRead(START) == 0) // При нажатии на Кнопку СТАРТ.. { int start_time = millis();// Запомним время нажатия time = start_time; //Запишем его в глобальную переменную. int Rand = random(0, 4000); //Сгенерим "случайную" задержку time = time + Rand; //Прибавим время задержки delay(Rand); //Подождем tone(BUZ, 3000, 500); //Пищим! } if(digitalRead(STOP) == 0 && digitalRead(START) == 1)// При нажатии на кнопку СТОП... { int stop_time = millis(); //Запомним время остановки. time = stop_time - time; // Вычислим разницу во времени. Serial.println("Time: "); // Выведем время в Сериал. Serial.println(time); delay(1000); } } //Перед второй попыткой нажимай на кнопку СТАРТ снова.

Пояснения

int time; Переменным(не всем), при их обозначении, не обязательно задавать какое-либо значение. Эту переменную мы использовали для того, чтобы связать два оператора if.

В С++ переменные, объявленные внутри цикла, не будут доступны в других циклах, так как они действуют только внутри этого цикла. Это делается для того, чтобы предотвратить ошибки в программировании. Когда код программы разрастется, ты поймешь, о чем я говорю.

Чтобы переменная была доступна для нескольких операторов, нужно сделать ее глобальной. Т.е. объявить переменную вне функций.

millis(); Возвращает количество миллисекунд, прошедших с запуска программы.

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

random(min, max); Это генератор «случайных» чисел. Принимает два значения. Он генерирует число в диапазоне от min до max.

«Случайные» числа потому, что это определенная последовательность значений. Очень длинная, но одна и та же. Для того чтобы получать разные последовательности, стоит воспользоваться Random Seed();

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

Вывод

Теперь ты можешь тренировать свою реакцию с помощью собственноручно сделанного устройства. А можешь продолжать заниматься дальше.

Список радиоэлементов

Обозначение	Тип	Номинал	Количество	Примечание	Магазин	Мой блокнот
	Плата Arduino	Arduino Uno	1			В блокнот
	Макетная плата	Breadboard-half	1			В блокнот
	Пьезоизлучатель	Пассивный	1			В блокнот
	Кнопка тактовая	Без фиксатора	2			В блокнот
	Соединительные провода	"Папа-Папа"	1

randomSeed (seed)

Устанавливает значение, или начальное число, в качестве начальной точки функции random().

randomSeed (value); // задаѐт ‘value’ как начальное значение random

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

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

random (max)

random (min, max)

Функция random позволяет вам вернуть псевдослучайное число в диапазоне, заданном значениями min и max.

value = random (100, 200); // задаѐт ‘value’ случайным

// числом между 100 и 200

Примечание: Используйте это после использования функции randomSeed(). Следующий пример создаѐт случайное число между 0 и 255 и выводит PWM

сигнал на PWM вывод, равный случайному значению:

int randNumber; // переменная для хранения случайного значения

int led = 10; // LED с резистором на выводе 10

void setup() {} // setup не нужен

randomSeed (millis()); // задаѐт millis() начальным числом

randNumber = random (255); // случайное число из 0 – 255 analogWrite (led, randNumber); // вывод PWM сигнала

delay (500); // пауза в полсекунды

Источник: Гололобов В. – С чего начинаются роботы. О проекте Arduino для школьников (и не только) – 2011

Related Posts

Serial.begin (rate) Открывает последовательный порт и задаѐт скорость для последовательной передачи данных. Типичная скорость обмена для компьютерной коммуникации - 9600, хотя поддерживаются и другие скорости. void setup () { Serial.begin…….

Все переменные должны быть задекларированы до того, как они могут использоваться. Объявление переменной означает определение типа еѐ значения: int, long, float и т.д., задание уникального имени переменной, и дополнительно ей…….

Хорошо, мы установили эту программу. Мы отладили «механизм» работы с модулем. И посмотрели несколько примеров. Но хотелось бы и самим создавать что-то полезное. Попробуем. Сначала закроем предыдущий проект. Для этого…….

Внимание! При работе с модулем Arduino в других средах разработки следует внимательно относиться к конфигурации микроконтроллера (Fuses). До тех пор, пока вы точно не знаете, к чему может привести изменение…….