Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)

 

Содержание

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

Реферат

Введение

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

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

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

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

1.4 Моделирование физических процессов

1.5 Игра "Жизнь"

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

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

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

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

3.1 Детерминированное тестирование

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

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

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

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

3.1.5 Отличительные последовательности в ОС

3.2 Псевдослучайное тестовое диагностирование

4. Модули сигнатурного мониторинга на сетях клеточных автоматов

4.1 Метод генерирования субпоследовательностей

4.2 Алгоритмы отыскания субпоследовательностей

4.2.1 Алгоритм основной программы

4.2.2 Алгоритмы подпрограмм

4.2.3 Результаты работы основного алгоритма

4.2.4 Правила настроек КА

5. Программа моделирования ска на языке Delphi

5.1 Исходные требования к программе моделирования

5.2 Алгоритм реализации программы

5.3 Результаты моделирования сети клеточных автоматов

6. Экономическая часть

6.1 Технико-экономическое обоснование дипломной работы

6.2 Исследования и анализ рынков сбыта

6.2.1 Сегментация рынка по потребителям

6.2.2 Анализ емкости сегментов

6.2.3 Параметрическая сегментация рынка

6.3 Оценка затрат на разработку продукта

6.3.1 Определение потребности в материальных ресурсах

6.3.2 Расчет основной заработной платы на разработку программы

6.3.3 Расчет дополнительной заработной платы

6.3.4 Отчисления на социальные мероприятия

6.3.5 Расчет машинного времени

6.3.6 Расчет накладных расходов

6.3.7 Расчет коммунального налога

6.3.8 Расчет себестоимости программного продукта

6.3.9 Расчет прибыли

6.3.10 Расчет оптовой цены

6.3.11 Расчет налога на добавочную стоимость

6.3.12 Расчет цены на продажу

6.4 Экономическая эффективность научно-исследовательской работы

6.5 Выводы

7. Охрана труда и окружающей среды

7.1 Общие вопросы охраны труда и окружающей среды

7.2 Производственная санитария

7.2.1 Метеорологические условия помещения

7.2.2 Характеристика производственного помещения

7.2.3 Виды вентиляции

7.2.4 Естественное и искусственное освещение

7.2.5 Статическое электричество

7.3 Пожарная безопасность

7.4 Охрана окружающей среды

Заключение

Список источников информации

Приложение А

Приложение Б

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CPLD - Complex Programable Logic Devices- Field Programable Gate Array

Реферат

Записка _____ страница; 22 рисунка; 16 таблиц; 35 использованных источников; приложений 2.

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

Ключевые слова: КЛЕТОЧНЫЙ АВТОМАТ, ГЕНЕРАТОР ТЕСТОВ, СХЕМЫ ВТРОЕННОГО САМОТЕСТИРОВАНИЯ, ПРОГРАММИРУЕМАЯ ЛОГИЧЕСКАЯ МИКРОСХЕМА, ДИСКРЕТНОЕ УСТРОЙСТВО.

Реферат

Записка ____ сторінка; 22 малюнка; 16 таблиць; 35 використаних джерел; додатків 2.

У роботі запропоновано новий метод синтезу генераторів детермінованих тестів на сітях клітинних автоматів (СКА). Для заданої множини тестових векторів з необхідним покриттям несправностей синтезується генератор, що алгоритмічно формує цю множину тестів за найменший час. Генератори, що синтезовані запропонованим методом, мають високу швидкодію, регулярну та тестопридатну структуру, а їх реалізація здійснюється з невеликими апаратними витратами.

Ключові слова: КЛІТИННИЙ АВТОМАТ, ГЕНЕРАТОР ТЕСТІВ, СХЕМИ ВБУДОВАННОГО САМОТЕСТУВАННЯ, ЛОГІЧНА СХЕМА ЩО ПРОГРАМУЄТЬСЯ, ДИСКРЕТНИЙ ПРИСТРІЙ

The abstract

The report contains: 121 p., 22 fig., 16 tab., 35 sources, 2 appendices.paper presents a new approach for designing cost-effective test vector generator (TVG). Given a set of precomputed test vector with a predetermined fault coverage, a simple test vector generator is synthesizes to apply the given test. To achieve, cellular automata structure have been used. The resulting TVG is very efficient in terms of hardware size and speed performance, and is very regular and testable. Simulation of various benchmark combinational circuits has given good results when compared to alternative solutions.words: CELLULAR AUTOMATA, TEST VECTOR GENERATOR, BUILT-IN SELF-TEST, PROGRAMMABLE LOGIC ARRAY, DISCRETE DEVICE.

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сеть клеточный автомат мониторинг

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 - Пример вычисления численного значения правила

111110101100011010001000Правило 14410010000Правило 6501000001Степень 276543210

Правило 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.2) (1.3)

1.4 Моделирование физических процессов

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

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

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

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

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

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

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

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

Рис 1.7 - Дискретизация на примере квадратной и гексагональной решёток

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

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

Таким образом, вычислительная система может оперировать своей материальной частью, модифицировать, расширять себя и строить себе подобных [1]. Хотя системы этого класса и были придуманы Джоном фон Нейманом, такая параллельная архитектура получила название "не-фон-неймановской", так как последовательную архитектуру он создал раньше.

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

Например, рассмотрим автомат, реализующий игру "Жизнь". При данных решётке и правилах, меняя лишь состояние решётки, можно реализовать универсальные вычислительные системы, позволяющие производить любые вычисления, которые, по своим выразительным способностям эквивалентны произвольным машинам Тьюринга и клеточным автоматам [7]. Теми же возможностями обладает, в частности, автомат, называемый компьютером Бэнкса [1]. Однако использовать их крайне неэффективно, но с теоретической точки зрения это - важный результат.

1.5 Игра "Жизнь"

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

Рассматривается бесконечная плоская решётка квадратных ячеек-клеток. Время в этой игре дискретно (t=0, 1, 2,.). Клетка может быть живой или мёртвой. Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t (соседей у клетки восемь, четверо имеют с ней общие ребра, а четверо только вершины).

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

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

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

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

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

Следствием этих требований явились следующие правила игры "Жизнь":

. Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.

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

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

Зададимся вопросами:

Какие основные типы структур (то есть конфигураций, определяющих поведение сообществ на больших временах) могут существовать в такой системе?

Каковы здесь законы организации структур?

Могут ли они взаимодействовать, и к чему это приводит? Выясним, какие закономерности являются следствиями представленных выше правил. Первая закономерность - свойство локализации - структуры, разделенные двумя "мёртвыми" (пустыми) клетками не влияют друг на друга. Вторая закономерность - система клеток, которую описывает игра "Жизнь", развивается необратимо. В самом деле, конфигурация в момент времени t полностью определяет будущее (состояние в моменты t+1, t+2 и так далее). Но восстановить прошлое системы по её настоящему не удаётся. Картина здесь такая же, как в одномерных отображениях, только прообразов у данной конфигурации может быть бесконечно много.

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

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

Условимся классифицировать конфигурации клеток по следующим параметрам:

.По количеству клеток в комбинации: единичная клетка, дуплет (2 клетки в комбинации), триплет (3 клетки) и т.д.

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

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

Рисунок 1.8 - Примеры стационарных структур, реализующихся в игре "Жизнь"

Можно считать, что стационарные структуры повторяют себя на каждом шаге по времени. Но есть и другие конфигурации, повторяющие себя через N шагов, так называемые N-циклы (периодические структуры). При эволюции различных сообществ часто встречается 2-цикл, называемый "семафором". Однако эффективные алгоритмы, позволяющие строить различные конфигурации с данным периодом N, по-видимому, в настоящее время не созданы. Эволюция взятых наугад начальных данных часто приводит к возникновению простейших локализованных структур (показанных на рис.1.8) и семафоров. Однако возможны и более сложные типы эволюции, например, когда сообщество клеток симметрично "достраивается", и возникают циклы большого периода, имеющие сложную форму.

В игре "Жизнь" существуют конфигурации, которые могут передвигаться по плоскости. Одной из них является "планер" (или "глайдер") - конфигурация из 5 клеток (рис.1.9)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 Машина клеточных автоматов 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, d, l), (3.1)

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

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

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

d (Zi, Xk) = Zj; Zi, ZjZ; XkX; i, j = ; k = - множество функций переходов автомата;

l (Zi, Xk) = ya; yaY, a = - множество функций выхода автомата.

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

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

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

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

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

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

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

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

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

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

pa = {},

pb={ },

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

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

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

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

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

pa × pb = {}.

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

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

p1 + p2= { }.

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

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

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

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

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

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

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

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

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

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

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

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

Z (t) Z (t + 1), l (t) X1X212, 11, 121, 13, 035, 03, 142, 01, 054, 15, 0

Рисунок 3.1 - Отличительное дерево автомата А-1

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

d ({ } X1) = { 2, 1, 4 }, { 5, 2 }. (3.3)

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

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

p (1) p1 p2 p3 p3 p4 = p (0), (3.4)

которую можно упорядочить в виде

p (1) >p1 > p2 > p3 = p3 > p4 = p (0). (3.5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Z (t) Z (t + 1), l (t) X=0X=114, 12, 024, 13, 031, 04, 042, 01, 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), l (t) X=0X=112, 01, 123, 01, 131, 12, 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.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

Если автомат реагирует правильно на приложение входной последовательности, проверяющей правильность состояний автомата, то эта последовательность одновременно проверяет правильность переходов d (1,0) =2 и d (2,0) =3, которые используются для построения второй фазы эксперимента. Кроме того, анализ последовательности X / Z показывает, что в фазе проверки состояний автомата дополнительно проверяются переходы d (2,1) = 1, и d (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 показывает, что в заключительной третьей фазе эксперимента проверки правильности переходов остается проверить лишь два перехода: d (1,1) =1 и d (3,0) =1. Так как после фазы идентификации состояний А-3 находится в состоянии 1, то для проверки перехода d (1,1) = 1 необходимо приложить последовательность 101 и проверить выходную последовательность 101. Перевести автомат с помощью Хп = из 1 в состояние 3, осуществить d (3,0) и, приложив отличительную последовательность X01=01, проверить правильность перехода d (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 символа.

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

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

3.1.5 Отличительные последовательности в ОС

На функциональном уровне описания ячейки однородной одномерной сети без наблюдаемых выходов Х будем рассматривать ее таблицу истинности как таблица переходов - выходов автомата Мура, задаваемого тройкой (X,Y,d), у которого функции переходов и выходов совпадают, то есть

d (Zi,Xa) =l (Zi,Xa) =Zj,Zi, ZjZ, XaX, (3.10)

Пусть Z={Z1,…Zi,…Zn} - множество состояний автоматной модели ячейки сети. Будем обозначать Z [Zi] = { Z1,… Zi-1, Zi+1,…Zn } = { Z - Zi } - множество состояний ячейки сети, из которого исключен элемент Zi. Как было показано на примере одномерной сети (рисунок 1.2), при синтезе проверяющих тестов сложность решения задачи анализа полноты полученных тестов и их расширения связана с наличием в автоматной модели ячейки сети пар Xa - совместимых состояний. Из таблицы переходов ячейки легко можно определить множества Xi - совместимых состояний для каждого входного символа Xi X, i= . Образуем множество ZC = …элементы, которого представляют собой состояния, Xa - совместимые для всех входных символов множества X.

Определение 3.7 Пусть ячейка одномерной ОС без наблюдаемых выходов X представлена моделью автомата Мура (Х,Z,d), в котором Xa - преемником состояния ZiZ является состояние Zk, не обязательно отличное от Zi. Входной символ Xa X будем называть отличительным символом состояния Zi тогда и только тогда, когда Zk не является Xa - преемником для множества Z [Zi] начальных состояний автомата и Zk ZC.

Если столбец Xa таблицы переходов ячейки сети содержит пару неразличимых состояний (Zа, Zb), то есть d (Za, Xa) = Zk, d (Zb,Xa) = Zk состояния (Zа, Zb) неразличимы для входного символа Хa. В общем случае может быть две альтернативы. Пара состояний (Zа, Zb) различается, по меньшей мере, одним входным символом Хb, либо пара (Zа, Zb) - Xi совместима для каждого входного символа Xi X. В первом случае состояния Zа и Zb можно идентифицировать только приложением к входу проверяемой ячейки входного символа Хb. Во втором случае для различения состояний (Zа, Zb) можно воспользоваться множеством характеристических входных символов подобно тому, как в [1] использовались характеристические последовательности при построении диагностических экспериментов для автоматов, не имеющих отличительных последовательностей.

Определение 3.8 Пусть ячейка одномерной сети представлена моделью автомата Мура (Х, Z, d). Множество входных символов Xc={ X1, X2, …, Xr } называется множеством входных характеристических символов тогда и только тогда, когда для любой пары состояний (Zа, Zb) Z автомата

d (Za,X1) d (Za,X2) … d (Za,Xr) d (Zb,X1) d (Zb,X2) … d (Zb,Xr) (3.11)

Определение 3.9 Пусть Z={ Z1, Z2, Z3, … Zr } подмножество состояний минимального автомата А. Множество Хс={ X1, X2, X3, … Xp }, будем называть множеством характеристических последовательностей, если для каждого начального состояния ZiZ, реакция на Хс различна, то есть

l (Z,X1) l (Zi,X2) … l (Zi,Xp) l (Zj,X1) l (Zj,X2) … l (Zj,Xp) Zi Zj, (3.12)

для Zi, Zj Z, а исключение любой последовательности из множества Хс не позволяет различить, по меньшей мере, одно состояние ZiZ.

Множество отличительных и характеристических символов может быть найдено из характеристического дерева автомата ячейки сети, которое строится по правилам, приведенным в разделе 1.5 [1]. На рисунке 3.4 приведено характеристическое дерево сети (рисунок 1.2), из которого следует, что символ X1=1 является отличительным для множества состояний {Z0, Z1, Z2, Z3} символ X0=0 для состояний Z2 и Z3. Пара состояний {Z0, Z1} является X0-совместимой.

Рисунок 3.4 - Характеристическое дерево ячейки сети

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

Так как произведение разбиений = () и = () равно p (0), то множество Хc={ X1, X3 } является множеством входных характеристических символов. Простые s - множества для каждой вершины характеристического дерева определяют множества состояний, для которых метка вершины дерева является отличительным входным символом.

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

Например, из характеристического дерева ячейки сети (рисунок 3.5, таблица 3.4) следует, что

= {Z3, Z4}; = {Z1, Z3, Z4}; = {Z1, Z3}, (3.13)

Таблица 3.4 - Таблица переходов выходов ячейки сети

Z (t) Z (t+1) X1X2X3Z1Z2Z1Z3Z2Z3Z3Z4Z3Z4Z1Z3Z4Z4Z1Z1

Рисунок 3.5 - Характеристическое дерево ячейки сети

Множества Хa - совместимых состояний ячейки позволяют определить множество Zc в виде:

Zc= ={Z3}, (3.14)

Определив множество Zc, из характеристического дерева можно легко найти множество отличительных символов и состояний ячейки, которые различаются этими символами в соответствии с определением 3.7 Для рассматриваемого примера состояние Z1, различается символом X1, состояния Z2 и Z4 - символом X3.

Определение 3.10 Пусть состояние Zj правого выхода ячейки C (k) однородной одномерной сети транспортируется на крайний правый выход сети приложением входного набора Xт к входам ячеек C (k+1), C (k+2),…. C (p). Входной набор Xт является проверяющим тестом, идентифицирующим состояние Zj ячейки C (k), если состояние наблюдаемых выходов сети различно, когда Zj и каждое из состояний множества Z [Zj], приложено к левому входу ячейки C (k+1), то есть

d (Zj,Xт) d (Zi,Xт), ZiZ [Zj]. (3.15)

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

Нижеследующая теорема определяет необходимые и достаточные условия существования в однородной сети проверяющих тестовых наборов Xт.

Теорема 3.1 Пусть правый выход ячейки C (k) одномерной однородной сети находится в состоянии Zj и к верхним входам ячеек C (k+1), C (k+2),…. C (p) приложен входной набор Xk={ Xk+1, Xk+2,…,Xp }, вызывающий последовательность переходов состояний ячеек сети в виде

Zj Zk+1Zk+2… Zp-1Zp, (3.16)

где состояние слева от входного символа XaXk, a= (k+1) (k+2) …. является предшествующим, а состояние справа от Xa - последующим. Если существует последовательность состояний ячеек C (k+1),C (k+2), …. C (p), порождаемая приложением входного наборa Xk, в котором каждый символ XaXk является отличительным символом предшествующего состояния, то последовательность этих символов образует проверяющий тестовый набор состояния Zj, ячейки C (k) сети.

Как будет показано ниже, задача построения проверяющих входных наборов для заданной одномерной ОС значительно упрощается, если существуют циклические переводящие последовательности, образованные от отличительных входных символов. При построении диагностических экспериментов (ДЭ) по автоматным моделям ДУ возникает задача нахождения множества переводящих последовательностей T (Zi,Zj), с помощью которых ДУ из начального состояния Zi переводится в состояние Zj. Известно, что эта задача тривиальна, если ДУ задано графом или таблицей переходов [10]. Как показано в [10], переводящая последовательность T (Zi,Zj) определяется путем построения фрагментов дерева преемников состояния Zi, содержащего путь или множество путей, оканчивающихся состоянием Zj.

При построении проверяющих тестов для одномерных ОС возникает аналогичная задача нахождения множества переводящих последовательностей по автоматной модели ячейки сети. Тестопригодность сети, число ячеек которой превышает число состояний автоматной модели ячейки сети, определяется наличием в ней циклических переводящих последовательностей T (Zi,Zi), которые так же, как и любые другие переводящие последовательности, можно легко найти из автоматной модели ячейки сети. В соответствии с теоремой 3.1 циклическая переводящая последовательность T (Zi,Zi), которая образована из отличительных входных символов, является одновременно проверяющим тестовым набором, который транспортирует состояние проверяемой ячейки сети на наблюдаемый выход.

Определение 3.11 Циклическую переводящую последовательность, образованную из входных отличительных символов предшествующих состояний ячеек сети, будем называть циклической отличительной последовательностью (ЦОП).

Рассмотрим класс однородных одномерных сетей без наблюдаемых выходов X, состоящих из p ячеек, каждая из которых имеет m входных символов, n состояний и каждое состояние имеет, по меньшей мере, один отличительный символ. Для сетей такого типа справедливо следующее утверждение.

Теорема 3.2 Если в ячейке ОС с n состояниями, каждое состояние имеет, по крайней мере, один отличительный символ, то для такой сети существует, по меньшей мере, одна циклическая отличительная последовательность.

В качестве примера рассматривается автомат, заданный в таблице 3.5 Из характеристического дерева автомата (рисунок 3.6) находим отличительные символы состояний:

Z1 - X2; Z2 - X2; Z3 - X3; Z4 - X1 (3.17)

Автомат удовлетворяет условию теоремы 3.1, следовательно, он имеет циклическую отличительную последовательность. Последовательность переходов по отличительным символам Z1Z2Z3Z4Z4 завершается циклом Z4Z4.

Таблица 3.5 - Таблица переходов-выходов ячейки

Z (t) Z (t+1) X1X2X3Z1Z1Z2Z2Z2Z1Z3Z2Z3Z1Z4Z4Z4Z4Z4Z2

Рисунок 3.6 - Характеристическое дерево ячейки

Аналогично, ЦОП имеется в автомате, заданном в таблице 1.2 Из характеристического дерева (рисунок 3.4) находим:

Z1 - X1; Z2 - X2; Z3 - X3; Z4 - X1; (3.18)

Последовательность переходов Z1Z3Z0Z2Z1 является циклической отличительной последовательностью.

Теорема 3.2 определяет необходимые условия существования в ячейке ОС циклической отличительной последовательности. В следующем подразделе будет показано, что существование ЦОП для заданной однородной сети упрощает процедуру построения проверяющего эксперимента для этой сети также, как и наличие отличительных последовательностей для автоматных моделей произвольных ДУ с элементами памяти. Такие ОС в дальнейшем будем называть легко тестируемыми.

Выводы:

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

Если для проверки цифровой схемы применяется детерминированный подход, сложность состоит в том, что детерминированный набор тестов должен быть встроен в схеме, то есть схема должна иметь дополнительные аппаратные средства, которые в режиме самотестирования выдают тестовые последовательности.

Схема самотестирования может быть реализована двумя различными способами:

а) тестовые наборы могут быть или записаны на кристалле с помощью ПЗУ (которая должна также содержать правильные выходные последовательности для сравнения с реальными выходными последовательностями);

б) тестовые наборы также могут быть сгенерированы, с помощью специальных генераторов, предназначенных для этой задачи, в данном проекте рассматривается реализация на КА;

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

Для схем умножителей, использование ПЗУ может быть оправдано, когда умножитель модифицируется в соответствии с требованиями C-тестируемости. Основной недостаток этого подхода заключается в том, что модификация схемы в соответствии с требованиями тестопригодного проектирования приводит к увеличению занимаемой основной схемой умножителя площади кристалла, введению дополнительных входов-выходов, и снижению производительности [18-21].

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

Если не модифицировать схему умножителя, то для тестирования требуется набор тестов линейного размера. Например, в [20], был предложен линейный набор тестов размера 3N + 60, где N - общая длина обоих операндов умножителя. В этом случае, размер тестового набора намного больший чем при С-тестируемости, так что затраты на хранение тестовых наборов в ПЗУ - предельно высокие. Эти затраты могли бы быть уменьшены, если бы нашелся такой генератор тестовых наборов, который генерирует нужные образцы теста. К сожалению, наборы тестов, предложенные в [18 - 21] неправильные и не могут быть эффективно произведены с использованием небольших аппаратурных затрат. Также, этот подход зависит от размерности умножителя, потому что размер набора тестов увеличивается с размерностью умножителя.

3.2 Псевдослучайное тестовое диагностирование

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

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

Рисунок 3.8 - Встроенное самотестирование по псевдослучайному подходу

а)

б)

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

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

Рисунок 3.10 - Сигнатурный анализатор

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

4. Модули сигнатурного мониторинга на сетях клеточных автоматов

Схемы встроенного самотестирования (СВС) широко используются в дискретных устройствах (ДУ), построенных на одном кристалле. Структура ДУ с СВС показана на рис.4.1, где тестируемая схема (ТС) - комбинационная схема с наблюдаемыми входами и выходами.

Рисунок 4.1 - Структура ДУ с встроенным самотестированием

Для достижения соответствующего качества тестирования, необходимо выполнить три условия:

. Минимизировать аппаратные затраты на построение генератора;

. Минимизировать время тестирования;

. Максимизировать покрытие неисправностей.

В настоящее время существуют следующие способы генерирования тестовых векторов в СВС: исчерпывающее тестирование (счетчик генерирует все 2n векторов, где n - количество входов тестируемой схемы), псевдослучайное тестирование (на основе сдвиговых регистров с линейными и нелинейными обратными связями, сетей клеточных автоматов), детерминированное тестирование (запись тестовых векторов в ПЗУ и формирование адресов на счетчиках) [6].

Большое распространение получают генераторы тестов на основе СКА. Главное достоинство таких сетей по сравнению с другими схемами - регулярность структуры и локальность взаимосвязей между клеточными автоматами (КА), что делает их привлекательными при реализации ДУ на программируемых логических интегральных схемах типа CPLD, FPGA. Важной характеристикой СКА является более высокая частота генерации тестов.

4.1 Метод генерирования субпоследовательностей

Исходным данным для работы алгоритма является детерминированное множество двоичных векторов М, в виде произвольной последовательности

где vi - i-й вектор M, m - количество векторов в M.

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

) Каждая субпоследовательность Sl должна быть детерминированной;

) ;

) Длина субпоследовательностей Sl - ;

) Последний вектор Sl берется в качестве первого Sl+1.

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

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

Упорядочивание исходного множества в субпоследовательности

Первый этап состоит из таких шагов:

1)Все векторы из исходного множества пронумеровываются.

2)Путём подбора отыскивается начальный вектор vн.

)Текущая субпоследовательность Sl= [], l=1.

4)Присоединить начальный вектор к Sl (Sl (1) =vн).

)Если в М не существует непомеченного вектора vi, такого, чтобы для субпоследовательности Sl+ vi выполнялось (2.2), перейти к пункту 8.

)Sl= vi.

7)Пометить vi как использованный.

)Если в М все векторы помечены, перейти к пункту 12.

)l=l+1;

10)Sl (1) =vi;

11)Перейти к пункту 5;

)Конец.

Знак "+" в пунктах 5 и 6 означает операцию присоединения вектора v к субпоследовательности Sl.

4.2 Алгоритмы отыскания субпоследовательностей

4.2.1 Алгоритм основной программы

На рисунке 4.2 показана блок-схема алгоритма первого этапа, реализованного в системе Delphi.

В данной схеме переменные М, List2 - объектного типа. Они содержат в себе список строк, а так же свойства и методы, предназначенные для работы со списком. Переменная М содержит исходный список векторов, а List2 предназначен для хранения полученных субпоследовательностей. Переменные i, j, L - целочисленного типа, i используется как счетчик, в j хранится индекс начального вектора, L используется для сравнения длинны субпоследовательности, полученной с различными начальными векторами.

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

Операторы с 4 по 8 составляют тело цикла, в котором отыскивается наилучший начальный вектор для первой субпоследовательности. Критерий качества этого вектора - максимально возможная длина первой субпоследовательности. В блоке 4 запоминается i-й вектор из исходного списка в переменную Sample, удаляется i-й вектор из исходного списка, очищается список, предназначенный для сохранения результата. В переменной L сохраняется длина субпоследовательности, полученная для предыдущего начального вектора. На первом проходе цикла L = 0. Оператор 6 выполняет переход по ветви "Да", если длина субпоследовательности для текущего начального вектора больше, чем для предыдущего, в этом случае запоминается улучшенный результат (блок 7). В результате в переменной Sample2 останется наилучший начальный вектор для первой субпоследовательности.

В блоке 9 выполняется поиск индекса вектора Sample2 в исходном множестве, а затем этот индекс удаляется. Это нужно для того, чтобы данный вектор не повторился дважды в первой субпоследовательности. После выполнения блока10, в List2 запоминается первая субпоследовательность. Далее, построение остальных субпоследовательностей происходит в цикле, условием выхода из которого (блок 11) является отсутствие неиспользованных векторов в исходном множестве.

4.2.2 Алгоритмы подпрограмм

Основой алгоритма, приведенного в п.4.2.1 является подпрограмма GetSubSeq. Ее блок-схема представлена на рис.4.3 Переменная М содержит исходное множество двоичных векторов. Sample - содержит начальный вектор, Lst2 - список, к которому будет добавлена полученная субпоследовательность. List3 и List4 - два вспомогательных списка, которые создаются в операторе 2 и существуют все время выполнения подпрограммы. List3, после выполнения подпрограммы, будет содержать искомую субпоследовательность, List4 предназначен для хранения результатов выполнения подпрограммы GetByMask.

В результате выполнения блока 2, в List3 находится начальный вектор. В блоке 3 вызывается подпрограмма GetMask, которая на основе списка List3 получает маску, используемую для нахождения следующего вектора субпоследовательности (удовлетворяющего выражению (2.2)). Найденная маска помещается в переменную Mask.

В блоке 4 вызывается подпрограмма GetByMask, которой в качестве входных параметров передаются М и Mask. Данная подпрограмма отыскивает все векторы в М, отвечающие заданной маске, и сохраняет их в список List4.

В блоке 5 используется свойство Count переменной List4. Оно содержит количество векторов, которое содержит список. Если List4. Count = 0, т.е. не найдено ни одного вектора, то на этом нахождение текущей субпоследовательности завершается. Найденная субпоследовательность, которая содержится в List3, присоединяется к списку Lst2 (блок 8). В этом же блоке происходит освобождение памяти, занимаемой объектами List3 и List4.

Если же в результате выполнения блока 4 был найден хотя бы один вектор, то нахождение субпоследовательности продолжается в цикле. Подпрограмма SelectVector, вызываемая в блоке 6, позволяет выбрать наиболее подходящий из возможных векторов (из List4), и сохраняет его в переменной V, после чего V присоединяется к List3 (блок 7). В этом же блоке все неиспользованные векторы возвращаются в исходный список М. Далее выполняется следующая итерация цикла.

Далее рассмотрим алгоритм функционирования подпрограммы GetMask. Исходными данными для работы является List - это список, который передается в подпрограмму из вызвавшей программы, на его основе строится маска. Результат работы подпрограммы возвращается через переменную Result. Строковые переменные Subl и Sub2 используются для выделения и сравнения частей векторов. На i-м шаге внешнего цикла Subl содержит подстроку, состоящую из трех элементов последнего вектора из списка List, стоящих в позициях i-1, i, i+l Sub2 содержит те же три элемента j-гo вектора:

Subl = List [List. Count-ll [i-1] + List [List. Count-1] [i] + List [List. Count - l] [i+l];= List [j] [i-1] + List [j] [i] + List [j] [i+1],

где '+' обозначает конкатенацию строк.

Если в подпрограмму передан пустой список, это вызовет ошибку, для исключения такой ситуации выполняется проверка, если возникла ошибочная ситуация, подпрограмма посылает 'сообщение об ошибке' вызвавшей программе и завершает работу. Символ '*' в маске означает незафиксированный разряд, т.е. при проверке соответствия вектора маске (в подпрограмме GetByMask) такой разряд не сравнивается.

На рис.4.4 приведена блок-схема подпрограммы GetByMask, которая по заданной маске Mask, извлекает векторы из списка L1 и добавляет эти векторы в список L2, который и является результатом ее выполнения. Переменная j - это счетчик строк, a i - позиций (разрядов). При достижении j значения, соответствующего количеству строк в L1, подпрограмма завершается (блок 4). При достижении значения i>n (т.е. пройдена вся строка), текущий вектор заносится в список L2, происходит переход к следующему вектору и переустановка i. Соответствие вектора маске проверяется в блоке 6 поразрядно, при первом несоответствии происходит переход к следующему вектору и переустановка i (блоки 9 и 8 соответственно).

Подпрограмма SelectVector, блок-схема алгоритма которой приведена на рис.4.5, необходима для того, чтобы выбрать наиболее подходящий из всех векторов, которые могут быть присоединены к субпоследовательности на данном шаге. Переменные LI, L2 - списки, содержащие строящуюся субпоследовательность и векторы, которые могут быть присоединены к ней на данном шаге соответственно; переменная V содержит выбранный вектор после завершения работы подпрограммы. Переменная i - счетчик строк, j - содержит значение номера выбранного вектора в L2. Здесь также используется функция GetFreeColCount, которая подсчитывает количество символов '*' в аргументе.

4.2.3 Результаты работы основного алгоритма

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

T = {11111111; 10100101; 01110000; 00111110; 01011100; 00000110; 00011001; 11100011; 11010010; 10001101; 11110000; 00001111; 00010000; 00001101; 11111010; 00101111}.

В результате работы алгоритма получены следующие субпоследовательности:

S1S2S3S411111010 10100101 01011100 00001111 01110000 00101111 0001000000010000 11111111 10001101 00000110 11010010 11111110 1000111010001110 00011001 11100011 11110000 11111111 11111010 1111011111110111 00111110 00001101 01111111 11101110 00111101 00001111

4.2.4 Правила настроек КА

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

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

S1 - 4, 33, 128, 50, 146, 101, 17, 17

S2 - 9, 65, 34, 5, 144, 195, 101, 65

S3 - 9, 129, 193, 212, 152, 33, 135, 21

S4 - 2, 9, 193, 66, 168, 200, 160, 20

5. Программа моделирования ска на языке Delphi

5.1 Исходные требования к программе моделирования

Исходными данными для работы программы являются:

.Количество сегментов сети клеточных автоматов n.

2.Начальные значения каждой клетки.

.Количество шагов эволюции клеточного автомата k.

.Правило функционирования для каждой клетки, заданное в виде минимальной дизъюнктивной нормальной форм

Результатом работы программы должны быть значения каждого КА на каждом шаге эволюции в следующем виде:

Программа должна работать в среде Windows 98/Me/2000/XP и иметь визуализированный интерактивный интерфейс.

5.2 Алгоритм реализации программы

На рисунке 5.1 изображена блок-схема основного алгоритма программы.

Текст программы и ее внешний вид, описание элементов управления представлены в ПРИЛОЖЕНИИ А и ПРИЛОЖЕНИИ Б соответственно.

Блок 1. Осуществляется ввод исходных данных, n - количество клеток, k - количество шагов эволюции.

Блок 2. Устанавливаются начальные значения счётчиков i, j. В массиве sp [j, i] хранятся значения клеток, полученные на предыдущем шаге, в массиве s [j, i] - текущие значения. До начала работы этого алгоритма в этом массив помещаются начальные значения.

Блок 3. Проверяется условие прохода всех шагов эволюции системы.

Блок 4. Проверяется условие прохода всех клеток сети.

Блок 5. Производится вычисление нового значения текущей клетки с последующим занесением его в массив s [j, i] по отдельному алгоритму с учётом значений массива sp [j, i].

Блок 6. Увеличение счётчика на 1. В массив sp [j, i] заносятся текущие значения.

Блок 7. Вывод нового значения текущей клетки на экран.

Блок 8. Увеличение счётчика цикла

5.3 Результаты моделирования сети клеточных автоматов

Исходные данные:

.n=8

2.k=7

Были произведены 4 эксперимента со следующими настройками КА

1.4, 33, 128, 50, 146, 101, 17, 17

.9, 65, 34, 5, 144, 195, 101, 65

.9, 129, 193, 212, 152, 33, 135, 21

.2, 9, 193, 66, 168, 200, 160, 20

Полученные результаты:

S1S2S3S411111010 10100101 01011100 00001111 01110000 00101111 0001000000010000 11111111 10001101 00000110 11010010 11111110 1000111010001110 00011001 11100011 11110000 11111111 11111010 1111011111110111 00111110 00001101 01111111 11101110 00111101 00001111

6. Экономическая часть

6.1 Технико-экономическое обоснование дипломной работы

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

Маркетинговые исследования включают:

• описание товара;
• назначение товара;
• область применения;
• расчеты по определению емкости;
• сегментация рынка по потребителям и конкурентам;
• составление сметы затрат на разработку изделия и его себестоимости.

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

6.2 Исследования и анализ рынков сбыта

6.2.1 Сегментация рынка по потребителям

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

Таблица 6.2 - Сегментация рынка по потребителям

Область использованияКод сегментаПотребители123Исследовательские лабораторииА+Конструкторские бюроБ+Организации по разработке специализированной аппаратурыВ+

Группы потребителей:

- сотрудники НИИ;

- инженеры электронщики и разработчики электронных устройств;

- прочие разработчики.

6.2.2 Анализ емкости сегментов

Данные об анализе сегментов рынка представлены в таблице 6.3.

Таблица 6.3 - Емкость сегментов рынка

Область использования (сегменты) Количество объектов, которые будут использовать изделие (шт.) Предполагаемое число продаж одному объекту (шт.) Предполагаемая емкость сегмента (шт.) Исследовательские лаборатории15115Конструкторские бюро25125Организации по разработке специализированной аппаратуры515Итого емкость рынка45

6.2.3 Параметрическая сегментация рынка

Основными требованиями потребителей являются простота использования, минимальная стоимость, скорость работы программы. Параметрическая сегментация рынка по пятибальной шкале приведена в таблице 6.4.

Таблица 6.4 - Параметрическая сегментация рынка

ПараметрыКод сегментаИтого% к общему итогуАБВЦена4541322,6Простота реализации5551525,8Скорость работы5551525,8Коэффициент покрытия неисправностей5551525,8Итого58100,0

Таким образом, на основании проведенных исследований наиболее важными характеристиками явились простота реализации, скорость работы и коэффициент покрытия неисправностей.

6.3 Оценка затрат на разработку продукта

6.3.1 Определение потребности в материальных ресурсах

Оценивается объем материальных ресурсов для производства программного продукта.

Стоимость материальных затрат приведена в таблице 6.5.

Таблица 6.5 - Покупные материалы при разработке данного продукта

МатериалыКоличество (шт.) СтоимостьОбщая стоимостьНазначениеДискеты42,5010,00Сохранение программыБумага5000,0420,00Распечатка исходных текстовКартридж для принтера199,0099,00Распечатка документации текстов программСуммарная стоимость141,00

6.3.2 Расчет основной заработной платы на разработку программы

В таблице 6.6 приведена оценка основной заработной платы

Таблица 6.6 - Расчет заработной платы (в гривнах)

ДолжностьОкладКоличество исполнителейВремя занятости (в месяцах) Основная заработная платаРуководитель темы25013150,00 (процент участия 20%) Итого150,00

6.3.3 Расчет дополнительной заработной платы

Дополнительная заработная плата включает доплаты, надбавки, гарантийные и компенсационные выплаты, предусмотренные законодательством. Дополнительная заработная плата составляет 10% от основной заработной платы.

Дополнительная заработная плата = 150 * 0,1 = 15 грн.

6.3.4 Отчисления на социальные мероприятия

а) Отчисления в пенсионный фонд составляют 32% от основной заработной платы.

Отчисления в пенсионный фонд = 150 * 0,32 = 48 грн.

б) Отчисления на медицинское страхование составляют 4% от основной заработной платы.

Отчисления на медицинское страхование = 150*0,04 = 6 грн.

в) Отчисления в фонд занятости составляют 1,5% от основной заработной платы.

Отчисления в фонд занятости = 150 * 0,015 = 2,25 грн.

6.3.5 Расчет машинного времени

Все работы по созданию проекта велись 3 месяца по 3 часа в день. Рабочих дней в месяце - 21. Цена за один час - 1 грн.

Стоимость машинного времени = 3 * 3 *21 *1 = 189 грн.

6.3.6 Расчет накладных расходов

Накладные расходы = 150 * 0,7 = 105 грн.

6.3.7 Расчет коммунального налога

Коммунальный налог составляет 10% минимальной заработной платы. На момент разработки проекта минимальная заработная плата составляла 118 грн.

Коммунальный налог = 11,80 грн.

6.3.8 Расчет себестоимости программного продукта

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

Себестоимость = 141+150+15+48+6+2,25+189+105+11,8 = 668,05 грн.

6.3.9 Расчет прибыли

Прибыль составляет 25% от себестоимости.

Прибыль = 668,05 * 0,25 = 167,01 грн.

6.3.10 Расчет оптовой цены

Оптовая цена состоит из себестоимости и прибыли.

Оптовая цена = 668,05 + 167,01 = 835,06 грн.

6.3.11 Расчет налога на добавочную стоимость

НДС на данный момент составляет 20% от оптовой цены.

Сумма НДС = 835,06 * 0,2 = 167,01 грн.

6.3.12 Расчет цены на продажу

Цена на продажу состоит из оптовой цены и налога на добавленную стоимость.

Цена на продажу = 835,06 + 167,01 = 1002,07 грн.

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

Таблица 6.7 - Калькуляция себестоимости (в гривнах)

Наименование статьи и затратСуммаСтоимость материалов и покупных изделий141,00Основная заработная плата150,00Дополнительная заработная плата15,00Отчисления на социальные мероприятия в том числе: - - Отчисления на медицинское страхование48,00 - Отчисления в пенсионный фонд6,00 - Отчисления в фонд занятости2,25Стоимость машинного времени189,00Оптовая цена835,06НДС167,01Цена 1002,07

6.4 Экономическая эффективность научно-исследовательской работы

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

Определение экономической эффективности научно-исследовательской работы базируется на общих методах расчета сравнительной экономической эффективности новой техники.

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

В действующих методологических положениях о порядке образования, распределение и использование фондов экономического стимулирования технического прогресса рекомендуется относить на организации, выполняющие научно-исследовательские и опытно-конструктивные работы, от 30% до 50% экономического эффекта; на технологические работы от 20% до 30%; на освоение и организацию производства новой техники от 25% до 40% экономического эффекта.

Экономическую эффективность некоторых поисковых и прикладных научно-исследовательских работ рассчитать не удается. В таком случае приводят качественное описание социально-экономической эффективности научно-исследовательской работы.

Сущность этой методики состоит в том, что на основе оценок работы определяется коэффициент научно-технического эффекта НИОКР:

, (6.1)

где: ri - весовой коэффициент і-го признака научно-технического эффекта (таблица 4.8);

ki - количественная оценка і-го признака научно-технического эффекта научно-исследовательской работы.

Таблица 6.8 - Коэффициент весомости признаков

Признак научно-технического эффекта НИОКРЗначение весового коэффициентаУровень новизны Теоретический уровень Возможность реализации0,6 0,4 0,2

Классификатор признаков научной новизны принимается равным k1=7, так как уровень новизны разработки определяется как новая.

Классификатор признаков теоретического уровня принимается равным k2=6, так как производится разработка нового способа.

Классификатор признаков времени реализации принимается равным:

k3=k31+k32; (6.2)

k31= 10, так как время реализации в течение первых 4 лет;

k32=2, так как масштабы реализации в пределах нескольких предприятий. Отсюда:

Нт = 0,6?7+0,4?10+0,2? (10+2) =10,6

6.5 Выводы

Так как максимально возможное значение коэффициента научно-технического эффекта НИОКР Нт=12, то проведенный анализ позволяет сделать вывод о целесообразности проведения данной исследовательской работы.

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

7. Охрана труда и окружающей среды

7.1 Общие вопросы охраны труда и окружающей среды

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

Охрана труда - система правовых, социально-экономических, организационно-технических, санитарно-гигиенических и лечебно-профилактических мероприятий и средств, направленных на охрану здоровья и работоспособности человека в процессе труда (Закон Украины Об охране труда" от 21.11.02) [22].

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

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

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

В данном разделе рассматриваются вопросы охраны труда и окружающей среды для дипломного проекта: Модули сигнатурного мониторинга на клеточных автоматах.

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

При выполнении данной работы использовалось такое оборудование: ПЭВМ, принтер, сканер, ксерокс.

Перечисленное оборудование использует напряжение промышленной электросети до 1000В, поэтому необходимо выполнять правила по безопасному ведению работы с электрооборудованием - ПУЭ-87 [23].

При работе на ПЭВМ на человека воздействует ряд опасных и вредных факторов, которые классифицируются согласно ГОСТ 12.0.003-74 [24]. Опасным фактором называется фактор, вызывающий травму или повреждение организма. Вредный фактор - фактор, длительное воздействие которого приводит к патологии в организме - профессиональным заболеваниям. Эти факторы разделяются на физические, химические, биологические и психофизические основные из них приведены в таблице 7.1.

Таблица 7.1 - Перечень опасных и вредных факторов

Наименование фактораИсточник возникновения фактораХарактер воздействия на человекаНормированные параметры и нормативные значенияНорматив- ный документ1. Повышенный уровень статического электричестваЭЛТОпасность поражения током, раздражение кожиПотенциал не более 500 В. ГОСТ 12.1.038-82 [25] 2 Повышенный уровень шума. Устройства охлаждения ЭВМ, печатающие устройстваУтомление слуховых анализаторовУровень звука L < 50 дБАГОСТ12.1.003-83 [26] 3. Повышенная пульсация светового излучения. Лампы дневного света. Утомление зрения. Коэффициент пульсаций, Кп=10СНиП II-4-79 [27] 4. Статическая нагрузка. Постоянная рабочая поза. Влияние на ЦНС, утомление организма. НПАОП 0.00-1.31-99 [28] 5. Недостаток естественного освещенияНеправильное расположение ПЭВМУтомление зрительного анализатораКЕО=1, 0125%СНиП II-4-79 [27] 6. Недостаток искусственного освещенияНеправильная планировка систем освещенияУтомление зрительного анализатораМинимальная освещенность Е = 500-700лкСНиП II-4-79 [27] 7. Отраженная блескостьНеправильное расположение ПЭВМУтомление зрительного анализатораДолжна отсутствовать в поле зренияДНАОП 0.00-1.31-99 [28] 8. Монотонность труда. Особенности технологического процесса. Влияние на ЦНС, утомление организма. ДНАОП 0.00-1.31-99 [28] 9. Повышенное значение напряжения в электрической цепи. Электрооборудование. Опасность поражения электричеством. Сила тока I=0.6 mA при U=220 V. ГОСТ 12.1.038-82 [25] 10. Яркость экранаЭкран монитора ПЭВМУтомление зрительных анализаторовВ = 100 кд/м2ДНАОП 0.00-1.31-99 [28]

7.2 Производственная санитария

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

7.2.1 Метеорологические условия помещения

Согласно ГОСТ 12.1.005-88 [29] оптимальные параметры микроклимата для выполнения работы должны находиться в пределах, указанных в таблице 7.2 Параметры являются оптимальными, так как категория работы III напряженная.

Категорию работы учитываем по физической нагрузке. Наша работа относится к категории Iа, то есть расход энергии при выполнении работы до 120 ккал/час и не требует физического напряжения.

Таблица 7.2 - Оптимальные параметры микроклимата

Категория работыПериод годаТемпература t, cОтносительная влажность, ?,%Скорость движения воздуха V, м/сЛегкая работа IаХолодный22.2440.600,1Легкая работа IаТеплый23.2540.600,1

Для обеспечения вышеуказанных оптимальных метеорологических условий в помещении предусмотрена система отопления (общее паровое), вентиляции (общая приточно-вытяжная искусственная) и кондиционирование согласно СНиП 2.04.05-91 [30].

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

Режим работы кондиционера должен обеспечить максимально возможное поступление наружного воздуха, но не менее 50% от производительности кондиционера.

При проектировании дисплейных классов вузов необходимо предусматривать приточно-вытяжную вентиляцию. Подача воздуха должна производиться в верхнюю зону малыми скоростями из расчета создания подвижности воздуха на рабочем месте студента менее 0,1 м/с, лучше через подшивной гофрированный потолок. Вытяжка - естественная из верхней зоны стены, противоположной оконным проемам.

Качественный состав воздуха: содержание кислорода в дисплейном классе должно быть в пределах 21-22 об. %. Двуокись углерода не должна превышать 0,1 об. %, озон - 0,1 мг/м3, аммиак - 0,2 мг/м3, фенол - 0,01 мг/м3, хлористый винил - 0,005 мг/м3, формальдегид - 0,003 мг/м3 [29].

7.2.2 Характеристика производственного помещения

Разработка производилась в трехэтажном здании Электрокорпуса на кафедре Автоматика и управление в технических системах.

По категории пожароопасности здание относится к категории В - ОНТП - 24-86 [31], класс по пожарной опасности оборудования закрытого типа - П-IIа ПУЭ-87 [23], огнестойкость конструкции здания - II степени, согласно ДБН В1.1-7-2002 [32]. В помещениях имеется система пожаротушения в соответствии с ГОСТ 12.1.004-91 [33]. Для обеспечения в помещении заданного температурного режима в соответствии с требованиями СНиП 2.04.05-91 [30] имеется централизованное отопление, вентиляция, кондиционер.

7.2.3 Виды вентиляции

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

В соответствии с СНиП 2.04.05-91 [30], вентиляция обеспечивает поддержание санитарно-гигиенических норм температуры, влажности, запыленности воздуха в рабочих помещениях. Для обеспечения необходимых санитарно-гигиенических параметров воздушной среды при эксплуатации устройства в помещении имеется естественная и искусственная вентиляция. Естественная вентиляция осуществляется через оконные проёмы и двери. Основным недостатком естественной вентиляции является то, что приточный воздух вводится в помещение без предварительной очистки и подогрева, а удаляемый воздух не очищается и загрязняет атмосферу.

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

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

7.2.4 Естественное и искусственное освещение

Работоспособность оператора во многом зависит от освещения. Неудовлетворительное освещение количественно или качественно утомляет не только зрение, но и вызывает утомление организма в целом, оказывает влияние на производительность труда оператора.

Для обеспечения нормального освещения применяется естественное, искусственное и смешанное освещения, которые нормируются СНиП 4-II-79 [27].

Лаборатория обеспечивается боковым естественным освещением в светлое время суток, в темное - системой общего искусственного освещения.

Нормированные значения КЕО, согласно СНиП 4-II-79 [27], для зданий, расположенных в I, II, IV, V поясах светового климата, определяются по следующей формуле:

(7.1)

где - значение КЕО для III пояса светового климата, составляет 1.5 СНиП 4-II - 79 [27];- коэффициент светового климата (для г. Харькова m=0,9 % - СНиП 4-II-79 [27]);- коэффициент солнечности климата, равен 0,75 т.к. окна расположены на южной стороне здания - СНиП 4-II-79 [27].

Значение КЕО для естественного освещения:

е = 1.5*0.9*0.75=1.0125%.

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

Таблица 7.3 - Характеристики производственного освещения

Точность зритель-ных работМинимальный размер объекта различе-ния, ммРазряд зритель-ной работыХарак-терис-тика типа фонаКонт-раст объекта с фономПодраз-ряд зритель-ной работыНормиро-вочное значение при освещенииЕстественном еHN, %Искуст-ном Еmin, Средней точности0,5¸1IVСред-няямалыйd1,0125300

Все производственные помещения, с постоянным нахождением в них людей, в соответствии с санитарными нормами и правилами, имеют естественное освещение.

7.2.5 Статическое электричество

Защита от статического электричества производится в соответствии с санитарно-гигиеническими нормативами допустимой надежности электрического поля. Допускаемые напряженности электрических полей не должны превышать 20 кВ/м в течение 1 часа, ГОСТ 12.1.045-84 [34].

7.3 Пожарная безопасность

Пожарная безопасность в соответствии с ГОСТ 12.1.004-91 [33] обеспечивается системами предотвращения пожара, пожарной защиты, организационно-техническими мероприятиями.

Система предотвращения пожара:

• контроль и профилактика изоляции;
• наличие плавких вставок и предохранителей в электронном оборудовании;
• для защиты от статического напряжения используется заземление;
• молниезащита зданий и оборудования согласно РД 34.21.122-87 [35].
• Для данного класса зданий и местности со средней грозовой деятельностью 10 и более грозовых часов в год, т.е. для условий г. Харькова установлена III категория молниезащиты [35].
• Для успешной эвакуации персонала при пожаре размеры двери рабочего помещения должны быть следующими:
• ширина двери не менее 1,5 м.;
• высота двери не менее 2,0 м.;
• ширина коридора 1,8 м.;
• рабочее помещение должно иметь два выхода;
• расстояние от наиболее удаленного рабочего места не должно превышать 100м.
• Организационные меры пожарной профилактики:
• обучение персонала правилам пожарной безопасности;
• издание необходимых инструкций и плакатов, плана эвакуации персонала в случае пожара.

7.4 Охрана окружающей среды

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

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

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

При изготовлении действуют экологические стандарты, которые определяют требования к производству и материалам, использующимся в конструкциях приборов. Они не должны содержать фреонов, хлоридов, бромидов и поливинилхлорида [ТСО95, BS 7750]. ТСО95 включают требования пониженного энергопотребления и ограничивают допустимые уровни мощности, потребляемые в неактивном состоянии.

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

Заключение

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

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

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

Список источников информации

1.Тоффоли Т., Марголус Н. Машины клеточных автоматов. Пер. с англ. - М.: Мир, 1991;

2.Питерсон У., Уэлдон Э. Коды исправляющие ошибки. (Перевод с английского под редакцией Добрушина Р.Л. и Самойленко С. И.) - Изд-во Мир, 1976.

.Самофалов К.Г., Романкевич А.М. и др. Прикладная теория цифровых автоматов. - К.: Вища шк. Головное изд-во, 1987.

.Варшавский В.И., Мараховский В.Б. и др. Однородные структуры. Анализ. Синтез. Поведение. - М.: Энергия, 1973.

.Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высш. шк., 1987.

.Прангвишвили И.В., Бабичева Е.В., Игнатушенко В.В. Новые принципы реализации логических и вычислительных устройств на основе однородных микроэлектронных структур // Автоматика и телемеханика. - 1963. - N019.

.Якубайтис Э.А. Логические автоматы и микромодули. Рига: Зинатне, 1975.

.Agrawal V. D., Lin C. J., Rutkowski P., Wu S. and Zorian Y. Built-In Self-Test for Digital Integrated Circuits. - AT&T Technical J., pp 30-39, Mar. /Apr. 1994.

9.Margolus N. CAM-8: a computer architecture based on cellular automata. In: Pattern Formation and Lattice-Gas Automata. - Addison-Wesley. - 1996;

10.Тоценко В.Г. Алгоритмы технического диагностирования дискретных устройств. - М.: Радио и связь, 1983.

11.Gonets G. A. A method for the design of fault detection experiments // IEEE Trans.comput. - 1970. - c-19. - N06. - p.551-558.

.Hennie F. C. Fault detection experiments for sequential circuits. - Proceeding of Fifth Symposium on Switching Circuit Theory and Logical Design, 1964, p.95-110.

13.Халчев В.Ф. Повышение контролепригодности дискретных устройств. Состояние проблемы // Измерения, контроль, автоматизация. - 1980. - N01. - с.189-197.

14.Пархоменко П.П. Основы технической диагностики. - М.: Энергия, 1976.

.Тоценко В.Г., Кисилев И.М. Метод повышения эффективности диагностирования дискретных устройств с регулярной структурой // Управляющие системы и машины. - 1977. - N05. - С.97-102.

16.Kohavi Z. Switching and finite automata theory. - New York, Morgan Hill, 1970.

.Dias F. J. Truth-table verification of an iterative logic array // IEEE Trans.comput. - 1976. - c - 25. - N06. - p.605-613.

.Shen J. P. and Ferguson F. J. The Design of Easily Testable VLSI Array Multipliers. - IEEE Trans.computers, vol.33, no.6, pp.554-560, June 1984.

.Chatterjee A. And Abraham J. A. Test Generation for Arithmetic Units by Graph Labeling. - Proc. FTCS 17, pp.284-289, Pittsburgh, Pa., July 1987.

.Hong S. J. The Design of Testable Parallel Multiplier. - IEEE Trans.computers, vol.39, no.3, pp.411-416, Mar. 1990.

.Takach A. R. and Jha N. K. Easily Testable Gate Level and DCVS Multipliers. - IEEE Trans.computer-Aided Design, vol.10, no.7, pp.932-942, July 1991.

22.Закон Украины об охране труда - 21.11.02.

.ПУЭ. Правила устройства электроустановок. - М.: Энергоатомиздат.

.ГОСТ 12.0.003-74. ССБТ. Опасные и вредные производственные факторы. Классификация. Введен 01.01.76.

25.ГОСТ 12.1.038-82 ССБТ. Электробезопасность. Предельно допустиме значения напряжения прикосновения и токов. - Введен 01.01.88.

26.ГОСТ 12.1.003-83. ССБТ. Шум. Общие требования безопасности. - Введён 01.07.89.

.СНиП II-4-79. Естественное и искусственное освещение. Нормы проектирования. - М.: Стройиздат, 1980.

.ДНАОП 0.00-1.31-99. Правила охраны труда при эксплуатации электронно-вычислительных машин. Действует с 01.01.00.

.ГОСТ 12.1.005 - 88. ССБТ. Общие санитарно-гигиенические требования к воздуху рабочей зоны. Введен 01.01.89.

.СНиП 2.04.05-91. Отопление, вентиляция и кондиционирование воздуха. - М.: Стройиздат, 1992 г.

31.ОНТП 24 - 86. Общесоюзные нормы технического проектирования. Определение категорій помещений и зданий по взрывопожарной и пожарной безопасности. М.: Стройиздат, 1986.

32.ДБН В 1.1 - 7 - 2002 Пожежна безпека обєктів будівництва. - Діє з 01.01.03

.ГОСТ 12.1.004 - 91. ССБТ. Пожарная безопасность. Общие требования. Введен 01.01.92.

.ГОСТ 12.1.006-84. ССБТ. Электростатические поля. Допустимые уровни на рабочих местах и требования к проведению контроля. - Введен 01.01.86. \

.РД 34.21.122 - 87. Инструкция по устройству молниезащиты зданий и сооружений.

Приложение А

Текст программы РЕАЛИЗАЦИИ КЛЕТОЧНОГО АВТОМАТА на языке dELPHI 7.0

UNIT ZASTAVKA;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ExtCtrls;= class (TForm): TImage;FormKeyDown (Sender: TObject; var Key: Word;: TShiftState);

{ Private declarations }

{ Public declarations };: TFormAbout;Vvodkolvokletok, Vvodpravila, Podshet;

{$R *. dfm}TFormAbout. FormKeyDown (Sender: TObject; var Key: Word;: TShiftState);_kolvokletok. Show; // показать форму. hide; // скрыть форму;.

UNIT VVODKOLVOKLETOK;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;_kolvokletok = class (TForm): TEdit;: TLabel;_kolvokletok: TButton;: TLabel;: TEdit;OK_kolvokletokClick (Sender: TObject);

{ Private declarations }

{ Public declarations };_kolvokletok: TVvod_kolvokletok;

kolvokl: integer;

// переменная, содержащая количество клеток в клеточном автомате: integer;

// переменная, содержащя количество шагов работы КА_kl: integer;

// переменная, используемая для хранения номера клетки

implementation Vvodpravila, zastavka;

{$R *. dfm}TVvod_kolvokletok. OK_kolvokletokClick (Sender: TObject);

var: integer;

// вспомогательная переменная для работы программы

// попытка работы программы: =StrToInt (kolvowagov. text);

// преобразование строкового значения в поле ввода kolvokletok в целочисленный тип(i>1) and (i<50) then

// проверка условия попадания введенного числа в допустимый диапазон

begin

kolvwagov: =i

end

else

showmessage ('Ошибка! Проверьте правильность записи. Число должно быть в диапазоне 2.50');

// в случае ошибки('Ошибка! Проверьте правильность записи. Число должно быть в диапазоне 2.50');

try

// попытка работы программы: =StrToInt (kolvokletok. text); // преобразование строкового значения в поле ввода kolvokletok в целочисленный тип(i>1) and (i<21) then // проаерка условия попадания введенного числа в допустимый диапазон

begin: =i;_kolvokletok. visible: =false;

for i: =1 to kolvokl do

// выполнять столько раз, сколько клеток в КА_kl: =i;. ShowModal;

// модальный показ формы для ввода правил клеток

end;_kolvokletok. Close;

else('Ошибка! Проверьте правильность записи. Число должно быть в диапазоне 2.20');

// в случае ошибки('Ошибка! Проверьте правильность записи. Число должно быть в диапазоне 2.20') ; .

UNIT VVODPRAVILA;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ExtCtrls;= class (TForm): TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TButton;: TButton;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TComboBox;: TLabel;: TLabel;: TLabel;: TComboBox;: TLabel;: TLabel;: TLabel;BUTEWEClick (Sender: TObject);FormShow (Sender: TObject);GOTOVOClick (Sender: TObject);

{ Private declarations }OPREDZNACHNOTN; // объявляем функциии в пределах этой формы

{ Public declarations };: TPravilokl;

f: array [1.20] of boolean;

// массив, содержащий значения клетки: array [1.20] of boolean;

// массив, содержащий предыдущие значения клетки: array [1.20,1.8,1.3,1.2] of integer;

// массив для хранения выбранных пользователем значений отрицаний: integer;

// переменная для хранения количества триад в функции возбуждения клетки: boolean;

// переменная для временного хранеия значения функции возбуждения

x: array [1.3] of boolean;

// массив для значений Xi-1, Xi, Xi+1

implementationVvodkolvokletok, Podshet, zastavka;

{$R *. dfm}

PROCEDURE Tpravilokl. OPREDZNACHNOTN;

// процедура для определения значений отрицаний, выбранных пользователемi,j: integer;

// вспомогательные переменные для организации цикла

begin[N_kl,1,1,1]: =Not11. Itemindex;[N_kl,1,2,1]: =Not12. Itemindex;[N_kl,1,3,1]: =Not13. Itemindex;[N_kl,2,1,1]: =Not21. Itemindex;[N_kl,2,2,1]: =Not22. Itemindex;[N_kl,2,3,1]: =Not23. Itemindex;[N_kl,3,1,1]: =Not31. Itemindex;[N_kl,3,2,1]: =Not32. Itemindex;[N_kl,3,3,1]: =Not33. Itemindex;[N_kl,4,1,1]: =Not41. Itemindex;[N_kl,4,2,1]: =Not42. Itemindex;[N_kl,4,3,1]: =Not43. Itemindex;[N_kl,5,1,1]: =Not51. Itemindex;[N_kl,5,2,1]: =Not52. Itemindex;[N_kl,5,3,1]: =Not53. Itemindex;[N_kl,6,1,1]: =Not61. Itemindex;[N_kl,6,2,1]: =Not62. Itemindex;[N_kl,6,3,1]: =Not63. Itemindex;[N_kl,7,1,1]: =Not71. Itemindex;[N_kl,7,2,1]: =Not72. Itemindex;[N_kl,7,3,1]: =Not73. Itemindex;[N_kl,8,1,1]: =Not81. Itemindex;[N_kl,8,2,1]: =Not82. Itemindex;[N_kl,8,3,1]: =Not83. Itemindex;

For i: =1 to kolvotriad do

// блок, предназначенный для того, чтобы если не выбрано отрицание, атоматически для переменной устанавливался "режим" без отрицания

beginj: =1 to 3 doNOTN [N_kl, i,j,1] =-1 then[N_kl, i,j,1]: =0;

// конец блока[N_kl,8,3,2]: =kolvotriad;;TPravilokl. BUTEWEClick (Sender: TObject);

begin: =kolvotriad+1;

// запоминаем, что пользователь отображает на экран ещё одну триадуkolvotriad of

// оператор выбора значения переменной, затем происходит отображение соответствующей панели с триадой

2: Triada2. Visible: =true;

: Triada3. Visible: =true;

: Triada4. Visible: =true;

: Triada5. Visible: =true;

: Triada6. Visible: =true;

: Triada7. Visible: =true;

8: Triada8. Visible: =true;;kolvotriad=8 then

// если отображается последняя 8-я триада, то сделать недоступной кнопку ещё

BUTEWE. Enabled: =false;TPravilokl. FormShow (Sender: TObject);

var: string;

// вспомогательная переменная для тображения на экране номера клетки, для которой вводится возбуждающая функция: =1;

// присваиваем начальное значение переменной, хранящей начальное количество триад. Visible: =false;

// скрываем от пользователя триады

triada3. Visible: =false;. Visible: =false;. Visible: =false;. Visible: =false;. Visible: =false;. Visible: =false;: =IntToStr (N_kl);. Caption: ='для '+s+'-й клетки';;TPravilokl. GOTOVOClick (Sender: TObject);Nachsostoyaniekl. ItemIndex of

// выбираем начальное значение

1: f [N_kl]: =false;

// заносим в массив для хранения значений функций, в данный момент тут будут содержатся начальные значения клеток

0: f [N_kl]: =false;

: f [N_kl]: =true;

end;;

// определяются значения отрицаний при переменных

if N_kl=kolvokl then. show;. close;;. close;;.PODSCHET;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class (TForm): TListBox;FormShow (Sender: TObject);FormClose (Sender: TObject; var Action: TCloseAction);

{ Private declarations }VICHISLENIEFKLETKI;

{ Public declarations };: TPodschet;Vvodpravila, Vvodkolvokletok, zastavka;

{$R *. dfm}TPodschet. VICHISLENIEFKLETKI;

// процедура для вычисления функции возбуждения клетки: boolean;

// переменная для хранения промежуточных данных функции одной триады,j,k: integer;

// вспомогательне переменные для счётчиков цикла: =false;

// присвоение для правильной работы программы

kolvotriad: =NOTN [N_kl,8,3,2];i: =1 to kolvotriad do

// цикл для каждой триады

beginj: =1 to 3 do

// цикл для каждого элемента триадыj=1 then

// если это первый элемент в триадеNOTN [N_kl, i,j,1] of

// выбираем значение из массива, 0 соответствует отсутствию отрицания, 1 - отрицанию

: triada: =x [j];

// т.к. первый элемент, то присваиваем

: triada: =not (x [j]);

// конец блока оператора выбора;

// конец блока оператора условия отбора первого элемента триады(j<>1) then // если это не первый элемент в триадеNOTN [N_kl, i,j,1] of

// выбираем значение из массива, 0 соответствует отсутствию отрицания, 1 - отрицанию

: triada: = (triada) and (x [j]);

// т.к. не первый элемент, то используем операцию логического умножения

1: triada: = (triada) and (not (x [j]));

end

// конец оператора выбора

// конец блока оператора условия отбора не первого элемента триады;

// конец цикла для каждого элемента триады: = (znachf) or (triada);

// конец цикла для каждой триады;TPodschet. FormShow (Sender: TObject);

// процедура выполняется тогда, когда на экране появляется форма: string;

// переменная для вывода результатов: integer;

// вспомогательные переменные_kl: integer;

// переменная для вычисления числа клеток, как глобальная "не прокатила"jj: =1 to kolvwagov do

// цикл по количеству шагов КА: ='';

// обнуление для правильного вывода

for N_kl: =1 to kolvokl do

// для всех клеток

begin(N_kl=1) then

// если первая клетка с учётом нулевых граничных условий

begin[1]: =false;[2]: =f [N_kl];

x [3]: =f [N_kl+1];;(N_kl=kolvokl) then

// если последнняя клетка с учётом нулевых граничных условий

begin[1]: =fpred [N_kl-1];[2]: =f [N_kl];[3]: =false;;(N_kl<>1) and (N_kl<>kolvokl) then

// для всех остальных клеток[1]: =fpred [N_kl-1];[2]: =f [N_kl];[3]: =f [N_kl+1];

end;;

// вызов процедуры вычисления значения клетки[N_kl]: =znachf;

// занесение в массив значений клеток[N_kl]: =f [N_kl];

// запоминаем предыдущее состояние клетки

if f [N_kl] =false then

// вывод на экран

vivod: =vivod+'0': =vivod+'1';. Items. Add (vivod);

// вывод на экран;TPodschet. FormClose (Sender: TObject; var Action: TCloseAction);

begin. close;

// закрыть главную форму, т.е. завершить работу программы;.

Приложение Б

Внешний вид программы МОДЕЛИРОВАНИЯ СЕТИ КЛЕТОЧНЫХ АВТОМАТОВ. описание элементов управления

При запуске программы отображается информационное окно (рис.1).

Рисунок 1 - Информационное окно

После нажатия любой клавиши при появлении первого окна, на экран выводится окно ввода исходных данных (рис.2).

Рисунок 2 - Окно ввода исходных данных

Это окно содержит поле для ввода количества элементов клеточного автомата и количество шагов эволюции. Также в этом окне находится кнопка "ОК", при нажатии которой происходит переход к окну ввода правил функционирования КА.

Рисунок 3 - Окно ввода правила функционирования клетки

В окне ввода правила существуют следующие элементы управления и ввода данных:

. Начальное состояние клетки - поле типа список, где возможен выбор из 2-х значений - "0" или "1". По умолчанию значение "0"

. Информационное поле. Показывает для какой по счёту клетки вводится правило.

. Поле триады. Даёт возможность пользователю выбирать отрицания при переменных. "n" - отрицание, "-" отсутствует. По умолчанию значение "-".

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

. Кнопка "Готово". При нажатии этой кнопки происходит переход к окну вывода результатов вычисления (рис.4).

Рисунок 4 - окно вывода результатов вычисления

Содержание Перечень обозначений и сокращений Реферат Введение 1. Основные понятия теории клеточных автоматов 1.1 Основные определения и понят

Больше работ по теме: