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

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

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

Для это­го рассмотрим набор [mo, m i , . . . ,mx-i], состоящий из X ячеек памяти.Каждая ячейка в наборе характеризуется ее номером (индексом) — нату­ральным числом х, О < х < X.Сопоставим каждой ячейке т упорядоченный набор ячеек памяти^i(m)= [mXl,тХ2,...,тХ1],0 ^ х{ < X,1 < г ^ Z,где длина (или мощность) набора Wi(m) — число / — не зависит от выбораячейки. Полученный набор Wi(m) назовем окрестностью ячейки т .

Такжепод окрестностью Wi (без указания конкретной ячейки) мы будем подразу­мевать правило, по которому каждой ячейке т сопоставляется ее окрест­ность Wi(m), а под \4?i\ —мощность окрестности произвольной ячейки, т.е.число I (это число мы также будем называть числом связности окрестно­сти).Следуя введенным в разделе 2.1.1 обозначениям, неоднородным кле­точным автоматомл/"(п,х,^,/)размера X над множеством О с окрестностью Wi и локальной функцией1связи / : \С1\ —> D. назовем автономный конечный автоматв котором:- S — множество возможных состояний автомата;- So Е S — начальное состояние;- F — функция переходов.Мы рассматриваем набор [mo, m i , . .

. , mx-i], содержащий X ячеек па­мяти со значениями из множества О. Каждому внутреннему состояниюавтомата s G S однозначно соответствует некоторое заполнение ячеек на--99бора:S = [mi, 7722, • • •, ™>х], ГПх € Q, 0 ^ х < X,т. е. s G S = D.x. Начальное состояние автомата определяется заполнениемячеек, при котором автомат начинает функционирование. Если О = Z2, тоавтомат называется двоичным (булевым).Функция переходов F: S—» S определяет следующее состоя­ние клеточного автомата на основании его текущего состояния (запол­нения ячеек памяти).

По аналогии с классическими клеточными автома­тами, мы определяем функцию переходов при помощи локальной функ­ции связи. Если в момент времени t автомат находился в состоянии St =[m 0ji , m M , . . . , mx-i,t], то его состояние st+i = [mo.t+i, miit+i, • • •, mX-i,t+i]в момент времени t + 1 определяется какst+1 = F(st)<£> mXft+i = /0¥i(mXtt)),где 0 ^ х < X, a ^i{mXjt) —значения ячеек из окрестности тх в моментвремени t. Как и прежде, мы считаем, что функция / не содержит фик­тивных аргументов.2.2.2.

Л О К А Л Ь Н А Я Ф У Н К Ц И Я С В Я З И И Р А В Н О В Е Р О Я Т Н О С Т Ь З А П О Л Н Е ­НИЯ НАБОРА ЯЧЕЕК ПАМЯТИПри исследовании влияния локальной функции связи на распределе­ние значений ячеек неоднородного клеточного автомата мы будем придер­живаться той же схемы, что и в разделе 2.1.3.Рассмотрим произвольный неоднородный двоичный клеточный авто­матAf(Z2,X,Vhf)с окрестностью ^мощности I и локальной функцией связи / : Z 2 —> Z2.Длина вектора значений функции / составляет п = 21, вес —го = | | / | | ,нормированный вес— WQ = w/n.Допущение 2. Значения ячеек неоднородного клеточного автомата могутрассматриваться в качестве независимых случайных величин при случай­ном выборе окрестности каждой ячейки.-100Отметим, что корректность подобного допущения подтверждается со­ответствием эмпирических данных и полученных с его использованием тео­ретических результатов.Как и в случае классических клеточных автоматов, если принять до­пущение 2, можно сформулировать и доказать критерий сохранения рав­номерности распределения значений ячеек НКлА.Утверждение 5.

Равновесность локальной функции связи является необ­ходимым и достаточным условием сохранения равномерного распределе­ния значений ячеек неоднородного клеточного автомата бесконечного раз­мера с независимым и равновероятным выбором входящих в окрестностиячеек.Доказательство.

Как и при доказательстве утверждения 1 в разделе 2.1.3,мы используем индуктивную схему.Предположим, что в момент времени t значения ячеек распределенынезависимо и равновероятно (Vm : Рт[гщ = 1] = Pi[mt = 0] = | ) . Посколь­ку по условию автомат имеет бесконечный размер (X —> со), для произ­вольного подмножества {т^1\т^2\... ,т^}мощности и > 0 ячеек кле­точного автомата и любого двоичного набора а — [а\, а^ • • •, аи] Е Щ вмомент времени t верно равенствоPr [[mj 1} , m f } , .

. . , m[ u ) ] = а] = —(такое заполнение ячеек соответствует условию утверждения и может бытьвыбрано, например, в качестве начального).Из этого равенства следует, что каждый набор Wi(mt) значений ячеекиз окрестности т в момент времени t будет встречаться с равной вероят­ностьюР г [ ^ Ю = а] = ^ае4.Вероятность того, что ячейки т на (t + 1)-ом шаге принимает единич--101ное или нулевое значение, составляет соответственноР г К н = 1] = Е о е 4 : Л о ) = 1 ъШт)Р г К + 1= о] = «,! = f.= о] = £ _ ; r t o ) _ _ 0 * № ( " - ) = «] = (» — >* = " ~ wп(эти равенства выполняются, поскольку ячейки mXi, входящие в окрест­ность ^i(m), выбираются независимо и равновероятно для каждой ячейкит, а значения ячеек в соответствии с допущением 2 рассматриваются какнезависимые случайные величины).Очевидно, что равномерное распределение значений ячеек (равенствоРг[тпм-1 = 1] = Рг[т^+1 = 0]) достигается тогда и только тогда, когдаwпп —wп1<£Ф w= -п21<=$> WQ =-,2'т.

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

2.11 представлены графики временной зависимости отношениячисла ячеек с единичными значениями к общему количеству ячеек дляразличных значений нормированного весаи>о локальной функции связи /.Каждый график отражает усреднение экспериментальных данных по 1 000различных неоднородных булевых клеточных автоматов со следующимипараметрами:- размер — 257 ячеек;- начальное заполнение — случайное с равномерным распределениемзначений;-102-10402030Номер такта t50Рис.

2.11. Отношение количества единичных значений к общему числуячеек неоднородного клеточного автомата при различных ва­риантах нормированного веса WQ локальной функции связи1«аяка;0,8аясох0,6I1-1^ ^ * *яЯЯ0,4Я0,2яеео>ОJ»(0/161i2/164/166/168/16110/1612/16 ' 14/1616/16Относительный вес WQРис. 2.12. Зависимость среднего установившегося значения отношенияколичества единичных значений к общему числу ячеек неод­нородного клеточного автомата от нормированного веса wo ло­кальной функции связи-103- окрестность — случайная, мощности 4 для каждой ячейки;- локальная функция связи — случайная из множества булевых функ­ций заданного веса.Как и в случае классических клеточных автоматов, на графиках хо­рошо видно, что равномерное распределение значений ячеек клеточногоавтомата достигается только при использовании в качестве ЛФС равно­весной булевой функции, что подтверждает теоретические выводы.Для неоднородных клеточных автоматов также была получена эмпи­рическая зависимость среднего установившегося значения отношения чис­ла ячеек с единичными значениями к общему количеству ячеек от норми­рованного веса локальной функции связи (см.

рис. 2.12).2.2.3. Л А В И Н Н Ы Й Э Ф Ф Е К ТПонятие лавинного эффекта в неоднородных клеточных автоматаханалогично введенному ранее понятию для классических клеточных ав­томатов.При изучении лавинного эффекта в неоднородных клеточных автома­тах мы рассматриваем два идентичных автомата ЛЛ1) и ЛЛ2) видаДля обозначения значений ячеек первого автомата в момент времени t мыбудем использовать запись чщ \, второго — пгх1.Идентичность автоматов означает, что у них совпадают размеры набо­ра и множество значений ячеек, окрестности для соответствующих ячееки локальные функции связи. Также мы будем считать, что в начальный2момент времени автоматы J\f^ и ЛЛ ) находятся в состояниях, различаю­щихся только значением ячейки с индексом 0, т.е.В таком случае лавинный эффект отражает изменения, происходящиево втором автомате ЛЛ2) по сравнению с первым ЛЛ1) и вызванные несов­падением значения одной ячейки набора в начальный момент времени (т.

е.фактически изменением одного бита входных данных). Оптимальным мы-104считаем лавинный эффект, при котором изменяется в среднем половинаячеек памяти, а скорость распространения изменений является максималь­ной.Поскольку для неоднородных клеточных автоматов понятие расстоя­ния между ячейками не вводилось, для описания лавинного эффекта мыиспользуем единственную характеристику — интегральную.2.2.3.1.И Н Т Е Г Р А Л Ь Н А Я Х А Р А К Т Е Р И С Т И К А Л А В И Н Н О Г О ЭФФЕКТАИнтегральной характеристикой лавинного эффекта в неоднородныхклеточных автоматах мы назовем временную зависимость rj(t) числа изме­нившихся ячеек к общему их количеству:"(*) = i £ Н>"4!00^х<Хгде Z1 —обычное арифметическое сложение, а ф —сложение по модулю 2.Утверждение 6. Если каждая ячейка памяти неоднородного клеточногоавтомата входит в окрестность I других ячеек, где I — мощность окрестно­сти, то интегральная характеристика лавинного эффекта ограничена свер­ху выражениемг 1 №i t + i -imt+i-i<хiMW< f W | - 1 ' iffl-ГУ '>XU'Wl-i'Доказательство.

Сопоставимг/неоднородномуЛ/'(2 2 ,Х, 1 ;,/) ориентированный граф G=клеточному(V,E)дая вершина vx графа G соответствует ячейке тхе = (vXl,vX2)(2.7)автоматупорядка X.Каж­автомата N, а дугаприсутствует в графе G тогда и только тогда, когда ячейкатХ1 входит в окрестность ячейки тХ2, т. е. mXl G Wi(mX2).Поскольку каждая ячейка входит в окрестность ровно I других ячеек,+граф G является регулярным с полустепенью исхода deg {v) = \Wi\ длявсех v 6 V.Будем рассматривать изменения в значениях ячеек клеточного авто­мата, вызванные сменой значения ячейки тх в начальный момент времени-105t = 0. Обозначим через n(t) количество ячеек, функциональной завися­щих от значения тх,о на t-ош такте работы автомата.

Величина n{t) равнаколичеству вершин графа G, достижимых из vx по всем путям длины неболее t. Верхняя оценка n(t) с учетом значения deg+(i>) составляетn(t) < Ii=0\х,i=°t£№ >x2=0(точное значение n(t) определяется структурой конкретного графа, т. е.выбором окрестностей ячеек, и потому не может быть получено в общемслучае).Учитывая,'что по определению оптимального лавинного эффекта каж­дая ячейка изменяется с вероятностью | , и нормируя значение n(t) по раз­меру клеточного автомата, получаем верхнюю оценку интегральной харак­теристики лавинного эффекта:Vopt{t) <n(t)2^г,что после подстановки n(t) и сворачивания суммы геометрической прогрес­сии дает выражение 2.7.•Отметим, что доказанное утверждение на практике справедливо и длянеоднородных клеточных автоматов со случайным выбором окрестности:в этом случае следует ожидать, что каждая ячейка входит в окрестностьв среднем I ячеек, где I — мощность окрестности.2.2.3.2.

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

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