Модули сигнатурного мониторинга на клеточных автоматах - Коммуникации, связь, цифровые приборы и радиоэлектроника дипломная работа

Главная

Коммуникации, связь, цифровые приборы и радиоэлектроника
Модули сигнатурного мониторинга на клеточных автоматах

Основные понятия теории клеточных автоматов. Анализ подходов встроенного самотестирования цифровых схем. Модули сигнатурного мониторинга на сетях клеточных автоматов. Программа моделирования одномерной сети клеточных автоматов на языке Borland Delphi.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


БИС - микросхема большой степени интеграции
ГПП - генератор псевдослучайной последовательности
КЛБ - конфигурируемый логический блок
МаБИС - матричная микросхема большой степени интеграции
ОЗУ - оперативное запоминающее устройство
ПЗУ - постоянное запоминающее устройство
ПКН - покрытие константных неисправностей
ПЛИС - программируемая логическая интегральная схема
ПМЛЭ - программируемая матрица логических элементов
ППЗУ - перепрограммируемое постоянное запоминающее устройство
СБИС - микросхема сверхбольшой степени интеграции
СП - синхронизирующая последовательность
СРЛОС - сдвиговый регистр с линейной обратной связью
ЦОП - циклическая отличительная последовательность
CPLD - Complex Programable Logic Devices
FPGA - Field Programable Gate Array
Стремительный рост сложности современных систем управления технологическими процессами и оборудованием вызывает необходимость решения многих проблем, среди которых важное место занимают вопросы обеспечения необходимого уровня отказоустойчивости, работоспособности, продуктивности и быстрой адаптации к классу решаемых задач. Одним из эффективных путей достижения высоких показателей надежности систем управления на основе микроконтроллеров является введение аппаратной, программной и временной избыточности, которые обеспечивают отказоустойчивость в случае присутствия дефектов определенного класса.
Развитие субмикронных технологий, широкое применение сигнальных процессоров, микроконтроллеров и программируемых интегральных схем с числом выходов, которое достигает 1000 на одну микросхему, которые функционируют на тактовой частоте 1ч5 ГГц, приводит к значительному увеличению стоимости диагностирующего оборудования на всех этапах жизни управляющих систем. Существующие системы диагностического обеспечения дискретных устройств и систем на одном кристалле, подсистемы генерации тестов и моделирования неисправностей в большинстве случаев ориентированы на выявление класса неисправностей константного типа, что неадекватно отображает множество дефектов в субмикронной технологии.
Учитывая особенности субмикронных технологий производства интегральных схем, условия эксплуатации управляющих систем в рамках жестких ценовых и временных условий, необходимо объединить методы функциональной и тестовой диагностики и реализовать их в виде программно-аппаратных модулей сигнатурного мониторинга, встроенных на кристалл.
В связи с этим, разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга на клеточных автоматах является актуальной проблемой, учитывая их экономичность и высокую производительность.
1 . О сновные понятия теории клеточных автоматов
Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей [1]. Назовём дискретным пространством пространство над дискретным множеством [2] элементов. Экземпляр пространства этого класса будем называть решёткой клеточного автомата, а каждый его элемент - клеткой. Каждая клетка характеризуется определённым значением из некого множества. О клетке говорят, что она содержит или имеет соответствующее значение, либо находится или пребывает в состоянии, кодируемом данным значением. Оно можем быть булевым, целым, числом с плавающей точкой, множеством или другим объектом, в зависимости от потребностей задачи.
Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с некоторым законом, который называется правилами клеточного автомата. Каждое изменение состояния решётки называется итерацией. Время в рассматриваемой модели дискретно и каждая итерация соответствует некому моменту времени.
Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий момент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточном автомате говорят, что он является автоматом с клетками с памятью, иначе - автоматом с клетками без памяти.
Множество клеток, влияющих на значение данной, за исключением её самой, называется окрестностью клетки. Окрестность клетки удобнее задавать, если на решётке ввести метрику, поэтому далее, для удобства, будем говорить о решётке, как о дискретном метрическом пространстве.
Приведём пример клеточного автомата, который можно реализовать без использования вычислительной машины. Для этого необходимо взять пачку листов в клетку таких, чтобы при наложении одного листа на другой нижний слегка просвечивал. Кроме того, сетка, делящая лист на клетки, должна быть на каждом листе напечатана на одном и том же месте.
Допустим, что каждая клетка может содержать один бит информации. Это означает, что клетка может, например, быть либо помеченной, либо не помеченной. Пометим какие-либо клетки на первом листе, сформировав тем самым начальное состояние решётки. Для совершения итерации необходимо на первый лист положить второй и слегка обозначить (так, чтобы пометки на нижнем листе все же были видны) на верхнем листе те клетки, которые на предыдущем листе также были помеченными, если среди восьми их ближайших соседей найдутся две или три помеченные клетки. Также легонько обозначьте те клетки, которые на предыдущем листе были пустыми, если среди их соседей найдётся ровно три помеченные клетки.
Когда описанная процедура будет проделана для всех клеток верхнего листа, те из них, которые слегка выделены, можно пометить окончательно. Дальше эту процедуру можно повторять от листа к листу до тех пор, пока хватит терпения.
Таким образом, можно реализовать клеточный автомат «Жизнь», который обладает множеством интересных свойств и любопытнейшей историей [3].
Предложенная модель обладает всеми упомянутые выше необходимыми характеристиками клеточных автоматов. Во-первых, у неё есть решётка, составленная из квадратов. Во-вторых, на решётке определена окрестность. Для каждой клетки она представляет собой множество из восьми непосредственно примыкающих к ней соседей. В-третьих, определено множество состояний клетки. В данном случае это - множество эквивалентное множеству из двух элементов («жива», «мертва»). В-четвёртых, описаны правила, обладающие свойством локальности (на каждую клетку влияют только клетки окрестности). В-пятых, автомат работает итерационно. Результат каждой итерации находится на отдельном листе бумаги.
1.2 Основные свойства классической модели клеточных автоматов
Отметим основные свойства классической модели клеточных автоматов.
1 Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама.
2 Однородность системы. Ни одна область решётки не может быть отличена от другой по каким-либо особенностям ландшафта, правил и т.п. Однако на практике решётка оказывается конечным множеством клеток (ведь не возможно выделить неограниченный объём данных).
В результате могут иметь место краевые эффекты, клетки стоящие на границе решётки будут отличны от остальных по числу соседей. Во избежание этого можно ввести краевые условия, завернуть решётку в тор или, например, лист Мёбиуса.
3 Множество возможных состояний клетки - конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций.
4 Значения во всех клетках меняются единовременно, в конце итерации, а не по мере вычисления. В противном случае порядок перебора клеток решётки, при совершении итерации, существенно влиял бы на результат. Необходимо отметить, что на практике, при решении определённых задач, возникает потребность в том, чтобы отказаться от последних трёх свойств.
Поэтому выше было оговорено, что это - свойства «классических» клеточных автоматов.
Клеточный автомат (КА) может быть описан с помощью определения следующих основных свойств: окрестности, количества состояний КА, функции, с помощью которой клеточный автомат вычисляет свое последующее состояние (в дальнейшем - правило). Варьируя эти свойства можно получить широкий спектр КА.
В данной работе рассматривается одномерная сеть клеточных автоматов (СКА), любой из которых может иметь два состояния "О" или "1" на каждом такте функционирования сети. Окрестность определяется множеством соседних клеток, от состояния которых зависит последующее состояние данной клетки, а также диапазоном правил, используемых при настройке КА. Впервые определение окрестности было дано Фон Нейманом [4]. Окрестность Фон Неймана включает наиболее близко расположенные физически соседние клетки.
Рассмотрим клеточные автоматы с двумерными решётками из правильных многоугольников, которые встречаются на практике чаще всего. Возможны всего три таких решётки: треугольная (рис. 1.1), квадратная (рис. 1.2) и гексагональная (рис. 1.3). Ниже последнее утверждение будет доказано
Рисунок 1.1 - Треугольная решетка клеточного автомата
Рисунок 1.2 - Квадратная решетка клеточного автомата
Рисунок 1.3 - Гексагональная решетка клеточного автомата
Теорема 1. Не существует другой решётки из правильных многоугольников, кроме треугольной, квадратной и гексагональной.
Сумма углов правильного n-угольника . Тогда - величина каждого угла этого n-угольника. Пусть из правильных n-угольников удалось составить решётку. Тогда в ней угол в 2р радиан составляют углы целого числа (обозначим его k) фигур. То есть, k многоугольников можно составить так, чтобы они имели общую вершину. Найдём это k, как функцию от n. Это можно сделать из следующего уравнения:
Будем рассматривать эту функцию только при n?3, так как треугольник - многоугольник с наименьшим количеством вершин. Возьмем производную от k(n) по n:
Очевидно, что при n?3 функция k(n) убывает, так как . Таким образом, все возможные значения k меньше k(3), то есть шести. К тому же, k(n) > 2, так как
Решётку можно построить, только если целому n будет соответствовать целое k. Из изложенного выше следует, что возможны лишь четыре значения k: 6, 5, 4 и 3. Построим функцию n(k), обратную к k(n), и проверим, каким из возможных значений k соответствует целое n:
- не целое n, то есть решётку не построить;
Таким образом, действительно возможны только три перечисленные выше решётки из правильных многоугольников. В нашем случае, окрестность Фон Неймана включает три соседние клетки. В дальнейшем, если рассматривается СКА без специально определенных свойств, имеется в виду одномерная СКА, состоящая из КА, которые имеют два состояния, с взаимосвязями между клетками, определенными для окрестности Фон Неймана.
На рис. 1.4 показана структура одномерной линейной СКА, длинны n, с нулевыми граничными условиями.
Рисунок 1.4 - Одномерная n-клеточная СКА с нулевыми граничными условиями
Каждая ячейка СКА - КА, имеющий два состояния, структура которого представлена на рис. 1.5.
Ячейка состоит из двух основных блоков: элемента памяти на триггере типа D и комбинационной схемы, реализующей функцию возбуждения триггера F. Обозначим текущее состояние i-й ячейки СКА в момент времени t как , тогда последующее состояние определяется выражением:
где F - функция возбужден ил триггера, называемая правилом поведения клеточного автомата.
Правило может быть представлено и виде логической функции, либо таблицей истинности, либо как десятичный эквивалент двоичного числа (0...255), образуемого значениями функции и таблице истинности. В таблице 2.1 представлен пример численного значения правила
Таблица 1.1 - Пример вычисления численного значения правила
Аналогично вычисляется численное значение для любого правила.
Правило функционирования КА может быть записано в виде булевого выражения. Например, для правила 144, соответствующее выражение будет иметь вид:
где 'x' и '+' операции конъюнкции и дизъюнкции соответственно.
Определение 1. Диаграмма состояний КА.
Диаграмма состояний КА с двумя состояниями представляет собой вектор-столбец, состоящий из нулей и единиц. Обозначим состояние i-й ячейки в момент времени t - , тогда диаграмма состояний i-клетки за m-шагов может быть записана в виде:
где Т - оператор транспонирования матрицы
Определение 2. Диаграмма состояний ячейки СКА.
Диаграмма состояний ячейки, входящей в состав одномерной СКА записывается в виде матрицы, состоящей из трех столбцов (Хi-1, Xi, Xi+1). Хi - диаграмма на выходе интересующей ячейки, а Хi-1, Xi+1 - диаграммы на выходах левой и правой ячеек соответственно.
Определение 3. Диаграмма состояний СКА.
Диаграмма состояний СКА длины n может быть записана в виде совокупности из n триплет
Каждая совокупность из трех столбцов (Хi-1, Хi Хi+1) представляет диаграмму состояний i-й ячейки сети. Нужно заметить, что столбцы Х0 и Хn+1 - это столбцы, состоящие из нулей. Эти столбцы соответствуют нулевым граничным условиям.
Определение 4. Детерминизм правил КА.
В данной работе рассматриваются только детерминированные правила. Это значит, что любая пара идентичных состояний окрестности КА приводит его в одно и тоже последующее состояние.
Обозначим состояние окрестности i-й ячейки СКА на шаге t, как
Рассмотрим состояние i - ячейки СКА на шаге tj и tk, tj?tk, если
Вышеприведенное выражение дает возможность определить, является ли двоичная последовательность, состоящая из трех столбцов, частью диаграммы состояний ячейки СКА.
Определение 5. Универсальная окрестность.
где F представляет правило функционирования КА, а - это состояние окрестности i-й ячейки СКА в момент времени t. Параметр r - это положительное целое число, характеризующее размер окрестности, а, следовательно, и диапазон правил КА [5].
Универсальная окрестность, , ячейки xi, в одномерной СКА длинны n, может быть представлена в следующем виде:
Таким образом, окрестность Фон Неймана является частным случаем универсальной окрестности.
На рис. 1.6 показаны два варианта окрестности с г = 1 и г = 2. Как можно заметить, при r =1, на последующее состояние ячейки влияет три переменные, а при r =2 - пять.
Рисунок 1.6 - Универсальная окрестность с r=1 и r=2
Окрестность определяется диапазоном правил КА [6] в зависимости от параметра r следующим образом , где (2r+1) - количество соседних с рассматриваемой ячеек, участвующих в вычислении последующего.
Окрестность Фон Неймана, рассматриваемая в данной работе, позволяет использовать =256 правил. Этот класс КА называют "элементарный КА Вольфрама" [6].
Диаграмма состояний ячейки СКА с универсальной окрестностью состоит из совокупности (2г+1) столбцов (Хi-r,...,Xi,… Xi+r), где - диаграмма состояний КА. При этом столбцы (X-r+1, X-r+2,…, X0) и (Xn+1, Xn+2,…, Xn+r) обеспечивают заданные граничные условия.
Увеличение r > 1 и, следовательно, расширение окрестности влечет за собой ряд проблем, одна из которых состоит в кодировании правил, возможное число которых значительно возрастает, в этом случае правила рассматриваются в виде таблицы истинности и соответствующей логической функции. Кроме того, из-за такого расширения окрестности значительно усложняется проектирование СКА с заданными свойствами.
Определение 6. Детерминированность субпоследовательности.
Детерминированность для субпоследовательности S, состоящей из k строк, длины n, на основании (2.1) можно сформулировать следующим образом:
пусть - i-й элемент строки t, тогда субпоследовательность (СП) детерминирована, если
1.4 Моделирование физических процессов
Каждый клеточный автомат, это - некий мир, живущий по определённым законам. Жизнь его, как замкнутой системы, бесцельна. Время идет, он меняется, но сам по себе он не в силах понять, зачем это нужно и как долго это ещё будет продолжаться. Существование мира обретает смысл, когда кто-то смотрит на него из другого мира и делает определённые выводы из процесса его эволюции.
Клеточные автоматы можно рассматривать не как замкнутые в себе миры, а как миры-генераторы определённых выходных сигналов, в ответ на входные, предоставляя, тем самым, внешнему миру дополнительные рычаги управления и дополнительную информацию о поведении автомата. Такие клеточные автоматы получили название автоматов-трансдюсеров, то есть - преобразователей входных сигналов в выходные.
Как уже отмечалось выше, одной из основных областей применения клеточных автоматов является создание физических, биологических, химических и прочих моделей.
Клеточный автомат является аналогом понятия поля и оказывается идеальной средой для решения дифференциальных уравнений и уравнений в частных производных, например, уравнения Навье-Стокса, уравнения теплопроводности и волнового уравнения. Дифференциальные уравнения описывают непрерывные динамические системы, а клеточные автоматы, как было сказано выше, также являются динамическими системами, но дискретными. Они представляют собой простые, удобные и точные модели макро и микромира, эволюционных процессов, динамики жидкостей, турбулентности, фрактальности, хаотичности, упорядоченья и т.д.
Часто задавался вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не некие аспекты их проявления в природе. Камнем преткновения стал вопрос обратимости пути развития, основного свойства микроскопической физики. При решении такого рода задач решётка становится пространством для моделирования некой среды.
Пусть на рис. 1.7 изображено некое вещество. В задаче существенен какой-то его параметр. Зоны, обладающие одинаковым значением этого параметра, выделены одним и тем же цветом. Чтобы решать задачу численно необходимо как-то описать для машины исследуемый материал, сообщить распределение значений параметра. Для этого следует произвести дискретизацию, заменить непрерывный массив данных конечным числом информативных значений.
Наложим на вещество решётки, составленные из квадратов и шестиугольников. В каждую клетку поместим значение, соответствующее той зоне материала, которую она охватывает.
Если это - некий числовой параметр, то в ячейку можно записать его среднее значение по всем точкам, охватываемым клеткой или, как в настоящем примере, значение, которым обладает большинство точек, охватываемых ею. Возможны и другие способы определения значения, которое следует поместить в клетку, соответствующую некой области среды.
Рис 1.7 - Дискретизация на примере квадратной и гексагональной решёток
Основной интерес со стороны специалистов области компьютерных наук к клеточным автоматам обусловлен тем, что они образуют парадигму параллельных вычислений подобно тому, как машина Тьюринга образуют парадигму последовательных. Таким образом, они могут использоваться, как модели, обладающие естественным параллелизмом.
Одно из главных отличий клеточной системы от всех прочих вычислительных систем состоит в том, что во всех других системах присутствуют две принципиально различные части: архитектурная, которая фиксирована и активна (то есть выполняет некоторые операции) и данные, которые переменны и пассивны (то есть сами по себе они ничего сделать не могут). У клеточных автоматов и та, и другая части состоят из принципиально изоморфных, неотличимых друг от друга элементов.
Таким образом, вычислительная система может оперировать своей материальной частью, модифицировать, расширять себя и строить себе подобных [1]. Хотя системы этого класса и были придуманы Джоном фон Нейманом, такая параллельная архитектура получила название «не-фон-неймановской», так как последовательную архитектуру он создал раньше.
Данное утверждение может показаться спорным. Казалось бы, к архитектурной части логичнее отнести, например, решётку и правила. Однако это, скорее - аппаратная часть.
Например, рассмотрим автомат, реализующий игру «Жизнь». При данных решётке и правилах, меняя лишь состояние решётки, можно реализовать универсальные вычислительные системы, позволяющие производить любые вычисления, которые, по своим выразительным способностям эквивалентны произвольным машинам Тьюринга и клеточным автоматам [7]. Теми же возможностями обладает, в частности, автомат, называемый компьютером Бэнкса [1]. Однако использовать их крайне неэффективно, но с теоретической точки зрения это - важный результат.
Наверное, наиболее известным из них можно считать клеточный автомат под названием игра «Жизнь». Создана игра «Жизнь» была в 1970 году Джоном Хортоном Конуэем, математиком Кембриджского университета. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колонии живых организмов. По этой причине «Жизнь» можно отнести к быстро развивающиеся в наши дни категории игр, имитирующих процессы, происходящие в живой природе.
Рассматривается бесконечная плоская решётка квадратных ячеек-клеток. Время в этой игре дискретно (t=0, 1, 2, ...). Клетка может быть живой или мёртвой. Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t (соседей у клетки восемь, четверо имеют с ней общие ребра, а четверо только вершины).
Основная идея состоит в том, чтобы, начав с некоего расположения клеток, проследить за эволюцией исходной позиции под действием «генетических законов» Конуэя, которые управляют рождением, гибелью и выживанием клеток.
Конуэй тщательно подбирал свои правила и долго проверял их на «практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:
1. Не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции.
2. В то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться.
3. Должны существовать простые начальные конфигурации, которые в течении значительного промежутка времени растут, претерпевают различные изменения и заканчивают свою эволюцию одним из следующих трёх способов: полностью исчезают (либо из-за перенаселенности, то есть слишком большой плотности живых клеток, либо наоборот, из-за разреженности клеток, образующих конфигурацию); переходят в устойчивую конфигурацию и перестают изменяться вообще или же, наконец, выходят на колебательный режим, то есть бесконечный цикл превращений с определенным периодом.
Следствием этих требований явились следующие правила игры «Жизнь»:
1. Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.
2. Гибель. Каждая клетка, у которой больше трёх соседей, погибает из-за перенаселённости. Каждая клетка, вокруг которой свободны все соседние клетки или же занята всего одна клетка, погибает от одиночества.
3. Рождение. Если число занятых клеток, с которыми граничит какая-нибудь пустая клетка, в точности равно трём, то на этой клетке происходит рождение нового организма.
Какие основные типы структур (то есть конфигураций, определяющих поведение сообществ на больших временах) могут существовать в такой системе?
Каковы здесь законы организации структур?
Могут ли они взаимодействовать, и к чему это приводит? Выясним, какие закономерности являются следствиями представленных выше правил. Первая закономерность - свойство локализации - структуры, разделенные двумя «мёртвыми» (пустыми) клетками не влияют друг на друга. Вторая закономерность - система клеток, которую описывает игра «Жизнь», развивается необратимо. В самом деле, конфигурация в момент времени t полностью определяет будущее (состояние в моменты t+1, t+2 и так далее). Но восстановить прошлое системы по её настоящему не удаётся. Картина здесь такая же, как в одномерных отображениях, только прообразов у данной конфигурации может быть бесконечно много.
Докажем это утверждение: воспользуемся свойством локализации, расположим вокруг данной конфигурации множество локализованных одиночных клеток или их пар так, чтобы они не влияли на неё и друг на друга. Понятно, что все они исчезнут на следующем шаге, никоим образом не повлияв на будущее системы.
Здесь мы можем заметить признаки нелинейных диссипативных структур: эти структуры определяли поведение системы при t стремящемся к бесконечности в случае различных начальных данных. Третья закономерность - как показывают длительные наблюдения за процессом развития колоний, конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретённые свойства симметрии в процессе дальнейшей эволюции не утрачиваются, симметрия конфигурации может лишь обогащаться.
Условимся классифицировать конфигурации клеток по следующим параметрам:
1. По количеству клеток в комбинации: единичная клетка, дуплет (2 клетки в комбинации), триплет (3 клетки) и т.д.
2. По перспективе развития: развивающиеся (неограниченный рост), стабильные (количество клеток в популяции колеблется около какого-то среднего значения), вымирающие (популяция стабильно уменьшается), периодические (количество клеток принимает несколько фиксированных значений через определенный период).
Теперь рассмотрим типичные структуры, появляющиеся в игре «Жизнь». Простейшими являются стационарные, то есть не зависящие от времени структуры (сам Конуэй называет их «любителями спокойной жизни»). Их примеры показаны на рис 1.8. С помощью этих стационарных структур можно получить множество других. В самом деле, если мы имеем такую структуру, то конфигурация, полученная поворотом на 900, также будет стационарной. Конфигурации в нижних рядах показывают, как можно достраивать определённые структуры до любых размеров. Используя свойство локализации можно строить «большие» стационарные структуры из «малых» - элементарных.
Рисунок 1.8 - Примеры стационарных структур, реализующихся в игре «Жизнь»
Можно считать, что стационарные структуры повторяют себя на каждом шаге по времени. Но есть и другие конфигурации, повторяющие себя через N шагов, так называемые N-циклы (периодические структуры). При эволюции различных сообществ часто встречается 2-цикл, называемый «семафором». Однако эффективные алгоритмы, позволяющие строить различные конфигурации с данным периодом N, по-видимому, в настоящее время не созданы. Эволюция взятых наугад начальных данных часто приводит к возникновению простейших локализованных структур (показанных на рис. 1.8) и семафоров. Однако возможны и более сложные типы эволюции, например, когда сообщество клеток симметрично «достраивается», и возникают циклы большого периода, имеющие сложную форму.
В игре «Жизнь» существуют конфигурации, которые могут передвигаться по плоскости. Одной из них является «планер» (или «глайдер») - конфигурация из 5 клеток (рис. 1.9)
Планер (глайдер) - перемещающаяся конфигурация из 5 клеток. После второго хода планер немного сдвигается и отражается относительно диагонали. В результате двух последующих ходов планер «выходит из пике», ложится на прежний курс и сдвигается на одну клетку вправо и одну клетку вниз относительно начальной позиции. Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет «скоростью света». Выбор Конуэя пал именно на этот термин из-за того, что в изобретённой им игре большие скорости просто не достигаются.
Ни одна конфигурация не воспроизводит себя достаточно быстро, чтобы двигаться с такой скоростью. Конуэй доказал, что максимальная скорость на диагонали составляет одну четверть скорости света. Поскольку планер переходит сам в себя после четырёх ходов и при этом опускается на одну клетку по диагонали, то говорят, что он скользит по полю со скоростью, равной одной четвертой скорости света. Конуэй также показал, что скорость любой конечной фигуры, перемещающейся по вертикали или по горизонтали на свободные клетки, не может превышать половину скорости света. Скорость движения равна дроби, в числителе которой стоит число ходов, необходимых для воспроизведения фигуры, а в знаменателе - число клеток, на которое она при этом смещается. Понятно, что в силу симметрии есть планеры, распространяющиеся вдоль любой диагонали квадрата в обоих направлениях.
Впрочем, некоторые конфигурации могут передвигаться не вдоль диагоналей, а по вертикальным и горизонтальным прямым.
Более сложным образом конструируются другие элементы. Для анализа ситуаций, возникающих в игре «Жизнь», применяется компьютер.
В программе, моделирующей этот клеточный автомат, используется квадратная матрица, которая и является полем для игры. При смене хода анализируется каждый элемент старой матрицы и строится на её основе новая, которая соответствует конфигурации на следующем шаге эволюции. Для более детального исследования игра Конуэя расширена на несколько популяций, каждая из которых развивается по своим правилам. Правила для каждой популяции выбираются из следующих:
1. Условия рождения и смерти. Задаются четыре параметра (параметры можно менять в процессе игры): минимальное и максимальное количество соседей своей популяции, при котором рождается клетка; минимальное и максимальное количество соседей, при котором клетка выживает и переходит в следующее поколение.
2. Соседями клетки могут быть любые клетки, находящиеся в квадрате 3х3 с центром в данной клетке.
Игра «Жизнь» нашла свое применение в биологии как игра «Аква-Тор», которая моделирует поведение системы, состоящей из двух популяций, условно называемых «травоядные» и «хищники».
2 . А нализ существующих программных и аппаратных реализаций КА
2.1 Программная реализация КА на IBM PC
Для решения задач с помощью клеточных автоматов требуется большой объём памяти для хранения значений из клеток решётки.
Однако, взаимодействие переменных, соответствующих клеткам локально. В то время как в большинстве программ, как правило, вводится не столь большое количество переменных, которые влияют друг на друга произвольным образом.
При проведении эксперимента на клеточном автомате, необходимо производить огромное количество итераций. В работе [9] приводятся следующие данные: для получения удовлетворительных результатов решения прикладной задачи зачастую требуется выполнить порядка 1015 обновлений клеток. По чрезвычайно оптимистичной оценке, обновление клетки, при моделировании работы клеточного автомата на персональном компьютере с архитектурой IBM PC i386, может
Модули сигнатурного мониторинга на клеточных автоматах дипломная работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Курсовая Работа Синергия Менеджмент
Сочинение По Истории Ленин
Дипломная Работа На Тему Палестино–Израильский Конфликт В Контексте Истории
Что Такое Счастье Своими Словами Кратко Сочинение
Дипломная работа по теме Производство о применении принудительных мер медицинского характера
Сочинение На Тему Русский На 5
Сочинение Про Осень На Кабардинском Языке
Реферат: История развития искусства в начале XX века. Модерн в России
Реферат На Тему Развитие Речи Ребенка
Реферат: Модели систем массового обслуживания. Классификация систем массового обслуживания. Скачать бесплатно и без регистрации
Реферат по теме АСУ в легкой промышленности
5 Класс Контрольная Работа Треугольники
Курсовая Разница По Мсфо 21
Реферат: Задачи по экологическому праву
Курсовая работа: Инфраструктура. Скачать бесплатно и без регистрации
Чехов Собрание Сочинений В Томах Купить
Почвообрабатывающие Машины Реферат
Контрольная Работа Вариант 4 6 Класс
Написать Сочинение Век Нынешний И Век Минувший
Сочинение На Тему Трудные Случаи Правописания
Комплексная географическая характеристика Ставропольского края - География и экономическая география реферат
Гарантии и защита прав местного самоуправления - Государство и право контрольная работа
Анализ компонентов системы передачи Е1 - Коммуникации, связь, цифровые приборы и радиоэлектроника реферат