Модули сигнатурного мониторинга на клеточных автоматах - Дипломная работа

Стремительный рост сложности современных систем управления технологическими процессами и оборудованием вызывает необходимость решения многих проблем, среди которых важное место занимают вопросы обеспечения необходимого уровня отказоустойчивости, работоспособности, продуктивности и быстрой адаптации к классу решаемых задач. Одним из эффективных путей достижения высоких показателей надежности систем управления на основе микроконтроллеров является введение аппаратной, программной и временной избыточности, которые обеспечивают отказоустойчивость в случае присутствия дефектов определенного класса. Развитие субмикронных технологий, широкое применение сигнальных процессоров, микроконтроллеров и программируемых интегральных схем с числом выходов, которое достигает 1000 на одну микросхему, которые функционируют на тактовой частоте 1ч5 ГГц, приводит к значительному увеличению стоимости диагностирующего оборудования на всех этапах жизни управляющих систем. Существующие системы диагностического обеспечения дискретных устройств и систем на одном кристалле, подсистемы генерации тестов и моделирования неисправностей в большинстве случаев ориентированы на выявление класса неисправностей константного типа, что неадекватно отображает множество дефектов в субмикронной технологии. В связи с этим, разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга на клеточных автоматах является актуальной проблемой, учитывая их экономичность и высокую производительность. 1. Основные понятия теории клеточных автоматов 1.1 Основные определения и понятия Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей [1]. Каждая клетка характеризуется определённым значением из некого множества. Совокупность состояний всех клеток решётки называется состоянием решётки. Время в рассматриваемой модели дискретно и каждая итерация соответствует некому моменту времени. Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий момент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Пометим какие-либо клетки на первом листе, сформировав тем самым начальное состояние решётки. Таким образом, можно реализовать клеточный автомат «Жизнь», который обладает множеством интересных свойств и любопытнейшей историей [3]. В-пятых, автомат работает итерационно. Поэтому выше было оговорено, что это - свойства «классических» клеточных автоматов. 1.3 Двумерный клеточный автомат Клеточный автомат (КА) может быть описан с помощью определения следующих основных свойств: окрестности, количества состояний КА, функции, с помощью которой клеточный автомат вычисляет свое последующее состояние (в дальнейшем - правило). Впервые определение окрестности было дано Фон Нейманом [4]. Ниже последнее утверждение будет доказано Рисунок 1.1 - Треугольная решетка клеточного автомата Рисунок 1.2 - Квадратная решетка клеточного автомата Рисунок 1.3 - Гексагональная решетка клеточного автомата Теорема 1. В дальнейшем, если рассматривается СКА без специально определенных свойств, имеется в виду одномерная СКА, состоящая из КА, которые имеют два состояния, с взаимосвязями между клетками, определенными для окрестности Фон Неймана. На рис. 1.4 показана структура одномерной линейной СКА, длинны n, с нулевыми граничными условиями. Рисунок 1.4 - Одномерная n-клеточная СКА с нулевыми граничными условиями Каждая ячейка СКА - КА, имеющий два состояния, структура которого представлена на рис. 1.5. В таблице 2.1 представлен пример численного значения правила Таблица 1.1 - Пример вычисления численного значения правила 111 110 101 100 011 010 001 000 Правило 144 1 0 0 1 0 0 0 0 Правило 65 0 1 0 0 0 0 0 1 Степень 2 7 6 5 4 3 2 1 0 Правило 144 = 27 24 Правило 65 = 26 21 Аналогично вычисляется численное значение для любого правила. Такие клеточные автоматы получили название автоматов-трансдюсеров, то есть - преобразователей входных сигналов в выходные. Создана игра «Жизнь» была в 1970 году Джоном Хортоном Конуэем, математиком Кембриджского университета. Определение 3.1 Пусть В подмножество Z.