ТДУ_курсовая_вар_1
.pdf
|
Содержание |
|
Введение................................................................................................................... |
2 |
|
1. |
Описание автомата по исходным данным........................................................ |
3 |
2. |
Построение графа переходов и первичной таблицы переходов (ТП). .......... |
4 |
3. |
Объединение строк таблицы переходов. .......................................................... |
7 |
|
3.1. Нахождение максимального подмножества совместимых строк (МПСС |
|
|
ТП). ........................................................................................................................ |
7 |
|
3.2. Составление таблицы включений. .............................................................. |
9 |
|
3.3. Решение задачи покрытия. ........................................................................... |
9 |
|
3.4. Нахождение минимального множества таблицы покрытия................... |
11 |
|
3.5. Построение минимизированной таблицы переходов. ............................ |
13 |
|
3.6. Перенумерация строк минимизированной ТП. ....................................... |
13 |
4. |
Блок-схема синхронного автомата. ................................................................. |
14 |
5. |
Кодирование строк таблицы переходов.......................................................... |
15 |
|
5.1. Определение необходимого числа элементов памяти. ........................... |
15 |
|
5.2. Кодированные таблица переходов и таблица выходов........................... |
15 |
6. |
Реализация автомата в базисе {И, ИЛИ, НЕ, Триггер}................................. |
17 |
|
6.1. Таблицы истинности управления триггерами по входам YS и YR и |
|
|
выходных функций z1, z2. .................................................................................. |
17 |
|
6.2. Карты Карно и минимизированные ФАЛ. ............................................... |
19 |
|
6.3. Функциональная схема автомата. ............................................................. |
21 |
7. |
Реализация автомата на микросхемах............................................................. |
23 |
|
7.1. Выбор типа микросхем............................................................................... |
23 |
|
7.2. Реализация функций алгебры логики на микросхемах........................... |
23 |
|
7.3. Принципиальная схема автомата на микросхемах.................................. |
24 |
|
7.4. Спецификация микросхем. ........................................................................ |
25 |
Список использованной литературы................................................................... |
26 |
|
1
Введение.
Цифровые устройства для контроля и управления разнообразным оборудованием используются очень широко. Это могут быть узлы и блоки универсальных или специализированных вычислительных машин,
устройства и системы управления промышленным оборудованием и комплексами оборудования.
Автомат характеризуется конечным числом состояний {a0,a1,a2,…,ah–1},
одно из которых (обычно а0) называется начальным состоянием автомата.
Обычно буквы входного и выходного алфавита, а также состояния автомата отождествляются с цифрами в определенной системе счисления
(двоичной или десятичной). Поэтому дискретные автоматы часто называют
цифровыми. На вход автомата в дискретные моменты времени t=1, 2, 3,...
поступают слова, составленные из букв входного алфавита:{x0, x1, x2,…, xn–1}.
На выходе автомата появляются слова, составленные из букв выходного алфавита: {y1, y2, y3, …, ym–1}. Дискретный автомат осуществляет преобразование входных слов в выходные слова.
При любом способе задания конечной целью проектирования цифрового автомата является получение принципиальной схемы, составленной из элементов заданного базиса.
2
1. Описание автомата по исходным данным.
Вариант 1.
Исходные данные - вход-выходные временные последовательности:
Рисунок 1. Вход-выходные временные последовательности
Схема, которую нужно построить должна иметь два входа x1 и x2 и два выхода z1 и z2. Схема должна реализовать три циклические последовательности сигналов, показанных на Рисунке 2 (а-б-в). Все последовательности имеют одно и то же исходное состояние на интервале времени t1: x1x2 = 00, z1z2 = 00. Последовательности могут сменять друг друга в произвольном порядке.
3
Рисунок 2. Вход-выходные временные последовательности и временные диаграммы к ним
2. Построение графа переходов и первичной таблицы переходов (ТП).
Анализируя временные диаграммы (Рисунок 2), пронумеруем состояния
схемы, используя два правила:
1)вводится начальное устойчивое состояние, соответствующее интервалу времени t1, когда x1x2 = 00, z1z2 = 00 (в таблице 1 это состояние (а1, 1));
2)для каждого последующего такта вводится новое устойчивое состояние
(Рисунок 3).
4
Рисунок 3. Нумерация состояний
|
|
|
|
|
Таблица 1 |
|
|
Таблица переходов |
|
||
|
|
|
|
|
|
a |
|
a1 |
a2 |
a3 |
a4 |
|
|
|
|
|
|
|
x1x2 |
00 |
01 |
10 |
11 |
S |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
(1), 00 |
2, 01 |
6, 10 |
10, 00 |
|
|
|
|
|
|
2 |
|
~ |
(2), 01 |
3, 11 |
~ |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
~ |
~ |
(3), 11 |
4, 00 |
|
|
|
|
|
|
4 |
|
~ |
5, 10 |
~ |
(4), 00 |
|
|
|
|
|
|
5 |
|
1, 00 |
(5), 10 |
~ |
~ |
|
|
|
|
|
|
6 |
|
~ |
~ |
(6), 10 |
7, 01 |
|
|
|
|
|
|
7 |
|
~ |
~ |
8, 00 |
(7), 01 |
|
|
|
|
|
|
8 |
|
~ |
9, 01 |
(8), 00 |
~ |
|
|
|
|
|
|
9 |
|
1, 00 |
(9), 01 |
~ |
~ |
|
|
|
|
|
|
10 |
|
~ |
~ |
11, 11 |
(10), 00 |
|
|
|
|
|
|
11 |
|
~ |
~ |
(11), 11 |
12, 11 |
|
|
|
|
|
|
12 |
|
~ |
~ |
13, 01 |
(12), 11 |
|
|
|
|
|
|
13 |
|
1, 00 |
~ |
(13), 01 |
~ |
|
|
|
|
|
|
5
Первый цикл работы: из состояния 1 (а1, 1) со значением входов x1x2 = 00 и
выходов z1z2 = 00 схема под воздействием входного сиг нала 01 переходит в состояние 2 (а2, 2) со значением выходов z1z2 = 01. Затем под воздействием входного сигнала 10 схема переходит в состояние 3 (а1, 3) со значением выходов z1z2 = 11. В состояние 4 (а2, 4) и выходами z1z2 = 00 схема переходит под воздействием входного сигнала 11, а под воздействием сигнала 01, схема переходит в состояние 5 (а4, 5) со значением выходов z1z2 = 10. Завершается циклическая вход-выходная первая последовательность подачей входного сигнала 00 и переходом схемы в начальное состояние 1 (а1, 1). Затем таблица переходов расширяется с учетом второй и третьей вход-выходных последовательностей. При этом их начальные состояния совпадают с начальным состоянием первой последовательности.
Построим граф переходов (Рисунок 4). Вершина графа – круг (над чертой -
номер состояния, под чертой – значение выхода). Дуги – всевозможные переходы из данного состояния в другое, включая устойчивые состояния.
Рисунок 4. Граф переходов
6
Построение графа для первой вход-временной последовательности:
из состояния 1, 00 под входным воздействием 01 схема переходит в состояние 2, 01, далее под воздействием 10 схема переходит в состояние 3,
11, затем под входным воздействием 11 – в состояние 4, 00, под воздействием 01 – в состояние 5, 10, наконец, под воздействием 00 – в
исходное состояние 1, 00. Устойчивые состояния на графе показываются дугами, исходящими и входящими в одну и ту же вершину графа с подписью значений входов схемы. Аналогично строим граф для оставшихся циклов работы схемы.
3. Объединение строк таблицы переходов.
3.1. Нахождение максимального подмножества совместимых строк
(МПСС ТП).
Найдем множества Eij – множества строк, в которых в столбце j проставлено состояние i или знак безразличного состояния (~).
E11 |
= {1,2,3,4,5,6,7,8,9,10,11,12,13} |
E22 |
= {1, 2, 3, 6, 7, 10, 11, 12, 13} |
|
|
|
E 52 |
= {3, 4, 5, 6, 7, 10, 11, 12, 13} |
|
|
|
E 92 |
= {3, 6, 7, 8, 9, 10, 11, 12, 13} |
|
E33 |
= {2, 3, 4, 5, 9} |
E |
4 |
= {2, 3, 4, 5, 8, 9, 13} |
|
|
4 |
||
E36 |
= {1, 4, 5, 6, 9} |
E |
4 |
= {2, 5, 6, 7, 8, 9, 13} |
|
|
7 |
||
E83 |
= {4, 5, 7, 8, 9} |
|
4 |
= {1, 2, 5, 8, 9, 10, 13} |
E11 |
= {4, 5, 9, 10, 11} |
E10 |
||
|
|
|
||
3 |
|
E12 |
= {2, 5, 8, 9, 11, 12, 13} |
|
|
|
|||
|
|
|
4 |
|
E133 |
= {4, 5, 9, 12, 13} |
|
|
|
7
Найдем множества E |
i1,i2,i3,i4 |
= E1 ∩ |
E 2 ∩ |
E3 ∩ |
E |
4 |
для всех четверок i |
,i |
,i |
,i . |
|
i1 |
i 2 |
i3 |
i 4 |
1 |
2 |
3 |
4 |
||
E1,2,3,4 = {2,3} |
|
E1,5,3,4 = {3,4,5} |
|
|
E1,9,3,4 = {3,9} |
|
|
|||
E1,2,3,7 = {2} |
|
E1,5,3,7 = {5} |
|
|
|
E1,9,3,7 = {9} |
|
|
|
|
E1,2,3,10 = {2} |
|
E1,5,3,10 = {5} |
|
|
E1,9,3,10 = {9} |
|
|
|
||
E1,2,3,12 = {2} |
|
E1,5,3,12 = {5} |
|
|
E1,9,3,12 = {9} |
|
|
|
||
E1,2,6,4 = {Ø} |
|
E1,5,6,4 = {4,5} |
|
|
E1,9,6,4 = {9} |
|
|
|
||
E1,2,6,7 = {6} |
|
E1,5,6,7 = {5,6} |
|
|
E1,9,6,7 = {6,9} |
|
|
|||
E1,2,6,10 = {1} |
|
E1,5,6,10 = {5} |
|
|
E1,9,6,10 = {9} |
|
|
|
||
E1,2,6,12 = {Ø} |
|
E1,5,6,12 = {5} |
|
|
E1,9,6,12 = {9} |
|
|
|
||
E1,2,8,4 = {Ø} |
|
E1,5,8,4 = {4,5} |
|
|
E1,9,8,4 = {8,9} |
|
|
|||
E1,2,8,7 = {7} |
|
E1,5,8,7 = {5,7} |
|
|
E1,9,8,7 = {7,8,9} |
|
||||
E1,2,8,10 = {Ø} |
|
E1,5,8,10 = {5} |
|
|
E1,9,8,10 = {8,9} |
|
|
|||
E1,2,8,12 = {Ø} |
|
E1,5,8,12 = {5} |
|
|
E1,9,8,12 = {8,9} |
|
|
|||
E1,2,11,4 = {Ø} |
|
E1,5,11,4 = {4,5} |
|
|
E1,9,11,4 = {9} |
|
|
|
||
E1,2,11,7 = {Ø} |
|
E1,5,11,7 = {5} |
|
|
E1,9,11,7 = {9} |
|
|
|
||
E1,2,11,10 = {10} |
|
E1,5,11,10 = {5,10} |
|
|
E1,9,11,10 = {9,10} |
|
||||
E1,2,11,12 = {11} |
|
E1,5,11,12 = {5,11} |
|
|
E1,9,11,12 = {9,11} |
|
||||
E1,2,13,4 = {13} |
|
E1,5,13,4 = {4,5,13} |
|
|
E1,9,13,4 = {9,13} |
|
||||
E1,2,13,7 = {13} |
|
E1,5,13,7 = {5,13} |
|
|
E1,9,13,7 = {9,13} |
|
||||
E1,2,13,10 = {13} |
|
E1,5,13,10 = {5,13} |
|
|
E1,9,13,10 = {9,13} |
|
||||
E1,2,13,12 = {12,13} |
|
E1,5,13,12 = {5,12,13} |
|
E1,9,13,12 = {9,12,13} |
||||||
8
Из полученных множеств исключим те, которые полностью входят в другое множество. Оставшиеся множества Ei1,i2,i3,i4 являются максимальными подмножествами совместимых строк. Обозначим их латинскими буквами:
E1,2,6,10 = {1} = A; |
E1,2,6,7 |
= {6} = K; |
|||
E1,2,3,4 = {2,3} = B; |
E1,9,6,7 |
= {6,9} = L; |
|||
E1,5,3,4 |
= {3,4,5} = C; |
E1,2,8,7 |
= {7} = M; |
||
E1,9,3,4 |
= {3,9} = D; |
E1,9,8,7 |
= {7,8,9} = N; |
||
E1,5,13,4 = {4,5,13} = E; |
E1,9,11,10 = {9,10} = O; |
||||
E1,5,6,7 |
= {5,6} = F; |
E1,9,11,12 = {9,11} = P; |
|||
E1,5,8,7 |
= {5,7} = G; |
E1,9,13,12 |
= {9,12,13} = Q; |
||
E1,5,11,10 |
= {5,10} = H; |
E1,2,11,10 |
= {10} = R; |
||
E1,5,11,12 |
= {5,11} = I; |
E1,2,11,12 |
= {11} = S; |
||
E1,5,13,12 |
= {5,12,13} = J; |
E1,2,13,12 |
= {12,13} = T. |
||
3.2. Составление таблицы включений.
Столбцы таблицы соответствуют множествам A, B, …, T, а строки – строкам первичной таблицы переходов. На пересечении строки и столбца ставится знак «+», если данная строка таблицы переходов входит в данное подмножество совместимых строк.
3.3. Решение задачи покрытия.
Найдем минимальное множество столбцов W такое, что каждая строка
(состояние) входит хотя бы в одно из них. Для этого составим алгебраическое выражение Q типа конъюнкция дизъюнкций. Каждая дизъюнкция образуется как дизъюнкция тех столбцов, в которых стоит метка
«+» в данной строке (табл. 2).
9
Таблица 2
Таблица покрытий
S |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
+ |
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
+ |
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
+ |
|
+ |
+ |
+ |
+ |
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
+ |
|
|
|
|
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
+ |
|
|
|
|
|
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
+ |
|
|
|
|
|
|
|
+ |
|
+ |
+ |
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
+ |
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
+ |
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
+ |
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
+ |
|
|
|
|
+ |
|
|
|
|
|
|
+ |
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Получили: Q = AB(B\/C\/D)(C\/E)(C\/E\/F\/G\/H\/I\/J)(F\/K\/L)(G\/M\/N)N/\
/\(D\/L\/N\/O\/P\/Q)(H\/O\/R)(I\/P\/S)(J\/Q\/T)(E\/J\/Q\/T).
10