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

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

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

О С Н О В Н Ы Е П О Н Я Т И Я И О П Р Е Д Е Л Е Н И ЯКлеточный автомат представляет собой упорядоченный набор ячеекпамяти, образующих некоторую регулярную d-мерную решетку (на прак­тике наибольшее распространение приобрели клеточные автоматы неболь­шой размерности — с одно-, двух- и трехмерными решетками). Каждаяячейка клеточного автомата может хранить одно значение из некоторо­го конечного множества О.. Время для клеточного автомата изменяетсядискретными шагами (тактами).

Смена значений всех ячеек решетки про­исходит синхронно и одновременно при увеличения номера такта в соот­ветствии с правилами перехода, определяющими новое значение каждойячейки решетки в зависимости от текущих значений других ячеек.Структура пространственной решетки зависит от формы входящих внее ячеек. Так, например, в двумерном случае можно рассматривать ячей­ки прямоугольной, треугольной, шестиугольной и иных конфигураций. Внашей работе мы ограничимся рассмотрением только клеточных автома­тов, в которых решетки имеют прямоугольную форму, а ячейки — квадрат­ную.Для классических клеточных автоматов (ККлА) выполняются двасвойства [11]:-691) свойство локальности — значение каждой ячейки памяти на следую­щем такте работы клеточного автомата зависит только от текущихзначений ячеек в некоторой ее окрестности (и, возможно, от значениярассматриваемой ячейки);2) свойство однородности — правила перехода являются одинаковымидля всех ячеек решетки клеточного автомата.Из свойства однородности классических клеточных автоматов следу­ет, что все ячейки решетки являются неразличимыми по своим свойствам.Поскольку граничные ячейки решетки обладают меньшим количеством«соседей», они отличаются от других ячеек, что противоречит свойствуоднородности.

Для решения этой проблемы противоположные краяй-мерной решетки отождествляются, что для одномерных клеточных автоматовравносильно скручиванию решетки в кольцо, а для двумерных — в тор.Перед тем, как дать формальное определение клеточным автоматам,необходимо ввести некоторые дополнительные понятия. Для этого рассмот­рим набор ячеек памяти, упорядоченных в d-мерную решетку с линейнымиразмерами Х\ х Х2 х . . .

х Х^. Положение каждой ячейки в такой решет­ке описывается вектором координат (xi,X2,...,Xd),где 0 ^ xi < Xi и1 < % ^ d.Расстоянием между ячейками памяти т^I (1)(1)\(1)[х\ , х\ ,. •., xd')1личину д(т( \гп№),/ (2)(2)и т^(2Ки (xi',X2,...,xd)с координатамие-соответственно будем называть ве­определяемую следующим способом:5{т(1\тУ"') = тах{сг},гдеCi = тт{а»,6$},Щ •T(l) _T(2)щ = Xi — a,-.Введенное таким образом расстояние равно максимальной разницемежду соответствующими координатами ячеек с учетом отождествленияпротивоположных краев решетки. Очевидно, что максимально возможноерасстояние между двумя произвольными ячейками в таком случае состав--70-ляетmax"maxX,-l(2.1)l<i<dа расстояние от ячейки до самой себя равно нулю:5(т,т) = 0.Используя понятие расстояния между ячейками можно формальноввести определение r-окрестности ячейки (число г также будем называтьрадиусом окрестности).

Для этого рассмотрим rf-мерную решетку ячеекпамяти и некоторую ячейку га этой решетки.Назовем полной r-окрестностью ячейки т множество Ф+(га) ячеек,удаленных от нее на расстояние не более г (включая и саму ячейку га):Ф*(га) = {т*\5(т,га*) ^ г}.Квазиполной r-окрестностыо ячейки га будем называть множествоФ°(га) ячеек, удаленных от т на расстояние не более г, за исключениемсамой ячейки га:ф°(га) = Фг(т) \ {га}.Наконец, неполной r-окрестностью ячейки га будем называть любоесобственное подмножество Ф~(га) ее квазиполной r-окрестности Ф^(га):Ф~(га) С Ф°(га).Таким образом, полная r-окрестность ячейки га с координатами(ж1,Ж2, • • • ,Xd), 0 ^ Xi < Х{, 1 ^ % < d, образована всеми ячейками га*с координатами((xi + ci) modXi, (ж2 + с 2 ) m o d X 2 , .

. . , (xd + cd)где —г ^ c i ^ r n l ^ i ^ d ,modXd),а квазиполная и неполная окрестностимогут рассматриваться как подмножества полной окрестности. Все опера­ции над координатами ячейки производятся по модулю соответствующеголинейного размера решетки, что отражает отождествление ее противопо­ложных краев. В дальнейшем операцию взятия числа по модулю мы будем-71пропускать для сокращения записи.Зафиксируем некоторое правило, по которому неупорядоченному мно­жеству ячеек сопоставляется их упорядоченный набор (такое правило мо­жет основываться, например, на геометрической интерпретации решеткиили лексикографическом порядке перечисления векторов координат).

Припомощи этого правила сопоставим каждому множеству Фг(т) упорядочен­ный набор Wr(m).Если указывать конкретный тип окрестности (полная, квазиполнаяили неполная) нет необходимости, мы будем использовать обозначенияФ г ( т ) для множества и Wr(m) для набора. Кроме того, в случае, когдаимеется ввиду само правило, сопоставляющее каждой ячейке т упорядо­ченный набор ^ ( т ) , и не требуется указывать конкретную ячейку, будемиспользовать обозначение Ч7,..В дальнейшем мы будем использовать расширенное толкование тер­мина «окрестность», подразумевая под ним один из следующих объектов:- неупорядоченное множество Ф г (га) для конкретной ячейки га;- упорядоченный набор Wr(га), соответствующий множеству Ф г (га);- правило Wr, сопоставляющее каждой ячейке га набор Wr(m).Такая терминология не будет вносить неоднозначность, поскольку разли­чия следуют из контекста и из используемых обозначений.В силу регулярной структуры решетки и свойства однородности кле­точных автоматов мощность окрестностиWr(m) не зависит от выбора ячей­ки га, поэтому обозначим через \Ч/Г\ мощность окрестности произвольнойячейки.

Очевидно, что мощность:- полной окрестности составляет- квазиполной окрестности — на единицу меньше мощности полнойокрестности:d| ^ | = (2r + l ) - l ;- неполной окрестности — строго меньше мощности квазиполной окрест--72ности:\W;\ < |Ч^| = ( 2 r + l ) d - l .При формализации понятия клеточного автомата его удобно рассмат­ривать с позиции теории конечных автоматов.В общем случае клеточным автоматомС(П)11х12х...х1Л/)над множеством П. с d-мерной решеткой размера Х\ х Х2 х . . . х Хд,радиусом локальности г, окрестностью Ч?г и локальной функцией связи/ : О)^^ -* П., задающей правила перехода, называется автономный ко­нечный автоматAc(S,8o,F),где:- S — множество возможных состояний автомата;- SQ Е S — начальное состояние автомата;- F — функция переходов.Для обозначения ячейки решетки клеточного автомата с координата­ми (ж1,Ж2, • • • ,Xd) мы будем использовать запись т ( 1 1 1 1 2 ] .

. . Л ) , а в случае,если необходимо указать на ее значение в некоторый момент времени t —записьm(xuX2^Xd)>t.Каждое внутреннее состояние s автомата соответствует заполнениюрешетки клеточного автомата и описывается упорядоченным набором, ком­понентами которого являются значения ячеек памяти:s = [..., m{xii^Xd),...],1 ^ х{ < ХиXlXdпри этом rri(Xl)_)Xd) G П и s G S = Q. '-' .1 ^ г ^ d,Начальное состояние «о авто­мата определяется заполнением ячеек решетки, при котором автомат на­чинает свою работу.В случае, если ячейки клеточного автомата могут принимать толь­ко значения из множества {0,1} (О.

= Z2), то такой автомат называетсядвоичным или булевым.Функция переходов является отображением множества состояний S на-73себя (F : S —> S) и определяет следующее состояние автомата н аоснова-нии текущего. Определять функцию переходов F удобно через лоьс-^ьльнуюфункцию связи клеточного автомата, и в дальнейшем мы будем;ысполь-зовать именно такой способ. Для этого рассмотрим два п о с л е д о в а Т ^ - 7 1 Ь Н Ь 1 Хсостояния автомата. В момент времени t состояние автомата о п и с ! = » 1 : в а е т с янаборомst = [. . . , т ( ж ь . . . ^ ) ^ , . . . ] ,а в момент времени t + 1 — наборомSt+l = [••-, ™>(xi,...,xd),t+li • • •]•Набор St+i получается из st применением функции переходов F:si+1=F(st),а значения компонентов набора st+i определяются путем п р и м е н е : ^ : : и : Ял0~кальной функции связи к окрестности каждой ячейки набора st:m(Xll...,Xd),t+i = / ( ^ ( m ^ , .

. . ^ ) ^ ) ,1 < Xi < Xhl^i^d.Мы будем считать, что функция / существенно зависит от всех с в с з > ^ * х ар­гументов. В противном случае можно переопределить окрестность к ^ - л е т о ч ного автомата таким образом, чтобы ячейки, соответствующие фикхг^зЕЗНЫмаргументам, в нее не входили.На данный момент мы не определяем выходной алфавит и ф у - ^ з : * с Ч и ювыходов клеточного автомата, поскольку они несущественны для и с ^ < ^ - ; г 1 е < а , ( >вания свойств и необходимы лишь на этапе разработки конкретны;?—^ алго­ритмов генерации псевдослучайных последовательностей.-742.1.1.1.

О Д Н О М Е Р Н Ы Е БУЛЕВЫ К Л Е Т О Ч Н Ы Е АВТОМАТЫПростейшим видом клеточных автоматов являются одномерные буле­вы клеточные автоматы, представляющие собой частный случай клеточ­ных автоматов с одномерной решеткой двоичных ячеек памяти. В некото­рой литературе такие автоматы иногда называются элементарными кле­точными автоматами [85].Учитывая, что в соответствии со свойством однородности для разре­шения проблемы краевых клеток противоположные края решетки клеточ­ных автоматов отождествляются, одномерные клеточные автоматы можнопредставлять в виде набора ячеек памяти, объединенных в кольцо (см.рис. 2.1).Рис. 2.1. Решетка ячеек памяти одномерного клеточного автоматаОдномерным булевым клеточным автоматом с размером решетки X,радиусом локальности г, окрестностью "%.

и локальной функцией связи /называется клеточный автоматC(Z2,X,VrJ),описываемый автономным конечным автоматомАс (S, s0, F),в котором:-75-- S = Ъ§ — множество внутренних состояний;- so £ S — начальное состояние;- F : S —>• S — функция переходов.Внутреннее состояние описывается набором s = [mo, m i , . . . , m^-i]Действие функции F заключается в применении локальной функции связик окрестности каждой ячейки клеточного автомата:TnXtt+i = fi^rim^t)),0^х<Х.2.1.1.2. Д В У М Е Р Н Ы Е БУЛЕВЫ К Л Е Т О Ч Н Ы Е АВТОМАТЫВ основе двумерных булевых клеточных автоматов лежит двумернаяпрямоугольная решетка двоичных ячеек памяти (со значениями из множе­ства Z 2 ).Для данного типа клеточных автоматов также выполняются свойствалокальности и однородности (см.

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

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