Тема 3.2. Сети и коллективы автоматов

1. Автоматы можно различным образом соединять в единую структуру;

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

3. Результирующий автомат является более сложным, чем сумма исходных автоматов (например, из сравнения числа состояний);

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

Лекция 6.

Тема 3.3. Абстрактный синтез микропрограммных автоматов (мпа) по гса.

Не полностью определенные автоматы

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

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

Наиболее распространен двоичный структурный алфавит.

В дальнейшем будем иметь ввиду именно двоичный структурный алфавит.

Символы входного и выходного алфавитов, символы состояний можно закодировать векторами конечной длины, компоненты которых принимают два значения: 0 и 1.

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

Например, .

Найдем:

	0	0	0
	0	0	1
	0	1	0
	0	1	1
	1	0	0

Тема 3.4. Структурный синтез микропрограммных автоматов по гса

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

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

1. Сигналы структурного выходного алфавита как функции от сигналов структурного входного алфавита и сигналов структурного алфавита состояний автомата;

2. Внутренние сигналы автомата как функции сигналов и .

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

П - элемент памяти, представляющий собой элементарный автомат Мура.

- вектор состояния автомата, заданный символами структурного алфавита состояний.

- вектор функций управления элементами возбуждения элементов памяти автомата.

- вектор выходных сигналов, заданный символами структурного выходного алфавита .

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

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

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

1. кодирования выходных сигналов абстрактного алфавита;

2. состояния автомата, т.е. от вектора ;

3. для автомата Мили – от вектора .

Поэтому сигналы выходного алфавита могут быть описаны в виде булевых функций:

…

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

1. от кодов , ;

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

Сигналы алфавита также могут быть заданы в виде булевых функций:

…

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

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

Кодирование ГСА и разметка состояний автомата. Построение

графа переходов и таблиц переходов и выходов.

Процесс синтеза автомата зависит от следующих факторов:

• от критерия синтеза:

  • минимум оборудования;

  • максимум быстродействия;

• от типа автомата (Мили, Мура);

• от элементной базы;

• от способа кодирования состояний.

Синтез осуществляется в несколько этапов:

1. Разметка ГСА

2. Построение таблиц переходов

3. Получение логических функций для выходных сигналов и функций возбуждения.