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

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

2

Реферат

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

Введение

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

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

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

Синтез абстрактного автомата

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

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

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

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

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

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

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

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

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

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

Абсолютно несовместимые - состояния имеющие разные выходные сигналы.

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

Условно совместимые - состояния, совместимые при условии равенства функций выхода и эквивалентности функций перехода.

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

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

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

1 этап:

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

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

2 этап:

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

3 этап:

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

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

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

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

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

После выполнения этих действий мы получаем совместимые пары состояний - 9-10, 5-10, 5-8, 4-10, 4-8, 4-5, 2-8,2-5, 2-4, 1-2.

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

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

Ф1=(9,10)

Ф2=(5,10),(5,8)

Ф=(9,10), (5,10), (5,8)

Ф3=(4,10),(4,8),(4,5)

Ф=(9,10), (4,10), (5,10), (4,5,8)

Ф4=(2,8),(2,5),(2,4)

Ф=(9,10), (5,10), (4,10), (2,4,5,8)

Ф= (1,2), (9,10), (5,10), (4,10), (2,4,5,8), (3), (7), (6)

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

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

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

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

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

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

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

д	b1	b2	b3	b4	b5	b6	b7	b8
x1	b4	b4	b4	b4	b4	b2	b3	b2
x2	b6	b5	b6	b6	b6	b7	b6	b4
x3	b7	b7	b7	b7	b7	b4	b5	b5
x4	b2	b5	b5	b5	b5	-	b2	b7
x5	b5	b8	b8	b8	b8	b3	-	b1

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

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

д	b1	b2	b3	b4	b5	b6	b7	b8
x1	y1	y1	y1	y1	y1	y2	-	-
x2	y2	y2	y2	y2	y2	y2	y2	-
x3	-	y2	y2	y2	y2	y1	y2	y1
x4	y1	y2	y1	y1	y1	y1	y1	y1
x5	y1	y2	y2	y2	y1	-	y1	y1

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

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

-разбиением множества S является множество его подмножеств которые не пересекаются между собой и при объединении дают множество S. Эти подмножества называются блоками -разбиения.

Разбиение называется СП-разбиением, при условии, что если состояния находятся в одном блоке, то при одинаковом входном взаимодействии состояния, в которые перейдет автомат, будут также находиться в одном блоке.

Определение СП разбиений

Определение СП-разбиений основано на предположении, что рассматриваемые состояния находятся в одном блоке. Если в разных блоках совпадает хотя бы 1 состояние, то эти блоки объединяются.

Ищем СП-разбиения, попарно рассматривая все состояния:

объединяем блоки, имеющие хотя бы одно одинаковое состояние и

получаем один блок {12345678}. Это значит, что в данном случае

=>СП-разбиения нет. В таком случае ставил «Х»

Аналогично рассматриваем все пары состояний

Декомпозиция автоматов при отсутствии СП-разбиений

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

Определим ортогональные р-разбиения из множества состояний минимизированного автомата.

р1={1234; 5678}, р2={1357;2468}, р3={1256; 3478}.

Каждое р-разбиение соответствует новому автомату, т.е обозначим блоки р-разбиений через состояния автоматов:

р1->В{b1=1234; b2=5678}

р2->C{c1=1357; c2=2468}

р3->D{d1=1256; d2=3478}.

Для каждого разбиения построим функцию перехода компонентных автоматов на основе функции перехода исходного автомата. Функции переходов компонентных автоматов определяют реакцию автоматов B, C, D на внешнее входное воздействие и что исходный автомат находится в состояние К, соответствующему произведению алфавитов компонентных автоматов.

b₁*c₁*d₁=1 b₂*c₁*d₁=5

b₁*c₁*d₂=3 b₂*c₁*d₂=7

b₁*c₂*d₁=2 b₂*c₂*d₁= 6

b₁*c₂*d₂=4 b₂*c₂*d₂=8

Автомат B

д	1	2	3	4	5	6	7	8
x1	b1	b1	b1	b1	b1	b1	b1	b1
x2	b2	b2	b2	b2	b2	b2	b2	b1
x3	b2	b2	b2	b2	b2	b1	b2	b2
x4	b1	b2	b2	b2	b2	-	b1	b2
x5	b2	b2	b2	b2	b2	b2	-	b1

Автомат C

д	1	2	3	4	5	6	7	8
x1	c2	c2	c2	c2	c2	c2	c1	c2
x2	c2	c1	c2	c2	c2	c1	c2	c2
x3	c1	c1	c1	c1	c1	c2	c1	c1
x4	c2	c1	c1	c1	c1	-	c2	c1
x5	c1	c2	c2	c2	c2	c1	-	c1

Автомат D

д	1	2	3	4	5	6	7	8
x1	d2	d2	d2	d2	d2	d2	d2	d1
x2	d1	d1	d1	d1	d1	d2	d1	d2
x3	d2	d2	d1	d1	d1	d2	d1	d2
x4	d1	d1	d1	d1	d1	-	d1	d2
x5	d1	d2	d2	d2	d2	d2	-	d1

Для того, чтобы определить взаимное влияние автоматов друг на друга, определяют ф и ?-разбиение для каждого автомата в отдельности.

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

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

Определим ф-разбиения для компонентных автоматов, путем сравнения столбцов таблиц переходов:

фb= {17};{2345};{6},{8}

ф_c ={1};{2};{345}; {6}; {7}; {8}.

ф_d= {1};{2345};{6};{7};{8}.

Определим з-разбиения для компонентных автоматов, путем сравнения строк таблиц их переходов:

?b = {1};{2};{3},{4},{5}

?c = {1};{2};{3};{4}: {5}.

?d = {1};{24};{3};{5}

Определение входных сигналов компонентных автоматов и составление таблиц

Влияние автоматов друг на друга определяется по следующему правилу: если произведение р-разбиений i-го автомата меньше или равно ф-разбиению i-го автомата, то составляющая определяется как произведение р-разбиений исключая р-разбиение i-го автомата.

р₁*р₂={13,24,57,68}

р₁*р₃={12,34,56,78}

р₂*р₃={15,37,26,48}

р₁*р₂*р₃={1,2,3,4,5,6,7,8}

При сравнении произведений р-разбиений и ф-разбиений автоматов видно, что автоматы непосредственно не влияют на входные сигналы друг друга. Однако, при рассмотрении ортогональных р-разбиений видно, что на входной сигнал автомата С влияют D и B совместно, на входной сигнал автомата D - С и B совместно, а на входной сигнал автомата B - C и D совместно. Следовательно, составляющая входного сигнала .

Для составления таблиц переходов автоматов C,D и B примем следующие обозначения:

В{b1=1234; b2=5678}

C{c1=1357; c2=2468}

D{d1=1256; d2=3478}

U={u₁=x₁, u₂₌x₂; u₃=x₃; u₄=x₄; u₅=x₅}

V={v₁=x₁; v₂=x₂, v₃₌x₃; v₄=x₄; v₅=x₅}

W={w₁=x₁; w₂=x₂,x₄; w₃=x₃; w₄=x₅}.

Таблицы заполняем по следующему алгоритму на примере первой ячейки:

c1*d1*b1=1.

По сигналу u1(x1,x2) автомат B перейдет в состояния b₁, что мы и запишем в первую ячейку таблицы переходов автомата B.

Таким образом, заполняются все ячейки всех трёх автоматов:

д	b1	b2		д	c1	c2		д	d1	d2
c1*d1, u1	b1	b1		b1*d1, v1	c2	c2		b1*c1, w1	d2	d2
c1*d2, u1	b1	b1		b1*d2, v1	c2	c2		b1*c2, w1	d2	d2
c2*d1, u1	b1	b1		b2*d1, v1	c2	c2		b2*c1, w1	d2	d2
c2*d2, u1	b1	b1		b2*d2, v1	c1	c2		b2*c2, w1	d1	d1
c1*d1, u2	b2	b2		b1*d1, v2	c2	c1		b1*c1, w2	d1	d1
c1*d2, u2	b2	b2		b1*d2, v2	c2	c2		b1*c2, w2	d1	d1
c2*d1, u2	b2	b2		b2*d1, v2	c2	c1		b2*c1, w2	d1	d1
c2*d2, u2	b2	b2		b2*d2, v2	c2	c2		b2*c2, w2	-	d2
c1*d1, u3	b2	b2		b1*d1, v3	c1	c1		b1*c1, w3	d2	d2
c1*d2, u3	b2	b2		b1*d2, v3	c1	c1		b1*c2, w3	d2	d2
c2*d1, u3	b2	b1		b2*d1, v3	c1	c2		b2*c1, w3	d2	d1
c2*d2, u3	b2	b2		b2*d2, v3	c1	c1		b2*c2, w3	d2	d1
c1*d1, u4	b1	b2		b1*d1, v4	c2	c1		b1*c1, w4	d1	d1
c1*d2, u4	b2	-		b1*d2, v4	c1	c1		b1*c2, w4	d2	d2
c2*d1, u4	b2	b1		b2*d1, v4	c1	-		b2*c1, w4	d2	-
c2*d2, u4	b2	b1		b2*d2, v4	c2	c1		b2*c2, w4	d2	d1
c1*d1, u5	b2 b2	b1*d1, v5	c1	c2
c1*d2, u5	b2 b1	b1*d2, v5	c2	c2
c2*d1, u5	b2 -	b2*d1, v5	c2	c1
c2*d2, u5	b2 b1	b2*d2, v5	-	c1

Определение выходных сигналов осуществляется по произведению состояний компонентных автоматов B, C и D и входным сигналам в соответствии с таблицей выходов автомата B.

g	b1*c1*d1	b1*c1*d2	b1*c2*d1	b1*c2*d2	b2*c1*d1	b2*c2*d1	b2*c1*d2	b2*c2*d2
	1	2	3	4	5	6	7	8
x1	y1	y1	y1	y1	y1	y2	-	-
x2	y2	y2	y2	y2	y2	y2	y2	-
x3	-	y2	y2	y2	y2	y1	y2	y1
x4	y1	y1	y2	y1	y1	y1	y1	y1
x5	y1	y2	y2	y2	y1	-	y1	y1

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

Кодирование автомата.

На основании таблиц переходов и логической функции строится структурная схема сети автоматов. Структурный автомат представляет собой композицию комбинационной (логической) схемы и элементов памяти, связанных со схемой. Входными переменными схемы являются входные переменные автомата - сигналы приходящие на блоки Ub, Vc, Wd. Выходы схемы Fb, Fc, Fd определяют переход автомата в следующее состояние.

Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. Для этого необходимо, чтобы выполнялось условие N2n, где N - число символов входного алфавита.

Кодировать таблицы переходов и выходов будем в соответствии с условиями:

c₁d₁= b₁c₁= b₁d₁= 11 u₁₌w₁=000v₁=000

c₁d₂= b₁c₂= b₁d₂= 10u₂₌w₂= 001v₂= 001

c₂d₁= b₂c₁= b₂d₁= 01u₃₌w₃=010v₃= 010

c₂d₂= b₂c₂= b₂d₂= 00u₄₌w₄=011v₄= 011

u₅₌w₅ =100

дb	1	0		дc	1	0		дd	1	0
00011	1	1		00011	0	0		00011	0	0
00001	1	1		00001	0	0		00001	0	0
00010	1	1		00010	0	0		00010	0	0
00000	1	1		00000	1	0		00000	1	1
00111	0	0		00111	0	1		00111	1	1
00101	0	0		00101	0	1		00101	1	1
00110	0	0		00110	0	0		00110	1	1
00100	0	0		00100	0	0		00100	-	0
01011	0	0		01011	1	1		01011	0	0
01001	0	0		01001	1	1		01001	0	1
01010	0	1		01010	1	0		01010	0	0
01000	0	0		01000	1	1		01000	0	1
01111	1	0		01111	0	1		01111	1	1
01101	0	0		01101	1	-		01101	0	-
01110	0	-		01110	1	1		01110	0	0
01100	0	0		01100	0	1		01100	0	1
10011 0 0	10011	1	0
10001 0 -	10001	0	0
10010 0 1	10010	0	1
10000 0 1	10000	-	1

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

x₁= 000 b₁= c₁= d₁ =1t1=b1 y₁= 1y₂=0

x₂= 001b₂= c₂= d₂ =0 t2=c1

x₃= 010 t3=d 1

x₄= 011

x₅= 100

g	111	110	101	100	011	001	010	000
	1	2	3	4	5	6	7	8
000	1	1	1	1	1	0	-	-
001	0	0	0	0	0	0	0	-
010	-	0	0	0	0	1	0	1
011	1	1	0	1	1	1	1	1
100	1	0	0	0	1	-	1	1

g=?a1?a2?a3t1t2t3+ ?a1?a2?a3t1t2?t3+ ?a1?a2?a3t1t?2t3+ ?a1?a2?a3t1?t2?t3+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2t3+ ?a1a2?a3?t1?t2?t3+ ?a1a2a3t1t2t3+ ?a1a2a3t1t2?t3+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1t2t3+ ?a1a2a3?t1?t2t3+ ?a1a2a3?t1t2?t3+ ?a1a2a3?t1?t2?t3+ a1?a2?a3t1t2t3+ a1?a2?a3?t1t2t3+ a1?a2?a3?t1t2?t3+ a1?a2?a3?t1?t2?t3

Определение функций логики

Определение функции выхода

Данная функция определяется из таблицы выходов.

Функция выхода определяется из кодированной таблицы выходов по следующей методике: если обозначить кодирующие переменные входа как а1, а2 и а3, состояний - как t1 , t2, t3, выхода - как g, то функция выхода будет иметь вид:

g=?a1?a2?a3t1t2t3+ ?a1?a2?a3t1t2?t3+ ?a1?a2?a3t1t?2t3+ ?a1?a2?a3t1?t2?t3+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2t3+ ?a1a2?a3?t1?t2?t3+ ?a1a2a3t1t2t3+ ?a1a2a3t1t2?t3+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1t2t3+ ?a1a2a3?t1?t2t3+ ?a1a2a3?t1t2?t3+ ?a1a2a3?t1?t2?t3+ a1?a2?a3t1t2t3+ a1?a2?a3?t1t2t3+ a1?a2?a3?t1t2?t3+ a1?a2?a3?t1?t2?t3

Определение функции возбуждения триггеров.

Опять обозначим кодирующие переменные входа как a1, a2 и a3, состояний - как t, заменив в матрице выходов состояния на их коды, получим описание функций u(t1), u(t2), u(t3)

U(t1)=?a1?a2?a3t2t3+ ?a1?a2?a3t2?t3+ ?a1?a2?a3?t2t3+?a1?a2?a3?t2?t3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3? t3t2+ a1?a2?a3? t2?t3

U(t2) =?a1?a2?a3?t1?t3+ ?a1?a2a3t1t3+ ?a1?a2a3?t1t3+ ?a1a2?a3t1t3+ ?a1a2?a3t1?t3+ ?a1a2?a3?t1t3+ ?a1a2?a3?t1?t3+ ?a1a2a3t1t3+ ?a1a2at1?t3+?a1a2a3?t1t3+ ?a1a2a3?t1?t3+ a1?a2?a3t1t3+ a1?a2?a3?t1t3+ a1?a2?a3?t1?t3

U(t3)=?a1?a2?a3?t1?t2+ ?a1?a2a3t1t2+ ?a1?a2a3t1?t2+ ?a1?a2a3?t1t2+ ?a1a2?a3?t1t2+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3?t1?t2

Упрощение логических функций.

Для упрощения функций u(t1) используем карты Карно:

U(t1)=?a1?a2?a3t2t3+ ?a1?a2?a3t2?t3+ ?a1?a2?a3?t2t3+?a1?a2?a3?t2?t3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3? t3t2+ a1?a2?a3? t2?t3

	a2
	1	0	0	0	0	0	0	1
	0	0	0	0	0	0	0	0	t3
	1	0	0	1	0	0	0	1
	1	0	1	0	0	0	0	1
	t2	a3

Получим упрощённую функцию u(t1):

U(t1)=?a1?a2?a3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3?t3

Для упрощения функций u(t2), u(t3) и g воспользуемся склеиванием и поглощением, а так же импликантной таблицей.

U(t2) =?a1?a2?a3?t1?t3+ ?a1?a2a3t1t3+ ?a1?a2a3?t1t3+ ?a1a2?a3t1t3+ ?a1a2?a3t1?t3+ ?a1a2?a3?t1t3+ ?a1a2?a3?t1?t3+ ?a1a2a3t1t3+ ?a1a2at1?t3+?a1a2a3?t1t3+ ?a1a2a3?t1?t3+ a1?a2?a3t1t3+ a1?a2?a3?t1t3+ a1?a2?a3?t1?t3

?a1?a2?a3?t1?t3

?a1?a2a3t1t3

?a1?a2a3?t1t3

?a1a2?a3t1t3

?a1a2?a3t1?t3

?a1a2?a3?t1t3

?a1a2?a3?t1?t3

?a1a2a3t1t3

?a1a2at1?t3

?a1a2a3?t1t3

?a1a2a3?t1?t3

a1?a2?a3t1t3

a1?a2?a3?t1t3

a1?a2?a3?t1?t3

?a1?a2?a3?t1?t3

X

?a1?a2a3t3

X

X

?a1a2

X

X

X

X

X

X

X

X

a1?a2?a3t3

X

X

a1?a2?a3?t1?t3

X

Как видно по импликантной таблице,

U(t2)=?a1?a2?a3?t1?t3+?a1?a2a3t3+?a1a2+a1?a2?a3t3+a1?a2?a3?t1?t3

Упрощение функции U(t3):

U(t3)=?a1?a2?a3?t1?t2+ ?a1?a2a3t1t2+ ?a1?a2a3t1?t2+ ?a1?a2a3?t1t2+ ?a1a2?a3?t1t2+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3?t1?t2=a1?a2?a3?t1?t2+?a1?a2a3t1+?a1?a2a3?t1t2+?a1a2?a3?t1+?a1a2a3t1t2+?a1a2a3?t1?t2

	?a1?a2?a3?t1?t2	?a1?a2a3t1t2	a?1?a2a3t1?t2	?a1?a2a3?t1t2	?a1a2?a3?t1t2	?a1a2?a3?t1?t2	?a1a2a3t1t2	?a1a2a3?t1?t2
?a1?a2?a3?t1?t2	X
?a1?a2a3t1		X	X
?a1?a2a3?t1t2				X
?a1a2?a3?t1					X	X
?a1a2a3t1t2							X
?a1a2a3?t1?t2								X

Минимальная днф U(t3):

U(t3) =?a1?a2?a3?t1?t2+?a1?a2a3t1+?a1?a2a3?t1t2+?a1a2?a3?t1+?a1a2a3t1t2+?a1a2a3?t1?t2

Теперь определяем минимальную днф функции выхода g :

g=?a1?a2?a3t1t2t3+ ?a1?a2?a3t1t2?t3+ ?a1?a2?a3t1t?2t3+ ?a1?a2?a3t1?t2?t3+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2t3+ ?a1a2?a3?t1?t2?t3+ ?a1a2a3t1t2t3+ ?a1a2a3t1t2?t3+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1t2t3+ ?a1a2a3?t1?t2t3+ ?a1a2a3?t1t2?t3+ ?a1a2a3?t1?t2?t3+ a1?a2?a3t1t2t3+ a1?a2?a3?t1t2t3+ a1?a2?a3?t1t2?t3+ a1?a2?a3?t1?t2?t3 =

= ?a1?a2?a3t1+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1+ a1?a2?a3t2t3+ a1?a2?a3?t1?t3

Табл

?a1?a2?a3t1t2t3

?a1?a2?a3t1t2?t3

?a1?a2?a3t1t?2t3

?a1?a2?a3t1?t2?t3

?a1?a2?a3?t1t2t3

?a1a2?a3?t1?t2t3

?a1a2?a3?t1?t2?t3

?a1a2?a3?t1?t2?t3

?a1a2a3t1t2t3

?a1a2a3t1?t2?t3

?a1a2a3?t1t2t3

?a1a2a3?t1?t2t3

?a1a2a3?t1t2?t3

?a1a2a3?t1?t2?t3

a1?a2?a3t1t2t3

a1?a2?a3?t1t2t3

a1?a2?a3?t1t2?t3

a1?a2?a3?t1?t2?t3

?a1?a2?a3?t?1?t3

X

X

X

X

?a1?a2a3t3

X

?a1a2

X

X

a1?a2?a3t3

X

X

a1?a2?a3?t?1?t3

X

?a1a2a3??t?1

X

X

X

X

a1?a2?a3t2t3

X

X

a1?a2?a3?t?1?t3

X

X

Минимальная днф g:

g= ?a1?a2?a3t1+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1+ a1?a2?a3t2t3+ a1?a2?a3?t1?t3

Логические функции

U(t1)=?a1?a2?a3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3?t3

U(t2)=?a1?a2?a3?t1?t3+?a1?a2a3t3+?a1a2+a1?a2?a3t3+a1?a2?a3?t1?t3

U(t3) =?a1?a2?a3?t1?t2+?a1?a2a3t1+?a1?a2a3?t1t2+?a1a2?a3?t1+?a1a2a3t1t2+?a1a2a3?t1?t2

g= ?a1?a2?a3t1+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1+ a1?a2?a3t2t3+ a1?a2?a3?t1?t3

Разработка комбинационных логических схем

Мы получили 4 логические функции, которые необходимо реализовать на практике:

U(t1)=?a1?a2?a3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3?t3

U(t2)=?a1?a2?a3?t1?t3+?a1?a2a3t3+?a1a2+a1?a2?a3t3+a1?a2?a3?t1?t3

U(t3) =?a1?a2?a3?t1?t2+?a1?a2a3t1+?a1?a2a3?t1t2+?a1a2?a3?t1+?a1a2a3t1t2+?a1a2a3?t1?t2

g= ?a1?a2?a3t1+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1+ a1?a

Логическая схема компонентного автомата B .

U(t1)=?a1?a2?a3+?a1a2?a3t2?t3+?a1a2a3t2t3+a1?a2?a3?t3

Для этой схемы мы используем 3 схемы 3-ИЛИ, 9 схем 3-И, и 5 схем НЕ.

2?a3t2t3+ a1?a2?a3?t1?t3

Логическая схема компонентного автомата С.

U(t2)=?a1?a2?a3?t1?t3+?a1?a2a3t3+?a1a2+a1?a2?a3t3+a1?a2?a3?t1?t3

Для этой схемы мы используем 11 схем 3- И, 5 схем НЕ и 3 схемы 3-ИЛИ

Логическая схема компонентного автомата D.

U(t3) =?a1?a2?a3?t1?t2+?a1?a2a3t1+?a1?a2a3?t1t2+?a1a2?a3?t1+?a1a2a3t1t2+?a1a2a3?t1?t2

Здесь мы используем 5 схем НЕ, 16 схем 3- И, 3 схемы 3-ИЛИ.

Логическая схема выхода.

g= ?a1?a2?a3t1+ ?a1?a2?a3?t1t2t3+ ?a1a2?a3?t1?t2+ ?a1a2a3t1t2+ ?a1a2a3t1?t2?t3+ ?a1a2a3?t1+ a1?a2?a3t2t3+ a1?a2?a3?t1?t3

Здесь мы используем 6 схем НЕ, 19 схем 3-И, 4 схем 2-ИЛИ.

Заключение

логический схема цифровой автомат

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

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

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

Рекомендуемая литература

1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002 - 528 с.(21. pdf )

2. .Карпов Ю.Г. Теория автоматов: Учебник для вузов.СПб.: Питер, 2003 - 208 с.

3. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989 - 327 с.

4. Савельев А.Я. Прикладная теория цифровых автоматов: Учебник для вузов. М.: Высшая школа, 1987 - 272 с.

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