Синтез цифрового автомата

Введение.

 

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

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

Цель курсовой работы: изучить теоретическую основу разработки цифрового автомата и  научится работать в ней.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пояснительная записка

Глава I. Синтез абстрактного  автомата.

1. Исходные данные.

Дана исходная таблица переходов и выходов:

	1	2	3	4	5	6	7	8	9	10
X1	--/y2	5/--	1/y2	3/y2	10/--	3/--	4/у2	--/y2	1/--	3/y2
X2	3/y1	3/y1	6/--	3/y1	--/y1	--/y1	6/y1	9/y1	6/y1	8/у2
X3	7/--	7/у2	5/y1	2/y2	--/y2	7/y2	--/y2	6/у1	5/у2	2/y2
X4	10/y2	10/y2	4/y2	6/y2	4/y1	10/y2	4/y2	1/y2	4/--	--/--
X5	8/y2	8/y2	2/--	9/у1	2/у2	8/--	2/--	4/--	2/y2	3/y2

 

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

Таблица переходов:

	1	2	3	4	5	6	7	8	9	10
X1	--	5	1	10	3	5	--	5	1	3
X2	3	3	6	3	--	--	6	9	5	8
X3	7	7	5	2	--	7	--	6	5	2
X4	10	10	4	6	4	10	4	1	4	--
X5	8	8	2	9	2	8	2	4	2	3

 

Таблица выходов:

	1	2	3	4	5	6	7	8	9	10
X1	Y2	--	Y2	--	--	Y2	Y2	Y1	--	Y1
X2	Y1	Y1	--	Y1	Y1	Y1	Y1	Y1	Y1	Y2
X3	--	Y2	Y2	Y2	Y2	Y2	Y2	Y1	Y2	Y2
X4	Y2	Y2	Y2	Y2	Y1	Y2	Y2	Y2	--	--
X5	Y2	Y2	--	Y1	Y2	--	--	--	Y2	Y2

 

 

 

 

 

2. Минимизация по алгоритму Ангера – Пола

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

По степени  совместимости состояния бывают:

• Абсолютно несовместимые – состояния имеющие разные выходные сигналы.
• Абсолютно совместимые – состояния, имеющие одинаковые выходные сигналы и равные функции перехода.
• Условно совместимые – состояния, совместимые при условии равенства функций выхода и эквивалентности функций перехода.

1. Составление треугольной матрицы

Для нахождения минимального частично-определенного автомата необходимо составить треугольную матрицу Ангера-Полла.

Треугольная матрица заполняется в 3 этапа:

1 этап:

На первом этапе  мы определяем абсолютно несовместимые состояния, попарно сравнивая столбцы в таблице выходов.

Если значение не равно значению , то ставим «X» в соответствующей ячейке.

2 этап:

На втором этапе  мы определяем абсолютно-совместимые состояния, попарно сравнивая столбцы в таблице переходов, пропуская те пары, что мы определили как абсолютно несовместимые. Если состояния одинаковы при одинаковых сигналах, то ставим «V» в соответствующей ячейке.

3 этап:

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

После выполнения описанных действий мы получим матрицу Ангера-Пола:

2	V
3	3-6, 2-8, 5-7, 4-10	5-1, 8-2, 3-6, 2-5
4	X	X	1-10, 6-4, 6-3, 2-3, 5-2
5	10-4, 8-2	X	X	X
6	V	V	1-5, 2-8, 5-7, 4-10	X	3-5, 4-10, 2-8
7	3-6, 4-10, 8-2	3-6, 4-10, 2-8	V	X	4-4, 2-2	10-4, 8-2
8	3-9, 4-8, 6-7, 10-1	X	X	X	X	X	X
9	3-6, 9-2, 9-7, 4-10	1-5, 4-10, 6-3, 8-2, 5-7	V	X	1-3, 4-4, 2-2	5-1, 8-2, 10-4	X	3-6, 4-2, 6-5, 1-4
10	X	X	X	X	X	X	X	X	1-3, 2-5, 6-8, 5-2
	1	2	3	4	5	6	7	8	9

       1.2.2 Определение  совместимых состояний

Для нахождения несовместимых (а так же совместимых) пар состояний треугольная таблица просматривается по столбцам, начиная с нижнего правого (т.е. 9-10). С правого нижнего столбца мы ищем первую ячейку, отмеченную крестом. В нашем случае это (8,10).Тогда во всех клетках, где есть пара (8,10), ставится крест. Эту процедуру мы проводим для всех клеток, отмеченных крестом (в том числе и свежеотмеченные), и заканчиваем, когда таких клеток не остаётся. В этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами – несовместимым.

В итоге получаем окончательный вариант матрицы Ангера-Пола:

2	V
3	X	X
4	X	X	X
5	X	X	X	X
6	V	V	X	X	X
7	X	X	V	X	X	X
8	X	X	X	X	X	X	X
9	X	X	V	X	X	X	V	X
10	X	X	X	X	X	X	X	X	X
	1	2	3	4	5	6	7	8	9

 

После выполнения этих действий мы получаем совместимые  пары состояний – 1-2, 1-6, 2-6,  3-7, 3-9, 7-9.

1.2.3 Минимизированный цифровой автомат

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

1. (S₇;S₉)  Ф=(7,9)
2. (S₃;S₉ )&(S₃;S₇)&(S₇;S₉) Ф=(3,7,9)
3. (S₂;S₆) Ф=(2,6)
4. (S₁;S₆)&(S₁;S₇)&(S₆;S₂)  Ф=(1,6,2)

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

      b₁={1,2,6}, b₂={4}, b₃={5},b₄={3,7,9}, b₅={8}, b₆={10}.

Из этого  получаем, что в минимизированном автомате будет 6 состояний, 5 входных сигналов и 2 выходных сигнала.

 

Построим таблицы переходов и выходов минимизированного автомата.

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

Например: в b1 входят состояния {1,2,6}. При входном сигнале x1 они все перейдут в состояние {5}, входящее в b3. Значит на пересечении {b1,x1} таблицы переходов минимизированного автомата мы запишем b3. Таким способом заполняем все ячейки.

Таблица переходов минимизированного автомата:

δ	b1	b2	b3	b4	b5	b6
x1	b3	b6	b4	b1	b3	b4
x2	b4	b4	b1	b1	b4	b5
x3	b4	b1	b1	b3	b1	B1
x4	b6	b1	b2	b2	b1	b1
x5	b5	b4	b1	b1	b2	b4

 

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

Таблица выходов минимизированного автомата:

λ	b1	b2	b3	b4	b5	b6
x1	y2	y1	y1	y2	y1	y1
x2	y1	y1	y1	y1	y1	y2
x3	y2	y2	y2	y2	y1	y2
x4	y2	y2	y1	y2	y2	y1
x5	y2	y2	y2	y2	y1	y2

 

3. Декомпозиция автоматов