Решение комплексной задачи синтеза дискретного устройства с памятью

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

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

Пермский государственный технический университет

Кафедра ИТАС

Курсовая работа

по дисциплине «Теория автоматов»

Решение комплексной задачи синтеза дискретного устройства с памятью

Выполнил:

студент гр. ЭВТ-06

Бакунов Р.Р.

Зачетная книжка № 06-292

Проверил:

профессор Коган Т.И.

Пермь 2007 г.



Введение

дискретный устройство физический синтез

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

В данной курсовой работе будет вручную решена задача абстрактного и структурного синтеза дискретного устройства с памятью - кодового замка, будут рассмотрены элементы физического синтеза. Кроме того, будет произведен анализ полученной функциональной схемы автомата на отсутствие состязаний типа «Риск в 1» по одному из выходов. В настоящее время, в «компьютерную эру», человеку уже необязательно «обременять» себя ручным выполнением решений многих задач. Это тоже найдет свое отражение в данной курсовой работе: наряду с ручным синтезом автомата будет выполнен машинный синтез с использованием пакета «PROEKT», а также будет произведено их сравнение.



1. Задание на проектирование

Спроектировать цифровой автомат (кодовый замок), имеющий три входа (a, b, c) и два выхода (z1, z2).

Выход z1 возбуждается при подаче входной последовательности сигналов 0-4-5-1-0, выход z2- при нарушении заданной последовательности.

В качестве элементной базы использовать интегральные микросхемы базиса И-НЕ. В качестве элементов памяти использовать RS- триггеры с прямым управлением. После получения функциональной схемы автомата провести ее анализ на отсутствие состязаний типа «Риск в 1» в функции выхода z2 или z1. Входные сигналы образуют совокупность соседних чисел.

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

Построение первичной таблицы переходов-выходов.

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

abc	000	100	101	001	000
z1z2	00	00	00	00	10

Первичная таблица переходов-выходов имеет вид:

№	abc	z1	z2
	000	001	011	111	110	100	101	010
1	1	6	-	-	-	2	-	7	0	0
2	8	-	-	-	9	2	3	-	0	0
3	-	4	-	10	-	11	3	-	0	0
4	5	4	12	-	-	-	13	-	0	0
5	5	-	-	-	-	-	-	-	1	0
6	-	6	-	-	-	-	-	-	0	1
7	-	-	-	-	-	-	-	7	0	1
8	8	-	-	-	-	-	-	-	0	1
9	-	-	-	-	9	-	-	-	0	1
10	-	-	-	10	-	-	-	-	0	1
11	-	-	-	-	-	11	-	-	0	1
12	-	-	12	-	-	-	-	-	0	1
13	-	-	-	-	-	-	13	-	0	1

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

Диаграмма объединений

Минимизированная таблица переходов

№	abc
	000	001	011	111	110	100	101	010
a	1	6	12	10	9	2	13	7
b	8	-	-	-	9	2	3	-
c	-	4	-	10	-	11	3	-
d	5	4	12	-	-	-	13	-

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

Определение всех переходов:

a>b₁₀₀

b>a₁₁₀*c₁₀₁

c>d₀₀₁*a₁₁₁

d>a₀₁₁*a₁₀₁



Диаграмма переходов

Получилось, что нужно 3 ЭП. Но пустые строки минимизированной таблицы переходов можно использовать для переходов.

Пусть переход c>a₁₁₁ будет идти через b. Тогда минимизированная таблица переходов примет вид:

№	abc
	000	001	011	111	110	100	101	010
a	1	6	12	10	9	2	13	7
b	8	-	-	10	9	2	3	-
c	-	4	-	10	-	11	3	-
d	5	4	12	-	-	-	13	-

Переходы из строки с примут следующий вид:

c>d₀₀₁*(a a_b)₁₁₁

Получается следующая диаграмма переходов:

Минимально количество элементов карты Карно = 2.



Все переходы удалось сделать соседними, лишних строк вводить не надо, количество ЭП - 2.

Кодирование строк (при базе y1y2):

a>00

b>01

c>11

d>10

Реализуемая таблица переходов

у1у2	abc
	000	001	011	111	110	100	101	010
00	1	6	12	10	9	2	13	7
01	8	-	-	10	9	2	3	-
11	-	4	-	10	-	11	3	-
10	5	4	12	-	-	-	13	-

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

Таблица оцифрована в 8-ной системе счисления

№	abc
	000	001	011	111	110	100	101	010
00	00/0000	00/0101	00/0103	00/0107	00/0106	01/0004	00/0105	00/0102
01	01/0110	- 11	- 13	00/0117	00/0116	01/0014	11/0015	- 12
11	- 30	10/0031	- 33	01/0137	- 36	11/0134	11/0035	- 32
10	10/1020	10/0021	00/0123	- 27	- 26	- 24	00/0125	- 22
y1y2(t+1)/z1z2(t)

Построение таблицы возбуждений.

По заданию в качестве ЭП выбран RS-триггер с прямым управлением.

Таблица входов RS-триггера с прямым управлением

y(t)	y(t+1)
	0	1
0	0~	10
1	01	~0
S(t), R(t)

Таблица возбуждений

№	abc
	000	001	011	111	110	100	101	010
00	0~,0~00	0~,0~01	0~,0~03	0~,0~07	0~,0~06	0~,1004	0~,0~05	0~,0~02
01	0~,~010	- 11	- 13	0~,0117	0~,0116	0~,~014	10,~015	- 12
11	- 30	~0,0131	- 33	01,~037	- 36	~0,~034	~0,~035	- 32
10	~0,0~20	~0,0~21	01,0~23	- 27	- 26	- 24	01,0~25	- 22
S1(t)R1(t), S2(t)R2(t)

Получение условий работы синтезируемого ДУ.

Функции выходов:

z1(y1y2abc) = 20, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 15, 16, 17, 21, 23, 25, 31, 34, 35, 37];

z2(y1y2abc) = 01, 02, 03, 05, 06, 07, 10, 16, 17, 23, 25, 34, 37, [00, 04, 14, 15, 20, 21, 31, 35];

Функции возбуждения ЭП:

S1(y1y2abc) = 15, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 16, 17, 23, 25, 37];

R1(y1y2abc) = 23, 25, 37, [15, 20, 21, 31, 34, 35];

S2(y1y2abc) = 04, [00, 01, 02, 03, 05, 06, 07, 16, 17, 20, 21, 23, 25, 31];

R2(y1y2abc) = 16, 17, 31, [04, 10, 14, 15, 34, 35, 37];

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

Минимизация функций, описывающих условия функционирования ДУ.

z1(y1y2abc) = 20, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 15, 16, 17, 21, 23, 25, 31, 34, 35, 37];



«20» покрыто.

z2(y1y2abc) = 01, 02, 03, 05, 06, 07, 10, 16, 17, 23, 25, 34, 37, [00, 04, 14, 15, 20, 21, 31, 35];

«01», «03», «05», «07» покрыто.

«02», «06», «16», «17», «23», «37» покрыто.

«10» покрыто.

«25» покрыто.



«34» покрыто.

S1(y1y2abc) = 15, [00, 01, 02, 03, 04, 05, 06, 07, 10, 14, 16, 17, 23, 25, 37];

«15» покрыто.

R1(y1y2abc) = 23, 25, 37, [15, 20, 21, 31, 34, 35];

«23», «37» покрыто.

«25» покрыто.



S2(y1y2abc) = 04, [00, 01, 02, 03, 05, 06, 07, 16, 17, 20, 21, 23, 25, 31];

«04» покрыто.

R2(y1y2abc) = 16, 17, 31, [04, 10, 14, 15, 34, 35, 37];

«16», «17» покрыто.

«31» покрыто.

Приведение функций, описывающих условия работы автомата, к виду, удобному для реализации в базисе И-НЕ.



Построение функциональной схемы автомата по отдельным каналам.

Выход z1

Выход z2

Триггер Т1



Триггер Т2

Общая функциональная схема автомата



4. Элементы физического синтеза

Для построения рабочей схемы синтезируемого ДУ нужны следующие микросхемы:

К155ЛА10 - 3 шт. (3х3И-НЕ)

К155ЛА3 - 2 шт. (4х2И-НЕ)

К155ЛА2- 1 шт. (8И-НЕ)

К555ТР2- 1 шт. (Четыре RS-триггера)

Краткая техническая характеристика интегральных микросхем 155-й серии:

Основой микросхем являются транзисторы (транзисторно- транзисторная логика - ТТЛ).

U_пит = +5 В

U¹ >= +2,4 В (высокий уровень)

U⁰ <= + 0,3 В (низкий уровень)

P_потр = 10 мВт

Для 555-й серии параметры аналогичны, за исключением того что P_потр = 2 мВт, т.е. микросхемы этой серии «экономичнее» в 5 раз.

5. Анализ автомата на отсутствие состязаний типа «риск в 1» по выходу z2 или z1



Анализ по выходу z2:

Анализ по выходу z1:

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

Т.к. состязаний в функциях z1 и z2 нет, то по заданию нужно выполнить пример из учебного пособия (часть 1, с. 130, пример 5.5).

Пример 5.5 Функциональная схема ДУ показана на рисунке.

Логическое выражение, описывающее условия его работы, имеет вид:



Очевидно, что в рассматриваемом ДУ могут иметь место состязания типа риск в нуле (форма КНФ) по переменным x₂ и x₃, т.е. при таких изменениях состояний входов, при которых x₂ или x₃ меняются с 0 на 1, на выходе ДУ может кратковременно появиться ошибочный единичный сигнал.

Из КНФ получаем:

Вычисляем функции риска в нуле по x₂ и x₃:

Вычисляем функцию риска в нуле для всего ДУ:

Приведем функцию к символической форме при базе x₁x₂x₃x₄:



Так как риск в нуле проявляется лишь при отсутствии выходного сигнала (сигнал на выходе равен 0), то нас интересуют запрещенные наборы функции , именно на них возможны состязания типа риск в нуле.

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

Полученный результат говорит о том, что на входных наборах 1, 3, 9, 10, 11, 14, 15 (при базе x₁x₂x₃x₄) на выходе ДУ сигнала быть не должно (нулевой сигнал). Однако вследствие наличия состязаний типа риск в нуле по переменной x₂ и x₃ при переходах входных сигналов 10 > 14, 11 > 15, 1 > 3, 9 > 11, когда переменные x₂ и x₃ изменяют свои значения с 0 на 1, возможны появления на выходе кратковременных ложных единичных сигналов.

6. Автоматизированный синтез автомата на ПЭВМ

Распечатка результатов машинного синтеза:

SINTEZ - PROEKT24

PAMJAT = 'RS' c пpямым упpавлением'

STR = 13, STO = 8, XRAZV = 1, XRAZB = 3, ZRAZB = 2

Схема построена на 'И-НЕ' элементах

База входного слова: a,b,c;

База выходного слова: z1,z2;



Пеpвичная таблица пеpеходов-выходов

N.вн. сост.	Вх.слова	вых.
	0	1	3	7	6	4	5	2	1	0
1	1	6	-	-	-	2	-	7	0	0
2	8	-	-	-	9	2	3	-	0	0
3	-	4	-	10	-	11	3	-	0	0
4	5	4	12	-	-	-	13	-	0	0
5	5	-	-	-	-	-	-	-	1	0
6	-	6	-	-	-	-	-	-	0	1
7	-	-	-	-	-	-	-	7	0	1
8	8	-	-	-	-	-	-	-	0	1
9	-	-	-	-	9	-	-	-	0	1
10	-	-	-	10	-	-	-	-	0	1
11	-	-	-	10	-	-	-	-	0	1
12			12	-	-	-	-	-	0	1
13	-	-	-	-	-	-	-	-	0	1

Матpица объединеных стpок

¦Nстp. мин. табл.	N стp. пеpв.табл.
	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	0	0	0	0	1	1	0	1	1	0	1	1
2	0	1	0	0	0	0	0	1	0	0	0	0	0
3	0	0	1	0	1	0	0	0	0	0	1	0	0
4	0	0	0	1	0	0	0	0	0	0	0	0	0

Минимизиpованная таблица пеpеходов

N.вн. сост.	Вх.слова
	0	1	3	7	6	4	5	2
1	1	1	1	1	1	2	1	1
2	2	-	-	-	1	2	3	-
3	3	4	-	1	-	3	3	-
4	3	4	1	-	-	-	1	-

Матpица выходов

N.вн. сост.	Вх.слова
	0	1	3	7	6	4	5	2
1	00	01	01	01	01	00	01	01
2	01	-	-	-	01	00	00	-
3	10	00	-	01	-	01	00	-
4	10	00	01	-	-	-	01	-

Pеализуемая таблица пеpеходов

N.вн. сост.		Вн. сост.
	0	1	3	7	6	4	5	2
1	1	1	1	1	1	2	1	1	00
2	2	-	-	1	1	2	3	-	01
3	3	4	-	2	-	3	3	-	11
4	3	4	1	-	-	-	1	-	10

Конечная матpица выходов

N.вн. сост.	Вх.слова
	0	1	3	7	6	4	5	2
1	00	01	01	01	01	00	01	01
2	01	-	-	01	01	00	00	-
3	10	00	-	01	-	01	00	-
4	10	00	01	-	-	-	01	-

Базис: y1,y2,a,b,c

'RS' c пpямым упpавлением'

Уpавнения возбуждения элементов памяти:

S1 = y2*~b*c;

R1 = b + ~y2*a;

S2 = a*~b*~c + y1*~c;

R2 = ~y1*b + b*~c + ~a*c;

Уpавнения выходов:

z1 = y1*~a*~c;

z2 = ~y1*~a*c + b + ~y2*a*c + ~y1*y2*~a + y1*a*~c;



Теперь выводим на элементах И-НЕ

'RS' c пpямым упpавлением'

Уpавнения возбуждения элементов памяти:

S1 = ~( ~( y2*~b*c ) );

R1 = ~( ~(b) * ~(~y2*a) );

S2 = ~( ~(a*~b*~c) * ~(y1*~c) );

R2 = ~( ~(~y1*b) * ~(b*~c) * ~(~a*c) );

Уpавнения выходов:

z1 = ~( ~( y1*~a*~c ) );

z2 = ~( ~(~y1*~a*c) * ~(b) * ~(~y2*a*c) * ~(~y1*y2*~a) * ~(y1*a*~c) );

Функциональная схема, полученная в результате машинного решения



7. Сравнение ручного и машинного решений

В ручном решении таблица переходов-выходов имеет вид:

№	abc
	000	001	011	111	110	100	101	010
00	00/0000	00/0101	00/0103	00/0107	00/0106	01/0004	00/0105	00/0102
01	01/0110	- 11	- 13	00/0117	00/0116	01/0014	11/0015	- 12
11	- 30	10/0031	- 33	01/0137	- 36	11/0134	11/0035	- 32
10	10/1020	10/0021	00/0123	- 27	- 26	- 24	00/0125	- 22
y1y2(t+1)/z1z2(t)

Функции возбуждения элементов памяти и выходов имеют вид:

В машинном решении эти функции имеют вид:

S1 = y2*~b*c;

R1 = b + ~y2*a;

S2 = a*~b*~c + y1*~c;

R2 = ~y1*b + b*~c + ~a*c;

z1 = y1*~a*~c;

z2 = ~y1*~a*c + b + ~y2*a*c + ~y1*y2*~a + y1*a*~c;



Видно, что есть расхождения в функциях z, S2 и R2.

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

№	abc
	000	001	011	111	110	100	101	010
00	00/0000	00/0101	00/0103	00/0107	00/0106	01/0004	00/0105	00/0102
01	01/0110	- 11	- 13	00/0117	00/0116	01/0014	11/0015	- 12
11	11/10 30	10/0031	- 33	01/0137	- 36	11/0134	11/0035	- 32
10	11/1020	10/0021	00/0123	- 27	- 26	- 24	00/0125	- 22
y1y2(t+1)/z1z2(t)

Между таблицами, полученными вручную и с помощью машины, есть различия. В ручной таблице клетка с ВС = 30 является неиспользуемой. В связи с этим отсутствует переход от клетки с ВС=20 к клетке с ВС=30. Причиной этого является, как следует из матрицы объединенных строк, разное объединение строк:

ручное решение: 1 - 1,6,7,9,10,12,13; 2 - 2,8; 3 - 3,11; 4- 4,5.

машинное решение: 1 - 1,6,7,9,10,12,13; 2 - 2,8; 3 - 3,5,11; 4 - 4.

В данном случае это привело к тому, что в таблице переходов-выходов машинного решения содержится большее количество значащих (заполненных) клеток, а, значит, большее число переходов и, как следствие, большее число букв в функциях S2 и R2. Таким образом, в данном случае машинное решение оказалось более сложным, чем ручное.

Работа машины имеет некоторые особенности. На этапе минимизации первичной таблицы переходов-выходов машина выбирает объединяемые строки путем последовательного сравнения каждой строки со всеми остальными. Группа непротиворечивых строк объединяется в одну строку минимизированной таблицы переходов, и строки, входящие в эту группу, исключаются из дальнейшего рассмотрения. Процедура продолжается, пока не будут исключены все строки из первичной таблицы переходов. Человек же при объединении строк первичной таблицы переходов выбирает варианты объединения строк, исходя из своих знаний и прогнозов на получение минимизированной таблицы с наименьшим количеством значащих клеток (тактов). Здесь кроется одна из причин возможных неоднозначностей конечных результатов. Но, как правило, это не единственная причина.

Вторая причина возможной неоднозначности ответа заключается в выбранном варианте кодирования состояний памяти автомата (строк реализуемой таблицы переходов). Человек, выполняя кодирование вручную по диаграмме переходов и карте Карно, так расставляет строки в соседних клетках, чтобы исключить состязания и при этом ограничиться минимальным количеством добавляемых строк. Машина же просматривает соседние состояния подряд, не ограничивая себя условием минимального количества добавляемых строк.



Заключение

В данной курсовой работе произведен ручной абстрактный и структурный синтез дискретного устройства (кодового замка) по заданным условиям работы, рассмотрены элементы физического синтеза (были подобраны микросхемы, необходимые для осуществления физического синтеза проектируемого ДУ, определено нужное их количество), а также произведен анализ спроектированного автомата на отсутствие состязаний типа «Риск в 1» по одному из выходов. Кроме того, был выполнен машинный синтез рассматриваемого ДУ с помощью пакета «PROEKT», а также проведено сравнение результатов ручного и машинного синтезов (в данном случае машинное решение оказалось более сложным, чем ручное), плюс ко всему прочему было дано объяснение несовпадения этих результатов.

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