Абстрактный синтез дискретного автомата

ВВЕДЕНИЕ

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

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

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

абстрактный синтез дискретного автомата

Рассмотрим содержание и особенности определенных этапов синтеза на примере

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

.

Определяем мощность входного и выходного множества М_х=5 М_у=4.Строим первичную таблицу переходов-выходов автомата Мура, как показано в соответствии с таблицей 1.

Таблица 1.1 ­ Первичная таблица переходов-выходов автомата Мура

х	Состояния S и выходные сигналы Y
			-	-	-	-	-	-	-
	-			-	-			-	-	-
	-	-			-	-
	-	-	-			-	-	-	-	-
	-	-	-	-			-			-

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

Решение этой задачи выполним методом Ауфенкампа и Хона основанного на понятии эквивалентных состояний.

Эквивалентным состоянием называется s_n и s_m такие состояния которым во-первых соответствуют одинаковые входные сигналы y(t) а во вторых переход из состояний s_n и s_mпод воздействием любого символа приводит к одному и тому же эквивалентному состоянию[3].

Алгоритм минимизации:

1. Методом последовательного разбиения выделяем все попарно эквивалентные состояния.

2. Объединяем эквивалентные состояния в одиночные классы у₁ у₂и выделяем в каждом классе по одному состоянию для выполнения последующих этапов при разбиении на классы пустые клетки во внимание не принимаются.

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

Первичный граф переходов-выходов автомата Мура представлен в соответствии с рисунком 1.

Рисунок 1 - Первичный граф переходов-выходов автомата Мура

Первое разбиение состояний на классы выполняем по выходным сигналам как показано в таблице 2.Анализ показывает что в классе у₁ состояние s₁ не является эквивалентным основным состоянием этого класса так как при поступлении сигнала х₁ автомат переходит из состояния s₁ в класс состояний у₂ в отличии от других состояний класса переводящих автомат под действием сигнала х₁ в состояния класса у₁[4].

Таблица 2 - Разбиение на классы автомата Мура

х	Состояния S и выходные сигналы Y
			-	-	-	-	-		-	-
	-		-		-		-	-		-
	-	-	-			-
	-	-		-	-	-		-	-	-
	-	-		-			-	-	-
Кл.

Таблица 3 - Переходы-выходы автомата Мура

x	Состояния Г и выходные сигналы Y
		-		-	-	-
			-			-
	-			-
		-		-	-	-
			-		-

Таблица 4 - Первичная таблица возбуждения

Таблица 5 - Вторичная таблица возбуждения

Продолжение таблицы 5