Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей на основе клеточных автоматов

• Автор: Сухинин, Борис Михайлович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 224 с. : ил.

Введение

Краткая историческая справка

Случайные последовательности широко используются в самых различных областях. Исторически их применение было связано с развитием теории игр и использованием методов МонтеКарло для численного решения математических задач.
До середины XX в. случайные последовательности имитировались при помощи простейших случайных экспериментов бросания монеты или игральной кости, извлечения шаров из урны, раскладывания карт и т.д. В г. английским ученым Леонардом Типпетом впервые были опубликованы таблицы , содержащие свыше ООО случайных цифр, произвольно извлеченных из отчетов о переписи населения.
Позже были разработаны механические генераторы случайных чисел. Первая такая машина была использована в г. Кендаллом и БабингтонСмитом для построения таблицы , содержащей 0 0 случайных чисел.
Компьютер i I, запущенный в г., обладал встроенным резисторным генератором шума, с которого при помощи специальной программы случайных бит подавались на сумматор этот метод был предложен Аланом Тыорингом. В г. i опубликовала таблицы , в которых содержался миллион случайных чисел, полученных на специально сконструированной ЭВМ с физическим генератором случайных чисел.
К концу XX в. спрос на генераторы случайных последовательностей с заданными вероятностными распределениями, а также на сами случайные
последовательности настолько возрос, что за рубежом стали появляться научнопроизводственные фирмы, занимающиеся производством и продажей больших массивов случайных чисел. Например, в мире с г. распространяется компактдиск i , который содержит 4,8 млрд. истинно случайных бит, а в сети Интернет можно найти массивы случайных чисел, полученные в результате измерения атмосферных шумов ., или регистрации радиоактивного распада i, Зб.
Подобные методы, основанные на различных физических процессах и явлениях, имеющих случайную природу, носят название генераторов истинно случайных последовательностей. Они дают очень хорошие статистические результаты, но требуют колоссального времени для получения скольконибудь длинной последовательности. Так, быстродействие генератора i составляет всего около 0 байт в секунду. После изобретения компьютеров начались поиски эффективных программных способов генерации случайных чисел.
Поскольку любая программа описывает некоторый детерминированный алгоритм, получить истинно случайные числа с ее помощью невозможно. Джон фон Нейман по этому поводу отмечал, что каждый, кто использует арифметические методы генерирования случайных чисел, без условно, грешит . Последовательности, полученные при помощи подобных генераторов, не являются истинно случайными, однако обладают схожими в идеальном случае неотличимыми свойствами, а потому носят название псевдослучайных.
К настоящему времени разработано большое количество всевозможных алгоритмов генерации псевдослучайных последовательностей, основанных на использовании положений теории чисел, свойствах различных алгебраических систем, применении конечных в т. ч. клеточных автоматов и т.д. Тем не менее, практически все такие алгоритмы в силу своей детерминированной природы обладают в той или иной мере различными недостатками, такими как слишком короткий период выходной последовательности, наличие корреляции между различными членами последовательности, неравномерное распределение, предсказуемость, недостаточная
скорость и т.д. Поэтому разработка новых алгоритмов генерации псевдослучайных последовательностей, сочетающих в себе высокое быстродействие и хорошие статистические свойства формируемой выходной последовательности, до сих пор остается актуальной научной и инженерной задачей.
Общая характеристика работы
Диссертационная работа посвящена разработке новых методов генерации псевдослучайных равномерно распределенных двоичных последовательностей, основанных на использовании клеточных автоматов. К основным достоинствам разработанных методов относятся контролируемый.период и хорошие статистические свойства псевдослучайных последовательностей, эффективность и высокое быстродействие аппаратной реализации генераторов.
Актуальность


ПСП должны быть статистически неотличимы от случайных равномерно распределенных двоичных последовательностей, что должно подтверждаться успешным прохождением наборов специализированных статистических тестов. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и шести приложений. Первая глава посвящена обзору основных существующих алгоритмов генерации псевдослучайных последовательностей с равномерным распределением и анализу их достоинств и недостатков. По результатам аналитического обзора делается вывод, что существующие алгоритмы не в полной мерс соответствуют современным требованиям, к которым относятся, в первую очередь, большой период, хорошие статистические свойства и непредсказуемость выходной последовательности, а также высокое быстродействие реализации генератора. Во второй главе приводится формальное определение классических и неоднородных клеточных автоматов и исследуются различные их свойства, такие как распределение значений ячеек, характеристики лавинного эффекта, пространственная и временная периодичность. В этой главе содержатся основные теоретические результаты диссертации формулируются и доказываются критерий сохранения равномерного распределения значений ячеек в классических и неоднородных клеточных автоматах, необходимое условие существования пространственного периода в классических клеточных автоматах исследуются эмпирические зависимости характеристик лавинного эффекта от параметров клеточных автоматов и приводятся их теоретические оценки для оптимального лавинного эффекта. Корректность полученных теоретических результатов подтверждается их согласованностью с данными компьютерного моделирования. Третья глава посвящена разработке новых методов генерации псевдослучайных последовательностей. В ней приводится структура базовых и комбинированных генераторов псевдослучайных последовательностей, в составе которых могут использоваться как классические, так и неоднородные клеточные автоматы. Выбор параметров клеточных автоматов осуществляется на основании результатов, полученных во второй главе. В четвертой главе проводится экспериментальное исследование статистических свойств выходных последовательностей разработанных гене
раторов при помощи специализированного набора статистических тестов Национального института стандартов и технологии США. По результатам тестов выбираются конкретные параметры клеточных автоматов, используемых в структуре генераторов, а также делается заключение о возможности применения разработанных алгоритмов. Пятая глава посвящена построению высокоскоростной аппаратной реализации разработанных алгоритмов. В частности, описывается структура такой реализации и приводятся ее характеристики для двух комбинированных генераторов, выходные последовательности которых обладают наилучшими статистическими свойствами. Также в этой главе проводится сравнение разработанной аппаратной реализации с современными аналогами и делается вывод о существенном превосходстве предложенных генераторов на основе клеточных автоматов. В приложениях приводятся дополнительные сведения, включение которых в основной текст диссертации автор счел нецелесообразным. Прежде всего отметим, что проблема генерации случайной последоиательности с произвольным вероятностным законом распределения сводится с помощью известных методов обратной функции, исключения и композиции см. П и1,а2 . Де ОД Е . Е и произвольных значений индексов 1 Ь . Ргае а 2, шеО. Такие последовательности могут быть получены в следующей схеме испытаний. Допустим, что имеется шаров, различающихся только своим цветом. Сопоставим каждому шару уникальный номер от 1 до и поместим их в непрозрачную урну. Очевидно, что испытания вытягивания шаров из урны являются независимыми. Кроме того, введенные таким образом события являются попарно несовместными и имеют одинаковую вероятность Рга а и Е О Таким образом, полученная последовательность аьаг,. О. случайной последовательностью. В дальнейшем мы будем рассматривать в основном числовые случайные последовательности над множеством О. Для этого достаточно сопоставить каждому элементу П. Е Ъц. М2
2 для любого числа п Е и любой фиксированной последовательности индексов 1 1 . Ргод, аи , ОДП ап аи .