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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

З А В И С И М О С Т Ь Х А Р А К Т Е Р И С Т И К Л А В И Н Н О Г О Э Ф Ф Е К Т АОТВЫБОРА ОКРЕСТНОСТИХарактеристики лавинного эффекта в неоднородных клеточных авто­матах существенно зависят от выбора окрестности "Ч7/, а точнее, посколькусама окрестность для каждой ячейки должна определяться случайным об­разом (см. раздел 2.2.2), от выбора ее мощности I.На рис. 2.13 приведены графики интегральной характеристики лавин­ного эффекта в неоднородных булевых клеточных автоматах. Данные по--106--t-iЧ?окрестностьокрестностьокрестностьокрестностьокрестность01020304050607080\Wi\Wi|"4^\Wi\4?i9065432100Номер такта tРис. 2.13.

Интегральная характеристика лавинного эффекта в неодно­родных булевых клеточных автоматах J\f(%2, 257, "Ч^, /)лучены экспериментально путем исследования автоматов с параметрамиЛ^(^2,257,11у/,/), Начальные значения ячеек памяти выбирались в соот­ветствии с равномерным законом распределения. Окрестность^ выбира­лась случайным образом для каждой ячейки. Локальная функция связи/также является случайно выбранной из множества равновесных булевыхфункцией. Каждый график отражает усреднение по 1000 различных неод­нородных клеточных автоматов с заданным значением мощности окрест­ности \fy.Графики теоретической оценки интегральной характеристики опти­мального лавинного эффекта не приводятся, поскольку они зависят от вы­бранного значения мощности окрестности "Ч^.На графиках видно, что интегральная характеристика лавинного эф­фекта быстро приближается к некоторому стационарному уровню, различ­ному для каждого значения |Ч^|.

Для больших значений мощности окрест­ности характерно более резкое нарастание характеристики и более высокоеустановившееся значение.-107Тем не менее, ни один график не достигает максимального уровня0,5. Это связано с тем, что графики отражают усредненные данные, и вряде экспериментов (при определенном сочетании выбора начального за­полнения, окрестности и локальной функции связи) лавинный эффект отизменения единственной ячейки не проявился. Очевидно, что вероятностьвозникновения такой ситуации должна уменьшаться с увеличением мощ­ности окрестности, что и подтверждается экспериментальными данными.Сравнивать лавинный эффект в классических (рис.

2.8 на стр. 90) инеоднородных (рис. 2.13 на стр. 106) клеточных автоматах не совсем кор­ректно, поскольку данные отражают характеристики для различных кле­точных автоматов с разным количеством ячеек памяти и принципиальноразличающейся структурой связей между ячейками. Тем не менее, еслипоставить задачу сравнения характеристик автоматов С(Z2,37 х 11, Ч^, /с)и A/"(Z2,257,4/j,/;v), то можно отметить следующие факты:- в неоднородных клеточных автоматах интегральная характеристикаоптимального лавинного эффекта экспоненциально зависит от номератакта, в то время как в классических — полиномиально;- в неоднородных клеточных автоматах кривая интегральной характе­ристики нарастает более круто;- установившийся уровень характеристики при равных значениях мощ­ности окрестности в неоднородных клеточных автоматах выше.Таким образом, для рассмотренных нами автоматов можно утверждать,что неоднородные клеточные автоматы в обладают лучшими характери­стиками лавинного эффекта по сравнению с классическими аналогами.2.2.4.

С В О Й С Т В А П Е Р И О Д И Ч Н О С Т ИНеоднородные клеточные автоматы- относятся к автономным конеч­ным автоматам. Период последовательности внутренних состояний s огра­ничен сверху мощностью множества состояний S: Ттах = | 5 | . В случае,если автомат является двоичным т.е. относится к классу Af(7i2,X,'4!i, / ) ,максимальный период составляетТ1Х=2- max — «•-108При этом следует учитывать, что максимальный периодТ т а х являетсяоценкой сверху и на практике недостижим.

Так, например, при одинаковыхзначениях всех ячеек в начальный момент времени последовательность со­стояний автомата обладает коротким периодом, в зависимости от локаль­ной функции связи составляющем 1 или 2.Более точные теоретические оценки периода являются затруднитель­ными в силу как нелинейности локальной функции связи, так и случайногохарактера выбора окрестности "Ч7;. Осуществление же эмпирической оцен­ки периода потребует (из-за большого количества возможных состоянийавтомата) чрезвычайно больших вычислительных ресурсов и (в связи сполучением результатов только для конкретного автомата) будет обладатьограниченной практической и теоретической значимостью.2.3. ВыводыДанная глава была посвящена изучению различных свойств классиче­ских и неоднородных клеточных автоматов, влияющих на возможность иособенности их использования в структуре генераторов псевдослучайныхпоследовательностей.

При проведении исследований использовались кактеоретические методы, так и эмпирический подход.В'результате исследований были получены новые научные результаты:- сформулирован, доказан и подтвержден эмпирически критерий сохранения равномерности распределения значений ячеек памяти клеточ­ных автоматов;- получено теоретическое описание характеристик оптимального лавин­ного эффекта и эмпирические зависимости характеристик лавинногоэффекта от выбора окрестностей ячеек; показано, что клеточные ав­томаты обладают свойством размножения изменений;- сформулировано и доказано необходимое условие существования про­странственного периода; показано, что нетривиальный пространствен­ный период существенно снижает верхнюю границу периода последо­вательности внутренних состояний.Большинство теоретических результатов получено для общего случаяn-мерных классических клеточных автоматов с произвольным радиусом-109локальности и неоднородных клеточных автоматов с произвольной мощно­стью окрестности; для двумерных булевых клеточных автоматов как наи­более перспективного подкласса классических клеточных автоматов с точ­ки зрения использования в структуре генераторов псевдослучайных после­довательностей также получены частные результаты.

Корректность теоре­тических выводов подтверждается их хорошей согласованностью с эмпи­рическими данными.Результаты исследований свидетельствуют о том, что в общем слу­чае неоднородные клеточные автоматы обладают лучшими свойствами посравнению с классическими аналогами. В главе 5 также будет показано,что аппаратная реализация генераторов на основе неоднородных клеточ­ных автоматов является гораздо более эффективной по сравнению с реа­лизацией генераторов на основе их классических аналогов.Проведенные исследования позволяют обосновать выбор параметровклеточных автоматов при осуществлении синтеза генераторов псевдослу­чайных последовательностей на их основе. В частности, из полученныхрезультатов следует, что:- для обеспечения равномерности распределения значений ячеек кле­точных автоматов локальная функция связи должна являться равно­весной;- для улучшения характеристик лавинного эффекта и обеспечения раз­множения изменений следует использовать окрестности по возможно­сти большей мощности;- для исключения формирования пространственных периодов в класси­ческих клеточных автоматах размеры решетки должны быть просты­ми числами.-110-ГЛАВА 3РАЗРАБОТКА ГЕНЕРАТОРОВПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙВ этой главе рассматриваются вопросы построения генераторов псев­дослучайных последовательностей с использованием классических и неод­нородных клеточных автоматов.

Поскольку наиболее удобными как дляаппаратной, так и для программной реализации являются двоичные си­стемы, мы рассматриваем только клеточные автоматы над множествомZ 2 = {0,1}.Для каждого типа автоматов сначала описывается базовый (упрощен­ный) генератор и обосновывается выбор параметров клеточного автомата,а затем предлагается комбинированный генератор, обладающий улучшен­ными характеристиками.3.1. О ПАРАМЕТРАХ КЛЕТОЧНЫХ АВТОМАТОВ И ЭФФЕК­ТИВНОСТИ ИХ РЕАЛИЗАЦИИПроцесс выбора параметров клеточных автоматов является поискомкомпромисса между эффективностью реализации и обеспечением хорошихсвойств выходной последовательности.При аппаратной реализации каждая ячейка клеточного автоматапредставляется в виде триггера и булевой функции, определяющей его зна­чение на следующем такте работы, причем для каждой ячейки функцияреализуется отдельно, что позволяет осуществлять параллельные вычисле­ния. Для задания булевых функций используются таблицы сопоставления-Illнабора аргументов и значений функции.

Характеристики

Список файлов диссертации