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

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

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

В данном разделе мы рассмотрим вопросы, связанные как с тра­диционными временными периодами, так и специфичными для клеточныхавтоматов пространственными периодами.-922.1.5.1.ВРЕМЕННАЯ ПЕРИОДИЧНОСТЬ КЛЕТОЧНЫХ АВТОМАТОВРассмотрим клеточный автомат С(С1,Х\ х 12х . . . х Xd^rif)наДпроизвольным множеством О. с размерами решетки Х\ х Х 2 х . . . х Хд- Та­кому клеточному автомату можно поставить в соответствие автономныйконечный автоматВ процессе функционирования автоматаAC{S,SQ,F).его внутренние состояния (т. е. заполнения решетки) формируют последо­вательностьs = s i , s 2 , .

. •,si Е S, г ^ 1.Напомним, что периодом последовательности s называется такое на­туральное число Т Е N, что при любом t > То выполняется равенствоSt = St+Tyа наименьшее число То € N U {0}, при котором указанное равенство вы­полняется, называется в таком случае предпериодом последовательности.Мощность множества внутренних состояний S определяется размера­ми решетки клеточного автомата и составляет | 5 | — \Q.\ I- 2--- <I Посколь­XXX%ку период последовательности состояний автономного конечного автоматане может превосходить мощности множества состояний, он ограничен свер­ху:Т ^ Tmax = |Q|*i-*»--*«.Для двоичных клеточных автоматов (О = Z 2 ) период определяется соот­ношениемТ1< - 1~П±^ хтахе\Х\-Х<1-...-Хй—лВ силу нелинейности локальной функции связи / и, соответственно,функции переходов F конечного автомата оценить период последователь­ности в общем случае не представляется возможным.

Тем не менее, исходяиз тех же соображений, что и авторы [67], мы надеемся, что при случай­но выбранном начальном состоянии вероятность «попадания» в короткийцикл будет ничтожно мала при достаточно больших размерах решетки.Примерами начальных состояний с малым периодом являются, напри­мер, нулевые заполнения всех ячеек решетки, что ведет к циклу длины 1-93или 2 (возможно, с предпериодом), а также любые другие начальные за­полнения ячеек, обладающие пространственной периодичностью, котораябудет рассмотрена далее.2.1.5.2. П Р О С Т Р А Н С Т В Е Н Н А Я П Е Р И О Д И Ч Н О С Т Ь К Л Е Т О Ч Н Ы Х АВТОМА­ТОВДля описания пространственных периодов рассмотрим некоторое за­полнение решетки клеточного автомата C(Q.,Xi х Хч х . .

. х Х^т,/) вмомент времени t:st = [...,m(Xl,x2,...,xd),ti- • -J •Мы будем говорить, что заполнение s обладает пространственной пе­риодичностью с периодом Т{ вдоль оси Xi (1 ^ г ^ d), если % € N —наименьшее число, при котором для всех ячеек решетки клеточного авто­мата при любом fcGZ выполняется равенство™>(xu...,xt,...1xd),t(2-6)— Щхи.^Хг+к-Т,,...^),^При этом следует учитывать, что операции над координатами ячеек вы­полняются по модулю соответствующего линейного размера решетки.Отметим, что в любом классическом клеточном автомате присутствуеттривиальный пространственный период Ti = Xi вдоль каждой из осей.Утверждение 4. Для существования пространственного периода необхо­димо, чтобы его величина делила размер решетки классического клеточ­ного автомата вдоль соответствующей оси.Доказательство.

Рассмотрим произвольный d-мерный классический кле­точный автомат с размерами решетки Х\ х Хч х . . . х Х^. Пусть в этомавтомате существует пространственный период величины TJ вдоль оси Xi,причем Ti ^ Х^Докажем, что величина пространственного периода с необходимостьюделит размер решетки клеточного автомата. Поскольку арифметическиедействия над координатами ячеек выполняются по модулю соответствую­щего размера решетки, для любых к J 6 Z верно равенство(xi + kTi) modXi = (ж,- + к% + lXt)modXi.-94В соответствии с соотношением Безу, существуют такие fc,l6Z, что.кТ{ + 1Х{ = GCD(T i : Х{) = T!^Tt.Предположим, что Ti не делит Xi и, следовательно, Т[ < Т\. Т[ такжеявляется величиной пространственного периода, поскольку для всех ячеекклеточного автомата выполняется соотношениеrn(x1,...,xl,...,xd),t—rn{xi,...,xl+k-T'l,...,xd),t-Но тогда Ti не является наименьшим числом, для которого выполняет­ся условие 2.6, что противоречит определению пространственного периода.Отсюда следует, что GCD(Tj, JQ) = Ti и Ti является делителем Х^•Также можно показать, что если Ti — некоторый делитель Xi, то воз­можно возникновение пространственного периода величины Т{ вдоль осиXi.

Для этого приведем пример соответствующего заполнения решетки:{1,если Xi mod Ti — О,О, в противном случае.Очевидно, что в таком случаеXimodTi = x'imodTi=>• m{xu^x.^XdU=га^,...,^,...,^,поэтому докажем равенство [(xi + kTi) modXi] modTi = Xi modT; для про­извольного к € Z:[(xt + kTi) modXi] modTi = [x{ + kTt + aXi] modTi\x^bT== [х{ + кТ{ + abTi] m o d T i | A + a b = c == [xi + cTij modTj = Xi modTj.Таким образом, m^,...,^,...,^ = m{xi^Xi+kTi^Xd)j,т. е. равенство 2.6 вы­полняется.Предположим, что в выбранном заполнении вдоль оси Xiсуще­ствует другой пространственный период величины Т[ < Ti.

Но тогдаm(Xl,...,o,...,xd),t = 1, а m{xu^T,^Xd)yt= 0, поскольку ^ ' m o d T ; ф 0. Следова--95тельно, Tj — наименьшее число, для которого равенство 2.6 выполняется,что соответствует определению пространственного периода.Поскольку классические клеточные автоматы являются однородны­ми, и геометрическая интерпретация окрестности \УГ не зависит от выбораконкретной ячейки, при наличии пространственного периода также выпол­няются равенстваrrl(xi,...,xl,...,Xd),t+l=m(xi,...,xt+kTi,...,xd),t+l-Из этих равенств следуют два важных вывода:. - пространственный период сохраняется в процессе функционированияклеточного автомата;- наличие пространственного периода Т{ вдоль оси Х{позволяетрассматривать клеточный автомат с исходным размером решет­ки Х\,...

,Xi,...Xi,...,Tj,...,Xdкак автомат с решеткой меньшего размера,Xd.Максимальный период клеточного автомата в таком случае определяетсясоотношениемТxmax\r\\Xi-...-Tt-...-Xd— |л-*-|5т. е. меньше величины максимально возможного периода клеточного авто­мата в \Q\x1:.,(xl-Tl):..-xd р а зСуществование пространственного периода возможно только в томслучае, если его величина делит размер решетки клеточного автоматавдоль соответствующей оси, и чем больше нетривиальных делителей имеетразмер, тем выше вероятность возникновения периода.

Следовательно, дляуменьшения вероятности возникновения подобных негативных эффектов вкачестве размеров решетки следует выбирать простые числа.-96!60i97i134171Номер такта t<• 208;245f282Рис. 2.10. Проявление периодичности на графике пространственной ха­рактеристики лавинного эффекта2.1.5.3. И Н Ы Е П Р О Я В Л Е Н И Я П Е Р И О Д И Ч Н О С Т ИКроме рассмотренных пространственных периодов на временной пери­од клеточных автоматов могут влиять другие «регулярности» в заполнениирешетки, в том числе рассматриваемые во времени. Одной из таких «регулярностей» являются «бегущие» заполнения (хорошо знакомые многим попопулярной игре «Жизнь» Джона Конвэя [26]):m(xi,X2,...,xd),t==m(xi+ai,X2+a2,...,xd+ad),t+liгде 0 ^ щ ^ г, 1 ^ г ^ d.

Возможны и более сложные зависимости,приводящие, тем не менее, к снижению периода.Проведенные нами эксперименты показали, что эффекты простран­ственной периодичности проявляются с большей вероятностью для клеточ­ных автоматов с окрестностями малой мощности. На рис. 2.10 изображеныграфики пространственной характеристики лавинного эффекта в автома­тах вида С(2^2,37 х 11,4/1, / ) . Данные получены усреднением по 10 000 кле­точных автоматов для каждого типа окрестности. На рисунке отчетливо-97видны колебания графика пространственной характеристики для клеточ­ного автомата с неполной окрестностью, состоящей из 4-х ячеек.

Пери­од колебаний совпадает с размером решетки клеточного автомата по осиX и составляет 37 тактов, что подтверждает связь колебаний с простран­ственной периодичностью. Также из графиков следует, что при увеличениимощности окрестности колебания резко сокращаются (поскольку графикиполучены усреднением значений по большому числу автоматов, это экви­валентно снижению вероятности).2.2.Н Е О Д Н О Р О Д Н Ы Е К Л Е Т О Ч Н Ы Е АВТОМАТЫ2.2.1. О С Н О В Н Ы Е П О Н Я Т И Я И О П Р Е Д Е Л Е Н И ЯНеоднородные клеточные автоматы (НКлА) являются развитием мо­дели классических клеточных автоматов, рассмотренной ранее.

Напомним,что классический клеточный автомат в общем виде представляет собой со­вокупность ячеек памяти, упорядоченных в некоторую решетку, и правилсмены значений ячеек, определяющих переходы между состояниями автомата. При этом значение каждой ячейки на следующем такте работызависит только от текущих значений соседних с ней ячеек (свойство ло­кальности), и все ячейки являются неразличимыми (свойство однородно­сти).Неоднородные клеточные автоматы (как и классические) являются со­вокупностью набора ячеек памяти и правил перехода, однако ячейки неупорядочиваются в какую-либо решетку или иную структуру и рассмат­риваются просто как некоторый набор. Понятие размерности автомата вэтом случае не имеет смысла, поэтому мы будем говорить о его размере —количестве ячеек памяти в автомате.Как следует из названия, в неоднородных клеточных автоматах свой­ство однородности не.выполняется, т.е.

ячейки являются различимыми имогут обладать различными свойствами (в частности, различными окрест­ностями). Под окрестностью каждой ячейки понимается некоторое напередвыбранное множество фиксированной мощности, в отличие от классическо­го случая не имеющее геометрической интерпретации, поэтому свойстволокальности для неоднородных клеточных автоматов также формулиру--98ется иначе: значение каждой ячейки на следующем такте работы зависиттолько от текущих значений ячеек, входящих в ее окрестность.Перед тем, как дать формальное определение неоднородного клеточ­ного автомата, необходимо сформулировать понятие окрестности.

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

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