Генератор случайных чисел с использованием 8051

Глава 1. Генератор случайных чисел с использованием 8051

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

Рис 1.1 – Микроконтроллер 8051

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

Оценка «случайности»
Применения для ГСЧ могут найтись самые разные, от игрушек до серьезной криптографии. Соответственно, и требования, предъявляемые к генератору, тоже сильно варьируются. Для оценки качества (уровня «случайности») генератора существуют специальные тесты. Вот самые основные из них:
Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно быть примерно поровну.
Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000...0 или 111...1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
Спектральный тест. К исходной последовательности применяется дискретное преобразование Фурье. Полученный спектр не должен иметь значительных пиков, которые говорили бы о наличии периодических свойств последовательности.
Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.
Существуют специальные наборы, включающие в себя десятки подобных тестов:

• 
  NIST — использовался в конкурсе AES для оценки алгоритмов шифрования.
  
• 
  DIEHARD — один из наиболее строгих существующих наборов.