Цифровые автоматы. Синтез автомата для преобразования двоично-десятичного кода с весами 4.3.2.1

Министерство Высшего и среднего специального образования России

Нижегородский государственный

технический университет

Кафедра “Вычислительная техника”

Курсовая работа по теме

“Цифровые автоматы”

Выполнил: ст. гр. 97-В-2

                                                                                Голов. С.А

 Проверил:

Нижний Новгород

1998 год

Содержание:

Техническое задание: .................................................................................................................................

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

МИНИМИЗАЦИЯ АВТОМАТА............................................................................................................................. 9

Структурный синтез автомата.......................................................................................................... 10

Реализация автомата на микросхемах малой степени интеграции............... 12

Реализация автомата на микросхемах средней степени интеграции........... 15

Реализация автомата на микросхемах большой степени интеграции......... 16

Техническое задание:

Синтезировать автомат для преобразования двоично-десятичного кода с весами 4.3.2.1, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код с весами 3.3.2.1, который снимается с выхода автомата в последовательной форме, начиная со старшего разряда. Провести синтез абстрактного автомата Мили и Мура по первой и второй стратегии. Для каждого автомата привести таблицы переходов и выходов, а также графы работы. По автомату с наименьшим числом внутренних состояний построить структурный автомат. Для структурного автомата провести минимизацию. Провести синтез комбинационной схемы автомата на микросхемах малой, средней и большой степени интеграции серии К155.

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

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

# набора	Веса входного слова				Веса выходного слова
	4	3	2	1	3	3	2	1
0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	1
2	0	0	1	0	0	0	1	0
3	0	1	0	0	0	1	0	0
4	0	1	0	1	0	1	0	1
5	0	1	1	0	0	1	1	0
6	0	1	1	1	0	1	1	1
7	1	0	1	1	1	1	0	1
8	1	1	0	1	1	1	1	0
9	1	1	1	0	1	1	1	1

ZДОП	W*
Z0 Z0 Z0 Z0	W0 W0 W0 W0
Z0 Z0 Z0 Z1	W0 W0 W0 W1
Z0 Z0 Z1 Z0	W0 W0 W 1W0
Z0 Z1 Z0 Z0	W0 W1 W0 W0
Z0 Z1 Z0  Z1	W0 W1 W0 W1
Z0Z1 Z1 Z0	W0 W1 W1 W0
Z0 Z1 Z1 Z1	W0 W1 W0 W1
Z1 Z0 Z1 Z1	W1 W1 W0 W1
Z1 Z1 Z0 Z1	W1 W1 W1 W0
Z1 Z1 Z1 Z0	W1 W1 W1 W1

Таблица №2

Информационно нагруженное дерево:

Граф автомата МУРА:

-

w0

W1

w0

w0

w0

w1

w1

w0

w1

w0

w1

w1

a1

a2

A3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

Z0

a2

a4

a6

a5

a9

a14

a13

-

-

a11

-

-

-

Z1

-

a3

a7

a10

a8

a15

a12

-

-

-

-

-

-

	w0	w1	w1	w1	w0	w1	w0	w1	w0	w1	w0
	a14	a15	a16	a17	a18	a19	a20	a21	a22	a23	a24
Z0	-	-	a17	-	-	-	a21	a22	a24	-	-
Z1	-	-	a20	a18	a19	-	a23	-	-	-	-

Таблица №3

Граф автомата МИЛИ:

 

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

Z0

a2 w0

a4 w0

a7 w0

a8 w0

a11 w0

a14 w1

- -

a1 w0

a1 w0

a1 w0

a1 w0

- -

- -

- -

Z1

a3 w1

a5 w1

a6 w0

a9 w1

a10 w1

a13 w1

a12 w1

a1 w1

- -

a1 w1

a1 w1

a1 w1

a1 w0

a1 w0

Таблица №4

Разметка автомата Мили  по первой  стратегии					Разметка автомата Мили  по второй стратегии
Z0	Z0	Z0	Z0		Z0	Z0	Z0	Z0
W0	W0	W0	W0		W0	W0	W0	W0
1	2	3	4	1	1	2	3	4	1
Z0	Z0	Z0	Z1		Z0	Z0	Z0	Z1
W0	W0	W0	W1		W0	W0	W0	W1
1	2	3	4	1	1	2	3	4	1
Z0	Z0	Z1	Z0		Z0	Z0	Z1	Z0
W0	W0	W1	W0		W0	W0	W1	W0
1	2	3	5	1	1	2	3	5	1
Z0	Z1	Z1	Z0		Z0	Z1	Z1	Z0
W0	W1	W1	W0		W0	W1	W1	W0
1	2	6	7	1	1	2	6	7	1
Z0	Z1	Z1	Z1		Z0	Z1	Z1	Z1
W0	W1	W1	W1		W0	W1	W1	W1
1	2	6	7	1	1	2	6	7	1
Z0	Z1	Z0	Z1		Z0	Z1	Z0	Z1
W0	W1	W0	W1		W0	W1	W0	W1
1	2	6	8	1	1	2	6	8	1
Z0	Z1	Z0	Z0		Z0	Z1	Z0	Z0
W0	W1	W0	W0		W0	W1	W0	W0
1	2	6	8	1	1	2	6	8	1
Z1	Z1	Z1	Z1		Z1	Z1	Z1	Z1
W1	W0	W1	W0		W1	W0	W1	W0
1	9	10	11	1	1	5	6	7	1
Z1	Z0	Z0	Z1		Z1	Z0	Z0	Z1
W1	W0	W1	W0		W1	W0	W1	W0
1	9	10	12	1	1	5	6	7	1
Z1	Z0	Z1	Z1		Z1	Z0	Z1	Z1
W1	W0	W0	W1		W1	W0	W0	W1
1	9	13	14	1	1	5	8	4	1

Первая стратегия МИЛИ:

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

Z0

a2

a3

a4

a1

a1

a8

a1

a1

a13

a12

-

-

-

-

w0

w0

w0

w0

w1

w0

w0

w0

w0

w1

-

-

-

-

Z1

a9

a6

a5

a1

-

a7

a1

a1

a10

a11

a1

a1

a14

a1

w1

w1

w2

w1

-

w1

w1

w1

w0

w1

w0

w0

w0

w1

Таблица №5

Вторая стратегия  МИЛИ:

	a1	a2	a3	a4	a5	a6	a7	a8
Z0	a2	a3	a4	a1	a7	a7	-	-
	w0	w0	w0	w0	w1	w1	-	-
Z1	a5	a3	a4	a1	a6	a7	a1	a4
	w1	w1	w1	w1	w0	w1	w0	w1

Таблица №6

Разметка автомата Мура по первой  стратегии					Разметка автомата Мура по второй стратегии
Z0	Z0	Z0	Z0		Z0	Z0	Z0	Z0
W0	W0	W0	W0		W0	W0	W0	W0
1	2	3	4	5	1	2	3	4	5
Z0	Z0	Z0	Z1		Z0	Z0	Z0	Z1
W0	W0	W0	W1		W0	W0	W0	W1
1	2	3	4	6	1	2	3	4	1
Z0	Z0	Z1	Z0		Z0	Z0	Z1	Z0
W0	W0	W1	W0		W0	W0	W1	W0
1	2	3	7	8	1	2	3	1	2
Z0	Z1	Z0	Z0		Z0	Z1	Z0	Z0
W0	W1	W0	W0		W0	W1	W0	W0
1	2	9	10	11	1	2	6	2	3
Z0	Z1	Z0	Z1		Z0	Z1	Z0	Z1
W0	W1	W0	W1		W0	W1	W0	W1
1	2	9	10	12	1	2	6	2	6
Z0	Z1	Z1	Z0		Z0	Z1	Z1	Z0
W0	W1	W1	W0		W0	W1	W1	W0
1	2	9	13	14	1	2	6	1	2
Z0	Z1	Z1	Z1		Z0	Z1	Z1	Z1
W0	W1	W1	W1		W0	W1	W1	W1
1	2	9	13	15	1	2	6	1	7
Z1	Z1	Z1	Z1		Z1	Z1	Z1	Z1
W1	W0	W1	W0		W1	W0	W1	W0
1	16	17	18	19	1	7	5	7	5
Z1	Z0	Z0	Z1		Z1	Z0	Z0	Z1
W1	W0	W1	W0		W1	W0	W1	W0
1	16	17	20	21	1	7	5	8	2
Z1	Z0	Z1	Z1		Z1	Z0	Z1	Z1
W1	W0	W0	W1		W1	W0	W0	W1
1	9	22	23	24	1	7	8	2	6

Первая стратегия МУРА:

w0

w0

w0

w0

w0

w1

w1

w0

w1

w0

w0

w1

w1

w0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

Z0

a2

a3

a4

a5

-

-

a8

-

a10

a12

-

-

a14

-

Z1

a16

a9

a7

a6

-

-

-

-

a13

-

-

-

a15

-

	w1	w1	w1	w1	w0	w1	w0	w0	w0	w1
	a15	a16	a17	a18	a19	a20	a21	a22	a23	a24
Z0	-	a22	a20	-	-	-	-	a23	-	-
Z1	-	a17	a18	a19	-	a21	-	-	a24	-

Таблица №7

Вторая стратегия  МУРА:

	w1	w0	w0	w0	w0	w1	w1	w0
	a1	a2	a3	a4	a5	a6	a7	a8
Z0	a2	a3	a4	a5	a8	a2	a8	a2
Z1	a7	a6	a1	a1	a7	a1	a5	-

Таблица №8

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

Минимизация автомата

Построение минимального автомата начинается с нахождения максимально совместимых классов.

Множество МС классов формируются на основе пар совместимых состояний

с помощью треугольной таблицы (диаграммы пар).

Из таблицы видно, что все состояния исходного минимизируемого автомата являются несовместимыми. Кроме того, известно, что множество всех МС классов полностью  определенного автомата является минимальным замкнутым покрытием. Таким образом,для минимизации полностью определенного автомата достаточно построить множество всех  МС классов(таблица 9)

	МС классы
1	____________ 1,2,3,4,5,6,7,8
2	_ __________ 1,2,3,4,5,6,7,8
3	_ _ ________ 1,2,3,4,5,6,7,8
4	_ _ _ _______ 1,2,3,4,5,6,7,8
5	_ _ _ _ ______ 1,2,3,4,5,6,7,8
6	_ _ _ _ _ ____ 1,2,3,4,5,6,7,8
7	_ _ _ _ _ _ ___ 1,2,3,4,5,6,7,8
8	_ _ _ _ _ _ _ _ 1,2,3,4,5,6,7,8

Таблица №9

Последняя таблица содержит все МС классы, (они не пересекаются),

следовательно, исходный автомат уже минимальный.

Структурный синтез автомата.

По таблице переходов-выходов (таблица 6) строится кодированная таблица переходов-выходов (таблица10):

Z	X	Q1	Q2	Q3	Y	Q1	Q2	Q3	f(Q1)	f(Q2)	f(Q3)	J1	K1	J2	K2	J3	K3
0	0	0	0	0	0	0	0	1	0	0	a	0	-	0	-	1	-
1	0	0	0	1	0	0	1	0	0	a	b	0	-	1	-	-	1
2	0	0	1	0	0	0	1	1	0	1	a	0	-	-	0	1	-
3	0	0	1	1	0	0	0	0	0	b	b	0	-	-	1	-	1
4	0	1	0	0	0	1	1	0	1	a	0	-	0	1	-	0	-
5	0	1	0	1	1	1	1	0	1	a	b	-	0	1	-	-	1
6	0	1	1	0	-	-	-	-	-	-	-	-	-	-	-	-	-
7	0	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-
8	1	0	0	0	1	1	0	0	a	0	0	1	-	0	-	0	-
9	1	0	0	1	1	0	1	0	0	a	b	0	-	1	-	-	1
10	1	0	1	0	1	0	1	1	0	1	a	0	-	-	0	1	-
11	1	0	1	1	1	0	0	0	0	b	b	0	-	-	1	-	1
12	1	1	0	0	0	1	0	1	1	0	a	-	0	0	-	1	-
13	1	1	0	1	1	1	1	0	1	a	b	-	0	1	-	-	1
14	1	1	1	0	0	0	0	0	b	b	0	-	1	-	1	0	-
15	1	1	1	1	0	0	1	1	b	1	1	-	1	-	0	-	0

Таблица №10

Минимизация функций проводится методом карт Карно:

		Q2	Q3
	J1	00	01	11	10
XQ1	00	0	0	0	0
	01	-	-	-	-
	11	-	-	-	-
	10	1	0	0	0

            __        __ 

ì  Y=XQ1+Q1Q2Q3   

ê         __ __     

ï  J1=Q2Q3X

ç

ç  K1=Q2

ê       __

í  J2=XQ1+Q3

ï                __    __     

ï   K2=Q1Q3+Q1Q3

ï          __       __ __          __

ê   J3=Q1Q2+XQ1+XQ1Q2

ê          __   __

î   K3=Q1+Q2

Таблица №11

Малая степень интеграции

В схеме использованы микросхемы:

DD5, DD6, DD8-K158 ЛР 3

DD4-К155 ЛЛ 1

DD8-К155 ЛИ 1

DD7-K155 ЛН1

DD1, DD2-К 531

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

В соответствие с таблицей №11 получается схема:

Средняя степень интеграции

В схеме использованы микросхемы:

DD4, DD5, DD6, DD7, DD8-К155 ЛЛ 1

DD1-К155 ИД 3

DD2, DD3-К531

В таблице10 в столбце Z показаны выходы дешифратора, на которых уровень логического“0”соответствущем наборе на входе. Согласно таблице 10

ì  Y=Z6+Z9+Z10+Z11+Z12+Z14

ê

ï  J1=Z9

ç

ç  K1=Z15+Z16

ê

í  J2=Z2+Z5+Z6+Z10+Z15

ï

ï   K2=Z4+Z12+Z15

ï

ê   J3=Z1+Z3+Z11+Z13

ê

î   K3=Z2+Z4+Z6+Z10+Z12+Z14

Большая степень интеграции

В схеме использованы микросхемы:

DD1-К155 PE3

DD2, DD3-K531

Запись в ПЗУ производится электронным программированием