Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Перечень обозначений и сокращений

БВВ - блок ввода/вывода

БИС - микросхема большой степени интеграции

ГПП - генератор псевдослучайной последовательности

ДУ - дискретное устройство

ДЭ - диагностический эксперимент

КА - клеточный автомат

СКА - сеть клеточных автоматов

КЛБ - конфигурируемый логический блок

МаБИС - матричная микросхема большой степени интеграции

ОЗУ - оперативное запоминающее устройство

ОС - однородная сеть

ПЗУ - постоянное запоминающее устройство

ПКН - покрытие константных неисправностей

ПЛИС - программируемая логическая интегральная схема

ПМЛЭ - программируемая матрица логических элементов

ППЗУ - перепрограммируемое постоянное запоминающее устройство

СБИС - микросхема сверхбольшой степени интеграции

СП - синхронизирующая последовательность

СРЛОС - сдвиговый регистр с линейной обратной связью

ЦОП - циклическая отличительная последовательность

CPLD - Complex Programable Logic Devices

FPGA - Field Programable Gate Array

Введение

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

Развитие субмикронных технологий, широкое применение сигнальных процессоров, микроконтроллеров и программируемых интегральных схем с числом выходов, которое достигает 1000 на одну микросхему, которые функционируют на тактовой частоте 1ч5 ГГц, приводит к значительному увеличению стоимости диагностирующего оборудования на всех этапах жизни управляющих систем. Существующие системы диагностического обеспечения дискретных устройств и систем на одном кристалле, подсистемы генерации тестов и моделирования неисправностей в большинстве случаев ориентированы на выявление класса неисправностей константного типа, что неадекватно отображает множество дефектов в субмикронной технологии.

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

В связи с этим, разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга на клеточных автоматах является актуальной проблемой, учитывая их экономичность и высокую производительность.

1. Основные понятия теории клеточных автоматов

1.1 Основные определения и понятия

Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей [1]. Назовём дискретным пространством пространство над дискретным множеством [2] элементов. Экземпляр пространства этого класса будем называть решёткой клеточного автомата, а каждый его элемент - клеткой. Каждая клетка характеризуется определённым значением из некого множества. О клетке говорят, что она содержит или имеет соответствующее значение, либо находится или пребывает в состоянии, кодируемом данным значением. Оно можем быть булевым, целым, числом с плавающей точкой, множеством или другим объектом, в зависимости от потребностей задачи.

Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с некоторым законом, который называется правилами клеточного автомата. Каждое изменение состояния решётки называется итерацией. Время в рассматриваемой модели дискретно и каждая итерация соответствует некому моменту времени.

Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий момент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточном автомате говорят, что он является автоматом с клетками с памятью, иначе - автоматом с клетками без памяти.

Множество клеток, влияющих на значение данной, за исключением её самой, называется окрестностью клетки. Окрестность клетки удобнее задавать, если на решётке ввести метрику, поэтому далее, для удобства, будем говорить о решётке, как о дискретном метрическом пространстве.

Приведём пример клеточного автомата, который можно реализовать без использования вычислительной машины. Для этого необходимо взять пачку листов в клетку таких, чтобы при наложении одного листа на другой нижний слегка просвечивал. Кроме того, сетка, делящая лист на клетки, должна быть на каждом листе напечатана на одном и том же месте.

Допустим, что каждая клетка может содержать один бит информации. Это означает, что клетка может, например, быть либо помеченной, либо не помеченной. Пометим какие-либо клетки на первом листе, сформировав тем самым начальное состояние решётки. Для совершения итерации необходимо на первый лист положить второй и слегка обозначить (так, чтобы пометки на нижнем листе все же были видны) на верхнем листе те клетки, которые на предыдущем листе также были помеченными, если среди восьми их ближайших соседей найдутся две или три помеченные клетки. Также легонько обозначьте те клетки, которые на предыдущем листе были пустыми, если среди их соседей найдётся ровно три помеченные клетки.

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

Таким образом, можно реализовать клеточный автомат «Жизнь», который обладает множеством интересных свойств и любопытнейшей историей [3].

Предложенная модель обладает всеми упомянутые выше необходимыми характеристиками клеточных автоматов. Во-первых, у неё есть решётка, составленная из квадратов. Во-вторых, на решётке определена окрестность. Для каждой клетки она представляет собой множество из восьми непосредственно примыкающих к ней соседей. В-третьих, определено множество состояний клетки. В данном случае это - множество эквивалентное множеству из двух элементов («жива», «мертва»). В-четвёртых, описаны правила, обладающие свойством локальности (на каждую клетку влияют только клетки окрестности). В-пятых, автомат работает итерационно. Результат каждой итерации находится на отдельном листе бумаги.

1.2 Основные свойства классической модели клеточных автоматов

Отметим основные свойства классической модели клеточных автоматов.

1 Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама.

2 Однородность системы. Ни одна область решётки не может быть отличена от другой по каким-либо особенностям ландшафта, правил и т.п. Однако на практике решётка оказывается конечным множеством клеток (ведь не возможно выделить неограниченный объём данных).

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

3 Множество возможных состояний клетки - конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций.

4 Значения во всех клетках меняются единовременно, в конце итерации, а не по мере вычисления. В противном случае порядок перебора клеток решётки, при совершении итерации, существенно влиял бы на результат. Необходимо отметить, что на практике, при решении определённых задач, возникает потребность в том, чтобы отказаться от последних трёх свойств.

Поэтому выше было оговорено, что это - свойства «классических» клеточных автоматов.

1.3 Двумерный клеточный автомат

Клеточный автомат (КА) может быть описан с помощью определения следующих основных свойств: окрестности, количества состояний КА, функции, с помощью которой клеточный автомат вычисляет свое последующее состояние (в дальнейшем - правило). Варьируя эти свойства можно получить широкий спектр КА.

В данной работе рассматривается одномерная сеть клеточных автоматов (СКА), любой из которых может иметь два состояния "О" или "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.

Рисунок 1.5 - Структура КА

Ячейка состоит из двух основных блоков: элемента памяти на триггере типа D и комбинационной схемы, реализующей функцию возбуждения триггера F. Обозначим текущее состояние i-й ячейки СКА в момент времени t как , тогда последующее состояние определяется выражением:

где F - функция возбужден ил триггера, называемая правилом поведения клеточного автомата.

Правило может быть представлено и виде логической функции, либо таблицей истинности, либо как десятичный эквивалент двоичного числа (0...255), образуемого значениями функции и таблице истинности. В таблице 2.1 представлен пример численного значения правила

Таблица 1.1 - Пример вычисления численного значения правила

	111	110	101	100	011	010	001	000
Правило 144	1	0	0	1	0	0	0	0
Правило 65	0	1	0	0	0	0	0	1
Степень 2	7	6	5	4	3	2	1	0

Правило 144 = 27 + 24

Правило 65 = 26 + 21

Аналогично вычисляется численное значение для любого правила.

Правило функционирования КА может быть записано в виде булевого выражения. Например, для правила 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, как

(1.1)

Рассмотрим состояние i - ячейки СКА на шаге tj и tk, tj?tk, если

(1.2)

Вышеприведенное выражение дает возможность определить, является ли двоичная последовательность, состоящая из трех столбцов, частью диаграммы состояний ячейки СКА.

Определение 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]. Однако использовать их крайне неэффективно, но с теоретической точки зрения это - важный результат.

1.5 Игра «Жизнь»

Наверное, наиболее известным из них можно считать клеточный автомат под названием игра «Жизнь». Создана игра «Жизнь» была в 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)

Рисунок 1.9 - Планер

Планер (глайдер) - перемещающаяся конфигурация из 5 клеток. После второго хода планер немного сдвигается и отражается относительно диагонали. В результате двух последующих ходов планер «выходит из пике», ложится на прежний курс и сдвигается на одну клетку вправо и одну клетку вниз относительно начальной позиции. Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет «скоростью света». Выбор Конуэя пал именно на этот термин из-за того, что в изобретённой им игре большие скорости просто не достигаются.

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

Впрочем, некоторые конфигурации могут передвигаться не вдоль диагоналей, а по вертикальным и горизонтальным прямым.

Более сложным образом конструируются другие элементы. Для анализа ситуаций, возникающих в игре «Жизнь», применяется компьютер.

В программе, моделирующей этот клеточный автомат, используется квадратная матрица, которая и является полем для игры. При смене хода анализируется каждый элемент старой матрицы и строится на её основе новая, которая соответствует конфигурации на следующем шаге эволюции. Для более детального исследования игра Конуэя расширена на несколько популяций, каждая из которых развивается по своим правилам. Правила для каждой популяции выбираются из следующих:

1. Условия рождения и смерти. Задаются четыре параметра (параметры можно менять в процессе игры): минимальное и максимальное количество соседей своей популяции, при котором рождается клетка; минимальное и максимальное количество соседей, при котором клетка выживает и переходит в следующее поколение.

2. Соседями клетки могут быть любые клетки, находящиеся в квадрате 3х3 с центром в данной клетке.

Игра «Жизнь» нашла свое применение в биологии как игра «Аква-Тор», которая моделирует поведение системы, состоящей из двух популяций, условно называемых «травоядные» и «хищники».

2. Анализ существующих программных и аппаратных реализаций КА

2.1 Программная реализация КА на IBM PC

Для решения задач с помощью клеточных автоматов требуется большой объём памяти для хранения значений из клеток решётки.

Однако, взаимодействие переменных, соответствующих клеткам локально. В то время как в большинстве программ, как правило, вводится не столь большое количество переменных, которые влияют друг на друга произвольным образом.

При проведении эксперимента на клеточном автомате, необходимо производить огромное количество итераций. В работе [9] приводятся следующие данные: для получения удовлетворительных результатов решения прикладной задачи зачастую требуется выполнить порядка 1015 обновлений клеток. По чрезвычайно оптимистичной оценке, обновление клетки, при моделировании работы клеточного автомата на персональном компьютере с архитектурой IBM PC i386, может потребовать несколько микросекунд. Тогда эксперимент займёт тысячелетия!

Машина клеточных автоматов CAM-8

Один из возможных выходов состоит в том, чтобы использовать вычислительные машины со специальной архитектурой. Эти вычислительные машины должны обладать высокой степенью параллелизма, и позволять вычислять единообразные функции, используя значения из окрестных ячеек данных в качестве аргументов. Такая система позволит достигнуть производительности выше на большое число порядков.

Самая известная подобная «машина клеточных автоматов» была разработана в Массачусетском Технологическом Институте (Massachusetts Institute of Technology). Этот проект носит название CAM (Cellular Automation Machine) [9].

Последняя, на данный момент, версия этого продукта CAM-8 [1, 9] представляет собой устройство, подключаемое к компьютеру с архитектурой IBM PC i386 и работающее под его управлением. В частности машине необходима видеосистема персонального компьютера для визуализации происходящего при моделировании, а также электропитание, дисковая память и т.д. В обмен машина предоставляет свои вычислительные возможности.

Симбиоз получился чрезвычайно выгодным. Устройства CAM нашли широкое применение во многих научно-исследовательских институтах всего мира в качества экспериментальной лаборатории благодаря чудесной производительности и весьма низкой цене.

Существуют и многочисленные программные имитаторы универсальных клеточных автоматов общего назначения. Весьма удачный проект, который впоследствии и перерос в CAM, был реализован Томазо Тоффоли (Tommaso Toffoli) и его соавторами [1]. Конечно, они очень существенно уступают аппаратным реализациям, однако вычислительные возможности персональных компьютеров постоянно растут и они несравнимо распространённее и доступнее, чем специализированные устройства.

3. Анализ подходов встроенного самотестирования однородных сетей

Существует два основных подхода встроенного самотестирования, которые применяются к цифровым схемам:

детерминированный подход;

3.1 Псевдослучайный подход. Детерминированное тестирование

Согласно детерминированному подходу, в схеме находится генератор определенных тестовых последовательностей и гарантируется определенное покрытие неисправностей, основанное на принятой модели неисправности.

3.1.1 Основные определения и понятия

Для правильного и подробного описания этого подхода необходимо ввести основные определения и понятия.

В качестве абстрактной модели дискретного устройства (ДУ) с памятью будем использовать автомат Мили, определяемый пятеркой

А = ( X, Y, Z, , ), (3.1)

где X = { X1, X2,…., Xm } - множество букв входного алфавита;

Z = { Z1, Z2,…, Zn } - множество состояний автомата;

Y = { Y1 , Y2, …Yr } - множество букв выходного алфавита;

Множество функций переходов автомата;

(Zi, Xk) = Zj; Zi, ZjZ; XkX; i, j = ;

k =

Множество функций выхода автомата

(Zi, Xk) = y; yY, =

В дальнейшем изложении будут использоваться следующие обозначения и понятия:

Xj = X1 X2 … Xk - входное слово или входная последовательность из К букв;

l ( Xj ) = k - длина последовательности;

Yj = Y1 Y2 … Yk - выходное слово или выходная последовательность длины l ( Yj ) = k .

Любое конечное множество состояний автомата будем называть -множеством. Элементы, образующие -множество, не обязательно различны. -множество, содержащее единственный элемент, называется простым, а содержащее несколько одинаковых элементов - кратным. -множество, однородно, если все элементы одинаковы.

(Zi, Xj) - выходная последовательность автомата, первоначально находящегося в состоянии Zi и проявляющаяся в результате приложения входной последовательности Xj.

Многие задачи теории автоматов (кодирование состояний, декомпозиция автоматов, минимизация числа состояний и другие) успешно решаются путем анализа разбиений состояний автомата. Термин «разбиение» имеет в математике ряд значений [10]. Вообще, под разбиением принято понимать всякое расчленение целого на части.

Определение 3.1 Пусть В подмножество Z. Разбиением i множества Z называют совокупность таких подмножеств Bi ,что их по парные пересечения - пустые множества, а объединение всех подмножеств Bi равно Z.

Подмножество Bi называют блоком разбиения i множества Z.

Пример 3.1 Пусть Z={A, B, C, D, E, F} . Тогда = {}, ={ },

где - разбиения множества Z .

Говорят, что для пары разбиений , , определенных на множестве Z, разбиение больше или равно разбиению ( , ), если каждый блок разбиения содержится в блоке . Например, разбиение и из примера 3.1 можно упорядочить в виде ..

Разбиение, в котором каждый блок включает один элемент множества Z, является (0) -разбиением, а разбиение, содержащее в одном блоке все элементы Z, является (1) - разбиением.

Определение 3.2 Если 1 и 2 - разбиения множества Z, то произведением разбиений (1 2) является разбиение, полученное в результате пересечения каждого блока из 1 с каждым блоком из 2.

Например, произведение пары разбиений множества из примера 3.1 равно

= {}.

Определение 3.3 Если 1 и 2 - разбиения множества Z, то суммой разбиений (1 + 2) является разбиение, полученное в результате объединения тех блоков 1 и 2 , которые имеют, по меньшей мере, один общий элемент.

Например, сумма пары разбиений множества Z из примера 3.1 равна

1 + 2= { }.

Если известна автоматная модель ДУ с элементами памяти, то задача построения проверяющего эксперимента сводится к нахождению входных и выходных последовательностей, которые позволяют однозначно идентифицировать автоматную диаграмму ДУ [11]. Большинство известных методов решения этой задачи основано на работе Хенни [12]. Предложенный им подход дает хорошие результаты для автоматов, которые имеют отличительные последовательности. Поэтому этот класс автоматов многие исследователи называют легко тестируемым [13]. Известна процедура нахождения отличительной последовательности автомата по его автоматной диаграмме предусматривающая построение дерева преемников автомата и применение определенных правил усечения вершин этого дерева. Процедура завершается, когда, либо найдена отличительная последовательность для заданного автомата, либо в результате построения отличительного дерева установлено, что автомат не имеет отличительной последовательности.

Известно, что необходимым условием существования для данного автомата отличительной последовательности является свойство минимальности автомата. Однако это условие не является достаточным, так как существуют минимальные автоматы, не имеющие отличительных последовательностей.

В этом подразделе определены достаточные условия существования для заданного автомата отличительной последовательности, а также найдены оценки наименьшей верхней и нижней границы длины минимальной отличительной последовательности.

Определение 3.4 Входная последовательность X0 называется отличительной для автомата А=(X, Y, Z, , ), если выходная последовательность автомата, как реакция на X0, различна для любого начального состояния, то есть

( Zi, X0 ) ( Zi, X0 ), для Zi , Zj Z , Zi Zj . (3.2)

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

Отличительное дерево приемников, в котором вершина ранга r является висячей если:

а) ей поставлена в соответствие группа - множеств, содержащая, по меньшей мере, одно кратное - множество;

б) ей поставлена в соответствие группа - множеств, в которой все не простые - множества совпадают с - множествами вершины ранга меньше r;

в) среди вершин ранга r имеется хотя бы одна вершина, отмеченная простым - множеством.

Для иллюстрации воспользуемся примером автомата А-1, заданного таблицей 3.1 переходов-выходов. Отличительное дерево, построенное в соответствии с вышеприведенными правилами усечения дерева преемников, приведено на рисунке 3.1. Каждая вершина отмечена - множествами, полученными в соответствии с правилами построения дерева преемников. Над каждым - множеством в отличительном дереве указаны состояния предшественники, принадлежащие начальному -множеству и порождающие соответствующие им группы - множеств.

Таблица 3.1 - Автомат А-1

Z ( t )	Z ( t + 1 ), ( t )
	X1	X2
1	2, 1	1, 1
2	1, 1	3, 0
3	5, 0	3, 1
4	2, 0	1, 0
5	4, 1	5, 0

Отображение множества допустимых начальных состояний, принадлежащих начальному - множеству, в группы - множеств, которыми отмечены вершины отличительного дерева, полностью определяется функцией переходов-выходов автомата. Например, для автомата А-1 ( { } X1 )= { 2, 1, 4 } , { 5, 2 }. (3.3)

Блоки разбиения 1 ={} множества состояний A-1 определяют отношение эквивалентности состояний в том смысле, что состояния, принадлежащие каждому блоку разбиения 1 X1 - неразличимы, а сами блоки разбиения 1 являются X1 - различимыми. Вершине отличительного дерева (рисунок 3.1), отмеченной разбиением 1 , поставлена в соответствие группа - множеств 1:{2, 1, 4 },{ 5, 2}, включающих состояния, которые являются преемниками соответствующих состояний блоков разбиения 1.

В отличительном дереве автомата A-1 каждому - множеству вершины дерева поставлено в соответствие - разбиение множества начальных состояний, для которых состояния - множеств являются конечными состояниями при приложении к входу автомата последовательности входных символов, соответствующих меткам дуг отличительного дерева. Путь в отличительном дереве от его корня до вершины, отмеченной группой простых -множеств, определяет отличительную последовательность минимальной длины. Отличительная последовательность X0=(X1, X1, X1, X2, X1) автомата А-1 определяет следующую последовательность - разбиений начальных состояний

(1) 1 2 3 3' 4 = (0), (3.4)

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

3.1.2 Установочные последовательности

В первой фазе диагностического эксперимента с автоматом предусматривается установка его в известное начальное состояние. Это достигается использованием установочных или синхронизирующих последовательностей [14, 10]. Методы построения условных и безусловных установочных экспериментов, а также синтез установочных синхронизирующих последовательностей достаточно полно и глубоко изложен в [10]. В этом разделе получена оценка сложности безусловного установочного эксперимента.

Определение 3.5 Входная последовательность Xu называется установочной для автомата ( X, Y, Z, , ), если его конечное состояние (Zi,Xu) может быть однозначно определено по выходной последовательности (Zi , Xu ) для всех Zi Z.

В соответствии с определением 3.5 если автомат исправен и имеет установочную последовательность, то независимо от начального состояния его можно перевести в определенное состояние. Как показано в [15] любой минимальный автомат имеет установочную последовательность. Правила усечения дерева преемников автомата, приведенные в [10], позволяют построить установочное дерево по его таблице переходов-выходов, из которого определяется множество установочных последовательностей автомата.

Следует отметить, что каждая отличительная последовательность является установочной, в то время как обратное неверно.

3.1.3 Синхронизирующие последовательности

В [10] приведены методы синтеза синхронизирующих последовательностей (СП) по таблице переходов-выходов автомата и по функциональной схеме ДУ. В этом разделе определена верхняя граница длины СП, которая сравнивается с известными оценками [16], анализируется сложность построения СП и условия существования в автомате однородных синхронизирующих последовательностей.

Определение 3.6 Входная последовательность XS автомата, которая устанавливает его в определенное конечное состояние независимо от состояния выхода и начального состояния, называется синхронизирующей последовательностью.

Если автомат A ( X, Y, Z, , ) задан таблицей переходов-выходов, то из определения 3.6 следует, что автомат имеет синхронизирующую последовательность тогда и только тогда, когда существует входная последовательность Xs такая, что (Zi, XS)=Z0 ; Zi Z, Z0 Z . Множество переходов (Zi, XS)=Z0 ; для Zi Z, автомата определяет отображение множества его состояний Z в некоторое определенное состояние Z0 при подаче на автомат входной последовательности XS , то есть Z Z0 .

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

Так как синхронизирующая последовательность не связана с анализом выходной последовательности автомата, то функции выходов автомата не рассматриваются при построении синхронизирующего дерева. Вершины синхронизирующего дерева отмечаются - множествами, коорые являются Xi-преемниками ( Xi X ) состояний, входящих в - множества предшествующих вершин. Вершина ранга j - синхронизирующего дерева является висячей, если:

а) вершина отмечаетя группой - множеств, которая соответствует группе - множеств какой-либо вершины ранга меньше j ;

б) вершина j-го ранга отмечена одним простым - множеством.

Путь в синхронизирующем дереве, корнем которого является начальное - множество, включающее все состояния автомата, и завершающийся висячей вершиной, отмеченной единственным простым - множеством, соответствует синхронизирующей последовательности автомата.

В качестве иллюстрации предлагается рассмотреть автомат А-2, заданный таблицей переходов-выходов (таблица 3.2). Синхронизирующее дерево (рисунок 3.2) является синхронизирующей последовательностью, которая устанавливает А-2 в состояние 4 независимо от начального состояния.

Таблица 3.2 - Автомат А-2

Z ( t )	Z ( t + 1 ), ( t )
	X=0	X=1
1	4, 1	2, 0
2	4, 1	3, 0
3	1, 0	4, 0
4	2, 0	1, 0

Рисунок 3.2 - Синхронизирующее дерево автомата А-2

3.1.4 Построение проверяющих последовательностей

Методы решения задач проверки ДУ, использующие явные и неявные модели ДУ, рассмотрены в [14, 10]. В качестве модели неисправности принята модель неисправности F1 и предполагается, что автомат является минимальным, сильносвязным, имеет отличительную последовательность и не меняет свое поведение в процессе эксперимента.

Для модели неисправности проверяющая последовательность состоит из 3-х частей или фаз:

а) установка в исходное начальное состояние;

б) проверка (идентификация) состояний;

в) проверка правильности переходов.

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

Фаза идентификации состояний заключается в попеременном приложении отличительной X0 и переводящих последовательностей Xп, определении реакции автомата на X0 для каждого начального состояния и определении X0-преемника каждого состояния. Фиксированная последовательность, идентифицирующая состояния автомата содержит n различных выходных последовательностей для всех состояний.

В третьей фазе эксперимента проверяются все m x n переходов автомата, каждое состояние до перехода и после перехода идентифицируется X0. Сокращение длины проверяющей последовательности достигается за счет совмещения второй и третьей фазы эксперимента [14].

Другой путь сокращения длины проверяющей последовательности заключается в использовании однородных отличительных последовательностей.

Рассмотрим автомат А-3, заданный таблицей переходов-выходов (таблица 3.3). Отличительное и синхронизирующее деревья автомата А-3 приведены на рисунке 3.3a и рисунке 3.3б соответственно. Автомат имеет синхронизирующую последовательность Xs = 11 и две отличительные последовательности X01 = 01 и X02 = 00.

Построим последовательность, проверяющую состояния автомата, с использованием вначале X01=01 , а затем X02=00.

Проверяющая последовательность начинается с Xs = 11, которая устанавливает автомат в начальное состояние 1. Затем X01=01 используется для идентификации состояний. Приложение X01 к автомату, находящемуся в состоянии 1, вызывает появление на выходе последовательности Y = 01. Прикладывая X01 повторно, проверяется 01 приемник начального состояния автомата.

Таблица 3.3 - Автомат А-3

Z ( t )	Z ( t + 1 ), ( t )
	X=0	X=1
1	2, 0	1, 1
2	3, 0	1, 1
3	1, 1	2, 0

С помощью переводящей последовательности Xп= переводим автомат из состояния 1 в 2. Прикладывая X01=1, получаем на выходе Y=00 и конечное состояние 2. Это конечное состояние проверяется X01=01 правильной реакцией автомата Y=00 .Затем, автомат из состояния 2 с помощью Xп=0/0 переводится в 3, прикладывается X01=01 проверяется состояние 3 по выходной последовательности Y=11.

a) Отличительное дерево автомата А-3

б) Синхронизирующее дерево автомата А-3

Рассмотренная выше фаза идентификации состояний автомата А-3 представляется следующей последовательностью

X 11 01 01 0 01 01 0 01 01

Z 1 1 1 2 2 2 3 1 1 (3.6)

Y 01 01 0 00 00 0 11 01

Если автомат реагирует правильно на приложение входной последовательности, проверяющей правильность состояний автомата, то эта последовательность одновременно проверяет правильность переходов (1,0)=2 и (2,0) =3, которые используются для построения второй фазы эксперимента. Кроме того, анализ последовательности X / Z показывает, что в фазе проверки состояний автомата дополнительно проверяются переходы (2,1) = 1, и (3,1) =2, которые подчеркнуты в последовательности

X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1

Z 1 2__1 2_1 2 3_2 3__2 3 1 1 2 1 (3.7)

Y 0 1 0 1 0 0 0 0 0 0 1 1 0 1

Анализ последовательности (3.7), проверяющей состояния автомата А-3 показывает, что в заключительной третьей фазе эксперимента проверки правильности переходов остается проверить лишь два перехода: (1,1)=1 и (3,0)=1. Так как после фазы идентификации состояний А-3 находится в состоянии 1, то для проверки перехода (1,1) = 1 необходимо приложить последовательность 101 и проверить выходную последовательность 101. Перевести автомат с помощью Хп = из 1 в состояние 3, осуществить (3,0) и, приложив отличительную последовательность X01=01, проверить правильность перехода (3,0) .

Полная проверяющая последовательность для А-3, включающая все три фазы эксперимента и состоящая из 24 входных символов представляется в виде:

X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1

Z 1 2 1 2 1 2 3 2 3 2 3 1 1 2 1 1 2 1 2 3 1 2 1 (3.8)

Y 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1

Так как для автомата А-3 существует две отличительных последовательности, то эксперимент, построенный выше, не является единственным. Нетрудно убедиться, что более короткий эксперимент получается при использовании однородной отличительной последовательности X02=00. Это связано с тем, что X02 -преемники не совпадают с начальными состояниями. В этом случае полный проверяющий эксперимент для автомата А-3 представляется в виде:

X 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0

Z 1 2 3 1 2 3 1 2 3 2 3 1 1 2 3 2 1 2 3 (3.9)

Y 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0

Легко убедиться в том, что использование однородной отличительной последовательности сокращает длину эксперимента на 4 символа.