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

раздел 2.1.1). Как и в случае одномерныхклеточных автоматов, для решения проблемы пограничных клеток проти­воположные края решетки двумерного клеточного автомата отождествля­ются, что соответствует рассмотрению решетки на торе (см. рис. 2.2).Р и с . 2.2. Отождествление противоположных краев решетки двумерногоклеточного автоматаДвумерным булевым клеточным автоматом с размерами решеткиX х Y, радиусом локальности г, окрестностью Wr и локальной функци--76ей связи / называется клеточный автоматC(Z2,XxY,Wr,f),описываемый автономным конечным автоматомAi(S,so,nв котором:- S = Z ^ ' y — множество внутренних состояний;- So G S — начальное состояние;- F : S -» S — функция переходов.Внутреннее состояние клеточного автомата описывается двумернымнаборомЩо,о)о_—771(0,1)^г(0,У-1)Щ\,о)ТО(1,1)••• Щх-1,о)• • •™>{1,Y-1) ' ' '7П(х-1,1)m{X-l,Y-l)_Действие функции переходов F заключается в применении локальнойфункции связи / к окрестности каждой ячейки клеточного автомата:™(x,y),t+l =fWr(™>M,t))-На рис.

2.3 приведены наиболее распространенные варианты выбораокрестностей Wi(m) для двумерных клеточных автоматов с радиусом ло­кальности г = 1 (закрашенная клетка соответствует вхождению ячейки вокрестность). Варианты, изображенные на рис. 2.3(a) и 2.3(6), также на­зывают полной и неполной окрестностями Мура, на рис.2.3(B) Иполной и неполной окрестностями фон Неймана соответственно.2.3(г) —-77-(а)(б)(в)(г)Рис. 2.3. Некоторые возможные варианты окрестности ячейки Ш\ длядвумерного клеточного автомата с радиусом локальности г = 1:(а) —полная окрестность, l^il = 9, (б) — квазиполная окрест­ность, |\Ki | = 8, (в) — неполная окрестность, \Ч?\\ = 5, (г)неполная окрестность, \Wi\ = 42.1.2.

О Б З О Р И М Е Ю Щ И Х С Я Р Е З У Л Ь Т А Т О В Д Л Я К Л А С С И Ч Е С К И Х О Д Н О ­МЕРНЫХБУЛЕВЫХ КЛЕТОЧНЫХ АВТОМАТОВРассмотрение свойств классических клеточных автоматов логично на­чать с обзора полученных в этой области результатов. Основные исследо­вания в области клеточных автоматов, их свойств и возможностей приме­нения для генерации псевдослучайных последовательностей принадлежатСтефану Вольфраму. Мы приводим основные результаты, опубликованныев работах [81-85] и др. (перечень работ вместе с полными текстами статейдоступен на сайте [68]).Вольфрамом был исследован одномерный булев клеточный автоматc(z2,nx,/)над множеством Ъ% с 11 ячейками памяти и полной окрестностью ра­диуса 1, где локальная функция связи / определена как /(хз,Х2,Х\)=x%з Ф %2 Ф i Ф Х2Х\ (Вольфрам также называет эту функцию «прави­лом 30», поскольку двоичная запись вектора значений функции соответ­ствует числу 30).

В качестве начального заполнения использовался наборso = [0,0,0,0,0,1,0,0,0,0,0]. Выходная последовательность формирова­лась из значений ячейки т^ на каждом такте. Графическая иллюстрацияфункционирования такого одномерного булева клеточного автомата при­ведена на рис. 2.4.78-1SO«ГР и с . 2.4. Последовательность внутренних состояний одномерного булева1клеточного автомата с полной окрестностью Ч ^ и локальнойфункцией связи /(а?з, %2, х\) = %з Ф х2 Ф х\ 0 х^х\-79Особое внимание в своих исследованиях Вольфрам уделил свойствампериодичности одномерных клеточных автоматов.

При больших значенияхразмера решетки X подавляющее число состояний приходится на главныйцикл или подходы к нему; более мелкие циклы в основном соответствуютспецифичным начальным заполнениям решетки, например, обладающимкакого-либо рода симметрией. Функция переходов автомата, определяемая«правилом 30», задает близкое к биективному отображение: более чем од­ного предка на графе переходов автомата имеет около 0,85yY из 2х вершин,однако в целом автомат не является обратимым (см. рис.

2.5).Также Вольфрам исследовал зависимость длины W наибольшего цик­ла на, графе переходов клеточного автомата от размера X решетки ячеекпамяти и определил, что W РХ 2 0 , 6 1 х для X ^ 53 (см. рис. 2.6).Вольфрамом была рассмотрена возможность применения подобныходномерных клеточных автоматов в качестве генераторов гаммы поточ- 'ного шифрования (т. е. генераторов псевдослучайных последовательностейкриптографического качества) [82]. Проведенные им исследования стати­стических свойств выходной последовательности не показали каких-ли­бо аномалий, позволяющих отличить ее от истинно случайной при длинепоследовательности, не превосходящей длину периода. В настоящее вре­мя одномерные клеточные автоматы используются в составе генераторапсевдослучайных последовательностей в математическом пакете WolframMathematica, разработанном компанией Wolfram Research [69], однако востальном не получили широкого распространения.2.1.3. Л О К А Л Ь Н А Я Ф У Н К Ц И Я С В Я З И И Р А В Н О В Е Р О Я Т Н О С Т Ь ЗНАЧЕ­НИЙ ЯЧЕЕК РЕШЕТКИОсновным параметром, определяющим особенности функционирова­ния клеточных автоматов, является локальная функция связи /.

Важнойзадачей является изучение связи между характеристиками функции / ираспределением значений ячеек по решетке клеточного автомата.Рассмотрим произвольный d-мерный двоичный клеточный автоматC(Z2,X1xX2x...xXd,WrJ)-80-4 - Ф— V- ^Рис. 2.5. Граф переходовv>— Р~~ Р ~одномерного булева клеточногоавтоматас полной окрестностью W± и локальной функцией связи= хз 0 Х2 Ф х\ ф Х2Х\ (иллюстрация из [82])f(x^,X2,xi)soоРис. 2.6. Длина наибольшего цикла одномерного булева клеточного ав­томата с полной окрестностью Ш* и локальной функцией связи/(жз, Х2, х\) = жз Ф Х2 Ф xi ф ж2а:1 (иллюстрация из [82])-81гс окрестностью Wr и локальной функцией связи / : Z 2 ' —>• Z2.ТВектор значений локальной функции связи имеет длину п = 2^ УОбозначим через w = | | / | | вес булевой функции /, т.е.

число наборов,на которых функция / принимает ненулевые значения (или, что то жесамое, количество ненулевых компонентов в векторе ее значений), а черезwo = w/n — нормированный вес.Поскольку клеточные автоматы обладают достаточно сложным пове­дением, при исследовании влияния локальной функции связи на равно­мерность распределения значений ячеек мы будем исходить из истинностиследующей гипотезы.Допущение 1. Значения ячеек классического клеточного автомата могутрассматриваться в качестве независимых случайных величин.Отметим, что корректность подобного допущения подтверждается со­гласованностью теоретических результатов с эмпирическими данными.Если принять допущение 1, то можно сформулировать и доказать кри­терий сохранения равномерного распределения значений ячеек классиче­ского клеточного автомата в следующем виде.Утверждение 1.

Равновесность локальной функции связи является необ­ходимым и достаточным условием сохранения равномерного распределе­ния значений ячеек классического клеточного автомата с бесконечным раз­мером решетки.Доказательство. Доказательство проведем по индуктивной схеме.екПредположим,чтораспределеныповмоментрешетке(Vm : Рг[ш{ = 1] = Pi[mt — 0] = | ) .временинезависимоПосколькузначенияtипояче­равновероятноусловиюрешеткаимеет бесконечный размер (Xi —> 00, 1 ^ i ^ d), для произвольногоподмножества {m^l\m^2\... , m ^ } мощности и > 0 ячеек автомата илюбого двоичного набора а = [ai,a2,..., a u ] £ Щввыполняется равенствоPr [[mf\ mf\ . .

. , m[u)] = a] = —момент времени t-82(такое заполнение соответствует условию утверждения и может быть вы­брано, например, в качестве начального).Отсюда следует, что каждый набор Wr(mt) значений ячеек из окрест­ности т в момент времени t будет встречаться с равной вероятностьюР г [ ¥ г Ю = а] = ^ - | ,а 6 4¥г1.Ha (t + 1)-ом шаге значение ячейки т определяется зависимостьюmt+i = f(^¥r(mt)).Вероятности того, что произвольная ячейка т клеточ­ного автомата принимает единичное или нулевое значение, составляют со­ответственноP r [ m m = 1] = E a e Z i - H : / ( a ) = 1 Р^Лт)P r[W m= а] = у,^щ== 0] = E a € Z i ^ .

: / ( a ) = 0 Р г | У г Ю = а] = (n - w)-^^=^.(в соответствии с принятым допущением 1 мы рассматриваем значенияячеек как независимые случайные величины).Равномерному распределению значений ячеек клеточного автомата вмомент времени £ + 1 соответствует равенство Pr[m t + i = 1] = Pr[m i + i = 0],которое, очевидно, достигается тогда и только тогда, когдаwпп —wп1<Ф w = -п24Ф1WQ= -)2'т.

е. при условии равновесности локальной функции связи.DТаким образом, равновесность локальной функции связи являетсянеобходимым и достаточным условием сохранения равномерного распреде­ления значений ячеек классического клеточного автомата. Использованиеже в качестве ЛФС неравновесных булевых функций будет приводить от­клонениям от равномерного распределения, что является нежелательнымпри использовании клеточных автоматов для генерации псевдослучайныхпоследовательностей.Несмотря на то, что критерий сформулирован для классических кле­точных автоматов с решеткой бесконечного размера, на практике он выпол­няется и для классических клеточных автоматов с достаточно большими-83-0,7500,6250,5000,3750,2502030Номер такта tРис. 2.7.

Отношение количества единичных значений к общему числуячеек решетки классического клеточного автомата при различ­ных вариантах нормированного весагио локальной функции свя­зиразмерами решетки, что подтверждается эмпирическими данными.На рис. 2.7 изображены графики временной зависимости отношенияколичества единичных значений в заполнении решетки клеточного авто­мата к общему числу ячеек для локальных функций связи с различныминормированными весами WQ.

ДЛЯ каждого значения нормированного весаи>о данные отражают усреднение экспериментальных результатов по 1000различных клеточных автоматов с размерами решетки 37 х 11 ячеек, ра­диусом локальности 1 и полной окрестностью W^. В каждом экспериментевектор значений функции / выбирался случайным образом из множествавсех булевых функций заданного веса.На графиках хорошо видно, что каждому значению нормированноговеса WQ соответствует быстрое приближение к некоторому стационарно­му значению числа единичных ячеек решетки клеточного автомата, при­чем равенство между количеством единичных и нулевых ячеек достигается-84только при WQ = | , что соответствует равновесным функциям и согласует­ся с теоретическими результатами.2.1.4.