Минимизация абстрактного автомата

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

КУРСОВОЙ ПРОЕКТ

ПО ДИСЦИПЛИНЕ

“ТЕОРИЯ АВТОМАТОВ”

Санкт-Петербург 2009

Минимизация абстрактного автомата, заданного таблицей переходов/выходов

Таблица 1

	s1	s2	s3	s4	s5	s6	s7	s8
x1	s8	s1	s4	s2	s7	s4	s3	s3
x2	s4	s6	s5	s8	s4	s5	s2	s2
x3	s2	s4	s8	s6	s2	s7	s5	s1

Тождественных состояний нет.

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

Таблица 2

	s1	s2	s3	s4	s5	s6	s7	s8
x1	y3	y2	y3	y3	y3	y3	y2	y2
x2	y2	y1	y2	y2	y2	y2	y1	y1
x3	y1	y3	y1	y1	y1	y1	y3	y3
	B1	B2	B1	B1	B1	B1	B2	B2

Получаем:

={B1, B2}, где B1={s1, s3, s4, s5, s6},

B2={s2, s7, s8}

Строим таблицу 1-разбиения. (По предыдущей строке и таблице №1.)

Таблица 3

I	B1	B2
	s1	s3	s4	s5	s6	s2	s7	s8
x1	B2	B1	B2	B2	B1	B1	B1	B1
x2	B1	B1	B2	B1	B1	B1	B2	B2
x3	B2	B2	B1	B2	B2	B1	B1	B1
	C1	C2	C3	C1	C2	C4	C5	C5

Находим из этой таблицы разбиение на 2-классы:

={C1, C2, C3, C4, C5}, где C1={s1, s5},

C2={s3, s6},

C3={s4},

C4={s2},

C5={s7, s8}

Строим таблицу 2-разбиения.

Таблица 4

II	C1	C2	C3	C4	C5
	s1	s5	s3	s6	s4	s2	s7	s8
x1	C5	C5	C3	C3	C4	C1	C2	C2
x2	C3	C3	C1	C1	C5	C2	C4	C4
x3	C4	C4	C5	C5	C2	C3	C1	C1
	D1	D1	D1	D1	D3	D4	D5	D5

Находим из этой таблицы разбиение на 3-классы:

= {D1, D2, D3, D4, D5}, где C1=D1, C2=D2, C3=D3, C4=D4, C5=D5

Таким образом, найдены -классы, которым соответствует автомат Мили, описываемый таблицами:

Таблица 5. Переходов. (Заменяем s5 на s1, s6 на s3, s8 на s7. Сначала смотрим на таблицу №4, потом на пи-2)

	s1	s3	s4	s2	s7
x1	s7	s4	s2	s1	s3
x2	s4	s1	s7	s3	s2
x3	s2	s7	s3	s4	s1

Таблица 6. Выходов

	s1	s3	s4	s2	s7
x1	y3	y3	y3	y2	y2
x2	y2	y2	y2	y1	y1
x3	y1	y1	y1	y3	y3

Строим граф минимизированного автомата. (Берем ячейку s1:x1 из таблиц №5 и №6: линия с подписью x1/y3 выходит из s1 и входит в s7. И так далее все ячейки.)

б) Таблица реакций исходного и оптимизированного автоматов на входное воздействие.

Таблица 7

	s1	s2	s3	s4	s5	s6	s7	s8
входное воздействие	x2	x3	x2	x3	x3	x2	x1	x3
реакция исходного автомата	y2	y3	y2	y1	y1	y2	y2	y3
реакция минимизированного автомата	y2	y3	y2	y1	y1	y2	y2	y3

в) Синтез автомата на элементах ИЛИ-НЕ и Т-тригерах.

Т-триггер по каждому такту изменяет своё логическое состояние на противоположное при единице на входе Т, и не изменяет выходное состояние при нуле на входе T. Т-триггер часто называют счётным триггером. Т-триггер может строиться как на JK, так и на D-триггерах.

Таблица истинности

T	Q(t)	Q(t+1)
0	0	0
0	1	1
1	0	1
1	1	0

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

1. Выбираем количество триггеров. Так как автомат имеет 5 состояний, то требуется:

q= ]log25[ =3 триггера.

2. Кодирование внутренних состояний входных и выходных сигналов.

Входной алфавит: X={x1, x2, x3}. Для кодирования необходимо:

]log₂3[ =2 разряда.

Обозначим структурное представление входов автомата символами x” и x'.

Выходной алфавит: Y={y1, y2, y3}. Для кодирования необходимо:

]log₂3[ =2 разряда.

Обозначим структурное представление выходов автомата символами y” и y'.

Алфавит состояний: S={s1, s2, s3, s4, s7}. Обозначим структурное представление состояний символами q1, q2 и q3.

Таблица 8

x	x”	x'
x1	0	0
x2	0	1
x3	1	1

Таблица 9

y	y”	y'
y1	1	0
y2	1	1
y3	0	0

Таблица 10

s	q1	q2	q3
s1	0	0	0
s2	0	0	1
s3	0	1	0
s4	0	1	1
s7	1	0	0

3. Составляем таблицы переходов. (Составляется на основании графа переходов и таблиц 8-10.)

Таблица 12

			входн	выходн	k(Sn)	k(Sn+1)	д
N	Sn	Sn+1	xi	x”	x'	yi	y”	y'	q1	q2	q3	q1	q2	q3	g1	g2	g3
1	s1	s7	x1	0	0	y3	0	0	0	0	0	1	0	0	+	0	0
2	s1	s4	x2	0	1	y2	1	1	0	0	0	0	1	1	0	+	+
3	s1	s2	x3	1	1	y1	1	0	0	0	0	0	0	1	0	0	+
4	s2	s1	x1	0	0	y2	1	1	0	0	1	0	0	0	0	0	-
5	s2	s3	x2	0	1	y1	1	0	0	0	1	0	1	0	0	+	-
6	s2	s4	x3	1	1	y3	0	0	0	0	1	0	1	1	0	+	1
7	s3	s4	x1	0	0	y3	0	0	0	1	0	0	1	1	0	1	+
8	s3	s1	x2	0	1	y2	1	1	0	1	0	0	0	0	0	-	0
9	s3	s7	x3	1	1	y1	1	0	0	1	0	1	0	0	+	-	0
10	s4	s2	x1	0	0	y3	0	0	0	1	1	0	0	1	0	-	1
11	s4	s7	x2	0	1	y2	1	1	0	1	1	1	0	0	+	-	-
12	s4	s3	x3	1	1	y1	1	0	0	1	1	0	1	0	0	1	-
13	s7	s3	x1	0	0	y2	1	1	1	0	0	0	1	0	-	+	0
14	s7	s2	x2	0	1	y1	1	0	1	0	0	0	0	1	-	0	+
15	s7	s1	x3	1	1	y3	0	0	1	0	0	0	0	0	-	0	0

4. Составляем карты Карно для выходных функций (элементная база ИЛИ-НЕ).

Таблица 13 (для y”)

						q1q2q3
	0	1	0	0	X	X	X	1
	1	1	1	1	X	X	X	1
x”x'	1	0	1	1	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица 14 (для y')

						q1q2q3
	0	1	0	0	X	X	X	1
	1	0	1	1	X	X	X	0
x”x'	0	0	0	0	X	X	X	0
	X	X	X	X	X	X	X	X

5. Составляем карты Карно функций возбуждения триггеров.

T=U{+, -, (Ш)}

Таблица 15 (для g1)

						q1q2q3
	+	0	0	0	X	X	X	-
	0	0	+	0	X	X	X	-
x”x'	0	0	0	+	X	X	X	-
	X	X	X	X	X	X	X	X

Таблица 16 (для g2)

						q1q2q3
	0	0	-	1	X	X	X	+
	+	+	-	-	X	X	X	0
x”x'	0	+	1	-	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица 17 (для g3)

						q1q2q3
	0	-	1	+	X	X	X	0
	+	-	-	0	X	X	X	+
x”x'	+	1	-	0	X	X	X	0
	X	X	X	X	X	X	X	X

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

г) Синтез автомата на элементах И-НЕ и JK-триггерах.

JK - триггер универсален и работает по правилу RS (вход J=S, вход K=R), причем отличается от последнего тем, что комбинация J=K=1 не является запрещенной. При действии этих сигналов он изменяет свое состояние на противоположное тому, в котором находился.

JK - триггер является универсальным двухступенчатым синхронным логическим устройством с двумя информационными входами и двумя выходами. Триггер собран по схеме master - slave и представляет собой два триггера в одном корпусе. Один из входов JK - триггера всегда заблокирован нулевым сигналом с выхода Q или не . В результате этого триггер не имеет запрещенных состояний и позволяет одновременную подачу двух единиц на входы J и K.

JK - триггер может работать в режиме RS - триггера, в режиме D - триггера и в режиме счетного входа, т.е. Т -триггера.

Пункты 1-3 аналогичны пунктам 1-3 предыдущего задания.

4. Составляем карты Карно для выходных функций.

Таблица 18. (для y”)

						q1q2q3
	0	1	0	0	X	X	X	1
	1	1	1	1	X	X	X	1
x”x'	1	0	1	1	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица 19 (для y')

						q1q2q3
	0	1	0	0	X	X	X	1
	1	0	1	1	X	X	X	0
x”x'	0	0	0	0	X	X	X	0
	X	X	X	X	X	X	X	X

5. Составляем карты Карно функций возбуждения триггеров

J=U{+,(-),(1),(Ш)};

K=U{-,(+),(0),(Ш)}.

Таблица 20 (для J1) (такая же, как и для g1)

						q1q2q3
	+	0	0	0	X	X	X	-
	0	0	+	0	X	X	X	-
x”x'	0	0	0	+	X	X	X	-
	X	X	X	X	X	X	X	X

Таблица 21 (для K1) (такая же как для g1)

						q1q2q3
	+	0	0	0	X	X	X	-
	0	0	+	0	X	X	X	-
x”x'	0	0	0	+	X	X	X	-
	X	X	X	X	X	X	X	X

K1=1

Таблица 22 (для J2)

						q1q2q3
	0	0	-	1	X	X	X	+
	+	+	-	-	X	X	X	0
x”x'	0	+	1	-	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица 23 (для K2)

						q1q2q3
	0	0	-	1	X	X	X	+
	+	+	-	-	X	X	X	0
x”x'	0	+	1	-	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица 24 (для J3)

						q1q2q3
	0	-	1	+	X	X	X	0
	+	-	-	0	X	X	X	+
x”x'	+	1	-	0	X	X	X	0
	X	X	X	X	X	X	X	X

Таблица №25 (для K3)

						q1q2q3
	0	-	1	+	X	X	X	0
	+	-	-	0	X	X	X	+
x”x'	+	1	-	0	X	X	X	0
	X	X	X	X	X	X	X	X

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

микропрограмма минимизация автомат таблица

1) Разработка микропрограммного автомата, реализующего микропрограмму, заданную таблицей.

Составляем граф функционирования по ТМА.

Составляем отмеченную граф-схему алгоритма (ГСА).

Строим абстрактную и структурную таблицы переходов (таблица 27).

Таблица 26

	Q4	Q2	Q1
	0	1	1
	0	0	1
	0	1	0
	0	0	0
	1	0	0
	1	0	1
	1	1	1

Таблица 27 (составляется по отмеченной ГСА и таблице 26)

N	текущ сост	будущ сост	вход сост {Z}	выход сост {Y}	K()	K()	д
					Q4	Q2	Q1	Q4	Q2	Q1	Q4	Q2	Q1
1					0	1	1	0	1	1	0	1	1
2				()	0	1	1	0	0	1	0	-	1
3			1	()	0	0	1	0	1	0	0	+	-
4				()	0	1	0	0	1	0	0	1	0
5					0	1	0	0	0	0	0	-	0
6			1		0	0	0	1	0	0	+	0	0
7					1	0	0	1	0	0	1	0	0
8					1	0	0	1	0	1	1	0	+
9					1	0	1	1	1	1	1	+	1
10					1	0	1	0	0	0	-	0	-
11					1	1	1	1	0	1	1	-	1
12					1	1	1	0	0	1	-	-	1

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

Таблица 28

	Контермы
	Q2 Q1
	Q2 Q1
	Q1
	Q2
	Q2
	Q4
	Q4
	Q4 Q1
	Q4 Q1
	Q4 Q2 Q1
	Q4 Q2 Q1

Таблица 29. (функции выходов - по столбцу выходные состояния, а функции возбуждения - по последнему столбцу таблицы 27)

функции выходов	функции возбуждения D={+,1}
=
=
=
=
=
=
=

Схемная реализация автомата.

Функциональная схема.

2) Разработка счетчика числа микрокоманд, работающего в двоично-десятичном коде заданном таблицей 30.

Таблица 30

№	0	1	2	3	4	5	6	7	8	9	код
3	0000	0001	0011	0101	0111	1000	1010	1100	1110	1111	5211

Этап I. Абстрактный синтез счетчика.

Шаг 1. Выбор количества триггеров. Так как N=10, то

q= ]log₂10[ =4 триггера

Обозначим их А, Б, В, Г.

Шаг 2. Кодирование внутренних состояний.

Шаг 3. Составление таблиц переходов.

Таблица 31

Текущие состояния в момент n	Будущие состояния в момент n+1	Операторы перехода д
А	Б	В	Г	А	Б	В	Г	А	Б	В	Г
0	0	0	0	0	0	0	1	0	0	0	+
0	0	0	1	0	0	1	1	0	0	+	1
0	0	1	1	0	1	0	1	0	+	-	1
0	1	0	1	0	1	1	1	0	1	+	1
0	1	1	1	1	0	0	0	+	-	-	-
1	0	0	0	1	0	1	0	1	0	+	0
1	0	1	0	1	1	0	0	1	+	-	0
1	1	0	0	1	1	1	0	1	1	+	0
1	1	1	0	1	1	1	1	1	1	1	+
1	1	1	1	0	0	0	0	-	-	-	-

Шаг 4. Составление обобщенных карт Карно.

Таблица 32

	ВГ
АБ	00	01	11	10
00	0	0	0	Х
01	Х	0	+	Х
11	1	Х	-	1
10	1	Х	Х	1

Таблица 33

	ВГ
АБ	00	01	11	10
00	0	0	+	Х
01	Х	1	-	Х
11	1	Х	-	1
10	0	Х	Х	+

Таблица 34

	ВГ
АБ	00	01	11	10
00	+	1	1	Х
01	Х	1	-	Х
11	0	Х	-	+
10	0	Х	Х	0

Таблица 35

	ВГ
АБ	00	01	11	10
00	0	+	-	Х
01	Х	+	-	Х
11	+	Х	-	1
10	+	Х	Х	-

Этап II. Структурный синтез счетчика.

Шаг 5. Выбор элементной базы и типа триггеров. Элементная база {ИЛИ-НЕ}. В качестве запоминающих устройств выбираем универсальные синхронные JK-триггеры.

Шаг 6. Вывод логических выражений для сигналов возбуждения JK-триггеров.

J=U{+,(-),(1),(Ш)};

K=U{-,(+),(0),(Ш)}.

Шаг 7. Схемная реализация счетчика. См. приложение 7.

3) Разработка таймера для счетчика из п. 2.

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

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

Таблица 36

N	входные сигналы	выходные сигналы
1	0	0	0	0	0	1	0	0	0	1
2	0	0	0	0	1	0	0	0	1	0
3	0	0	0	1	0	0	0	1	0	0
4	0	0	1	0	0	0	1	0	0	0
5	0	1	0	0	0	0	1	0	1	0
6	1	0	0	0	0	0	1	1	0	0

По таблице запишем логические выражения

+

Размещено на Allbest.ru