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