ТДУ_курсовая_вар_1
.pdf3.4. Нахождение минимального множества таблицы покрытия.
Используя свойства:
1.коммутативности xy = yx и x\/y = y\/x,
2.поглощения x(x\/y) = x,
3.дистрибутивности (x\/y)(x\/z) = x\/yz и x(y\/z) = xy\/xz
выражение Q приведем к виду дизъюнкция конъюнкций.
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)= =AB((B\/C)\/D)(C\/E)((C\/E)\/(F\/G\/H\/I\/J))(F\/K\/L)((G\/M)\/N)N/\ /\(N\/(D\/L\/ O\/P\/Q))(H\/O\/R)(I\/P\/S)(J\/Q\/T)(E\/(J\/Q\/T))= =AB(C\/E) (F\/K\/L)N(H\/O\/R)(I\/P\/S)(J\/Q\/T) =
=ABN(C\/E)(FH\/FO\/FR\/KH\/KO\/KR\/LH\/LO\/LR)/\ /\(IJ\/IQ\/IT\/PJ\/PQ\/PT\/SJ\/SQ\/ST) =
=ABN(C\/E)(FHIJ\/FHIQ\/FHIT\/ FHPJ\/FHPQ\/FHPT\/FHSJ\/FHSQ\/FHST\/ \/FOIJ\/FOIQ\/FOIT\/FOPJ\/FOPQ\/FOPT\/FOSJ\/FOSQ\/FOST\/ \/FRIJ\/FRIQ\/FRIT\/FRPJ\/FRPQ\/FRPT\/FRSJ\/FRSQ\/FRST\/ \/KHIJ\/KHIQ\/KHIT\/ KHPJ\/KHPQ\/KHPT\/KHSJ\/KHSQ\/KHST\/ \/KOIJ\/KOIQ\/KOIT\/KOPJ\/KOPQ\/KOPT\/KOSJ\/KOSQ\/KOST\/ \/KRIJ\/KRIQ\/KRIT\/KRPJ\/KRPQ\/KRPT\/KRSJ\/KRSQ\/KRST\/ \/LHIJ\/LHIQ\/LHIT\/ LHPJ\/LHPQ\/LHPT\/LHSJ\/LHSQ\/LHST\/ \/LOIJ\/LOIQ\/LOIT\/LOPJ\/LOPQ\/LOPT\/LOSJ\/LOSQ\/LOST\/ \/LRIJ\/LRIQ\/LRIT\/LRPJ\/LRPQ\/LRPT\/LRSJ\/LRSQ\/LRST\/=
=ABNCFHIJ\/ABNCFHIQ\/ABNCFHIT\/ABNCFHPJ\/ABNCFHPQ\/
\/ABNCFHPT\/ABNCFHSJ\/ABNCFHSQ\/ABNCFHST\/ABNEFHIJ\/
\/ABNEFHIQ\/ABNEFHIT\/ABNEFHPJ\/ABNEFHPQ\/ABNEFHPT\/
\/ABNEFHSJ\/ABNEFHSQ\/ABNEFHST\/ABNCFOIJ\/ABNCFOIQ\/
\/ABNCFOIT\/ABNCFOPJ\/ABNCFOPQ\/ABNCFOPT\/ABNCFOSJ\/
\/ABNCFOSQ\/ABNCFOST\/ABNEFOIJ\/ABNEFOIQ\/ABNEFOIT\/
\/ABNEFOPJ\/ABNEFOPQ\/ABNEFOPT\/ABNEFOSJ\/ABNEFOSQ\/
\/ABNEFOST\/ABNCFRIJ\/ABNCFRIQ\/ABNCFRIT\/ABNCFRPJ\/
11
\/ABNCFRPQ\/ABNCFRPT\/ABNCFRSJ\/ABNCFRSQ\/ABNCFRST\/
\/ABNEFRIJ\/ABNEFRIQ\/ABNEFRIT\/ABNEFRPJ\/ABNEFRPQ\/
\/ABNEFRPT\/ABNEFRSJ\/ABNEFRSQ\/ABNEFRST\/ABNCKHIJ\/
\/ABNCKHIQ\/ABNCKHIT\/ABNCKHPJ\/ABNCKHPQ\/ABNCKHPT\/
\/ABNCKHSJ\/ABNCKHSQ\/ABNCKHST\/ABNEKHIJ\/ABNEKHIQ\/
\/ABNEKHIT\/ABNEKHPJ\/ABNEKHPQ\/ABNEKHPT\/ABNEKHSJ\/
\/ABNEKHSQ\/ABNEKHST\/ABNCKOIJ\/ABNCKOIQ\/ABNCKOIT\/
\/ABNCKOPJ\/ABNCKOPQ\/ABNCKOPT\/ABNCKOSJ\/ABNCKOSQ\/
\/ABNCKOST\/ABNEKOIJ\/ABNEKOIQ\/ABNEKOIT\/ABNEKOPJ\/
\/ABNEKOPQ\/ABNEKOPT\/ABNEKOSJ\/ABNEKOSQ\/ABNEKOST\/
\/ABNCKRIJ\/ABNCKRIQ\/ABNCKRIT\/ABNCKRPJ\/ABNCKRPQ\/
\/ABNCKRPT\/ABNCKRSJ\/ABNCKRSQ\/ABNCKRST\/
\/ABNEKRIJ\/ABNEKRIQ\/ABNEKRIT\/ABNEKRPJ\/ABNEKRPQ\/
\/ABNEKRPT\/ABNEKRSJ\/ABNEKRSQ\/ABNEKRST\/ABNCLHIJ\/
\/ABNCLHIQ\/ABNCLHIT\/ABNCLHPJ\/ABNCLHPQ\/ABNCLHPT\/
\/ABNCLHSJ\/ABNCLHSQ\/ABNCLHST\/ABNELHIJ\/ABNELHIQ\/
\/ABNELHIT\/ABNELHPJ\/ABNELHPQ\/ABNELHPT\/ABNELHSJ\/
\/ABNELHSQ\/ABNELHST\/ABNCLOIJ\/ABNCLOIQ\/ABNCLOIT\/
\/ABNCLOPJ\/ABNCLOPQ\/ABNCLOPT\/ABNCLOSJ\/ABNCLOSQ\/
\/ABNCLOST\/ABNELOIJ\/ABNELOIQ\/ABNELOIT\/ABNELOPJ\/
\/ABNELOPQ\/ABNELOPT\/ABNELOSJ\/ABNELOSQ\/ABNELOST\/
\/ABNCLRIJ\/ABNCLRIQ\/ABNCLRIT\/ABNCLRPJ\/ABNCLRPQ\/
\/ABNCLRPT\/ABNCLRSJ\/ABNCLRSQ\/ABNCLRST\/ABNELRIJ\/
\/ABNELRIQ\/ABNELRIT\/ABNELRPJ\/ABNELRPQ\/ABNELRPT\/
\/ABNELRSJ\/ABNELRSQ\/ABNELRST.
12
Все конъюнкции имеют равную длину, выберем любую из них (W).
Например, W = ABNELHPJ.
Объединим строки первичной таблицы переходов:
W= ABNELHPJ = {1},{2,3},{7,8,9},{4,5,13},{6,9},{5,10},{9,11},{5,12,13}.
Далее исключим повторение цифр:
W`= {1},{2,3},{7,8},{4,13},{6},{5,10},{9,11},{12}.
3.5. Построение минимизированной таблицы переходов.
Построим таблицу с учетом объединения строк (Таблица 3).
|
|
|
|
|
Таблица 3 |
|
Минимизированная таблица переходов |
||||
|
|
|
|
|
|
x1x2 |
00 |
01 |
10 |
11 |
|
S |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
{1} |
|
(1), 00 |
2, 01 |
6, 10 |
10, 00 |
|
|
|
|
|
|
{2,3} |
|
~ |
(2), 01 |
(3), 11 |
4, 00 |
|
|
|
|
|
|
{7,8} |
|
~ |
9, 01 |
(8), 00 |
(7), 01 |
|
|
|
|
|
|
{4,13} |
|
1, 00 |
5, 10 |
(13), 01 |
(4), 00 |
|
|
|
|
|
|
{6} |
|
~ |
~ |
(6), 10 |
7, 01 |
|
|
|
|
|
|
{5,10} |
|
1, 00 |
(5), 10 |
11, 11 |
(10), 00 |
|
|
|
|
|
|
{9,11} |
|
1, 00 |
(9), 01 |
(11), 11 |
12, 11 |
|
|
|
|
|
|
{12} |
|
~ |
~ |
13, 01 |
(12), 11 |
|
|
|
|
|
|
3.6. Перенумерация строк минимизированной ТП.
Перенумерация строк заключается в присвоении каждой строке таблицы порядкового номера. Затем цифры состояний внутри клеток таблицы заменяются цифрами, присвоенными тем подмножествам, в которые эти состояния входят.
Получаем минимизированную таблицу переходов (ТП) (Таблица 4).
13
Таблица 4
Таблица переходов, после перенумерации
|
x1x2 |
00 |
01 |
10 |
11 |
S |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
(1), 00 |
2, 01 |
5, 10 |
6, 00 |
|
|
|
|
|
|
2 |
|
~ |
(2), 01 |
(2), 11 |
4, 00 |
|
|
|
|
|
|
3 |
|
~ |
7, 01 |
(3), 00 |
(3), 01 |
|
|
|
|
|
|
4 |
|
1, 00 |
6, 10 |
(4), 01 |
(4), 00 |
|
|
|
|
|
|
5 |
|
~ |
~ |
(5), 10 |
3, 01 |
|
|
|
|
|
|
6 |
|
1, 00 |
(6), 10 |
7, 11 |
(6), 00 |
|
|
|
|
|
|
7 |
|
1, 00 |
(7), 01 |
(7), 11 |
8, 11 |
|
|
|
|
|
|
8 |
|
~ |
~ |
4, 01 |
(8), 11 |
|
|
|
|
|
|
4. Блок-схема синхронного автомата.
Рисунок 5. Схема синхронного автомата
14
5. Кодирование строк таблицы переходов.
5.1. Определение необходимого числа элементов памяти.
Для построения схемы необходимо три элемента памяти: Y1, Y2, Y3.
Число элементов памяти определяется по формуле: m = ]log2S[ = ]log28[ = 3,
где ]a[ – обозначение ближайшего к a целого числа A ≥ a; m – количество необходимых элементов памяти;
S – число состояний автомата, в нашем случае S=8.
В таблице 5 представлено кодирование для минимизированной таблицы переходов. Теперь состоянию 1 соответствует комбинация 000, состоянию 2
– 001 и так далее до последнего 8 – 111.
|
|
|
|
Таблица 5 |
|
|
Кодирование состояний |
|
|
||
|
|
|
|
|
|
S |
Y1 |
Y2 |
|
Y3 |
|
|
|
|
|
|
|
1 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
2 |
0 |
0 |
|
1 |
|
|
|
|
|
|
|
3 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
4 |
0 |
1 |
|
1 |
|
|
|
|
|
|
|
5 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
6 |
1 |
0 |
|
1 |
|
|
|
|
|
|
|
7 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
8 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
5.2. Кодированные таблица переходов и таблица выходов.
Составляются кодированные таблица переходов и таблица выходов.
В качестве исходной берется таблица 4, в которой состояния автомата S
заменяются соответствующими кодами из таблицы 5.
15
В таблицах 6 и 7 соответственно представлены таблица переходов и таблица выходов.
|
|
|
|
|
Таблица 6 |
|
|
Кодированная таблица переходов |
|
|
|||
|
|
|
|
|
|
|
|
x1x2 |
00 |
01 |
10 |
|
11 |
Y1Y2Y3 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
000 |
|
(000) |
001 |
100 |
|
101 |
|
|
|
|
|
|
|
001 |
|
~ |
(001) |
(001) |
|
011 |
|
|
|
|
|
|
|
010 |
|
~ |
110 |
(010) |
|
(010) |
|
|
|
|
|
|
|
011 |
|
000 |
101 |
(011) |
|
(011) |
|
|
|
|
|
|
|
100 |
|
~ |
~ |
(100) |
|
010 |
|
|
|
|
|
|
|
101 |
|
000 |
(101) |
110 |
|
(101) |
|
|
|
|
|
|
|
110 |
|
000 |
(110) |
(110) |
|
111 |
|
|
|
|
|
|
|
111 |
|
~ |
~ |
011 |
|
(111) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7 |
|
|
|
Кодированная таблица выходов |
|
|
|||
|
|
|
|
|
|
|
|
|
x1x2 |
|
00 |
01 |
10 |
|
11 |
Y1Y2Y3 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
000 |
|
|
00 |
01 |
10 |
|
00 |
|
|
|
|
|
|
|
|
001 |
|
|
~ |
01 |
11 |
|
00 |
|
|
|
|
|
|
|
|
010 |
|
|
~ |
01 |
00 |
|
01 |
|
|
|
|
|
|
|
|
011 |
|
|
00 |
10 |
01 |
|
00 |
|
|
|
|
|
|
|
|
100 |
|
|
~ |
~ |
10 |
|
01 |
|
|
|
|
|
|
|
|
101 |
|
|
00 |
10 |
11 |
|
00 |
|
|
|
|
|
|
|
|
110 |
|
|
00 |
01 |
11 |
|
11 |
|
|
|
|
|
|
|
|
111 |
|
|
~ |
~ |
01 |
|
11 |
|
|
|
|
|
|
|
|
16
6. Реализация автомата в базисе {И, ИЛИ, НЕ, Триггер}.
6.1. Таблицы истинности управления триггерами по входам YS и YR и
выходных функций z1, z2.
Правила вычисления функций YS и YR следуют из логики работы RS-
триггера при переключении из одного состояния в другое в моменты времени
t –1 и t:
1)если y(t –1) = 0, y(t) = 1, то YS = 1, YR = 0, так как триггер должен переключиться из состояния 0 в состояние 1;
2)если y(t –1) = 0, y(t) = 0, то YS = 0, YR = ~, так как триггер был в состоянии
0 и должен сохранить это состояние;
3)если y(t –1) = 1, y(t) = 0, то YS = 0, YR = 1, так как триггер должен переключиться из состояния 1 в состояние 0;
4)если y(t –1) = 1, y(t) = 1, то YS = ~, YR = 0, так как триггер был в состоянии
1 и должен сохранить это состояние.
Эти правила представлены в таблицах 8 и 9.
|
|
|
Таблица 8 |
|
|
|
Таблица 9 |
||
|
Функция YS |
|
Функция YR |
||||||
|
|
|
|
|
|
|
|
|
|
|
y(t) |
0 |
1 |
|
|
y(t) |
0 |
1 |
|
y(t-1) |
|
|
y(t-1) |
|
|
||||
|
|
|
|
|
|
|
|
||
0 |
|
0 |
1 |
|
0 |
|
~ |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
~ |
|
1 |
|
1 |
0 |
|
Используя правила, изложенные в таблицах 8 и 9, построим таблицу значений S и R входов на всех входных наборах (Таблица 10).
17
Таблица 10
Таблица истинности функций включения YS и YR триггеров
Номер |
x1x2y1y2y3 |
YS1 |
YR1 |
YS2 |
YR2 |
YS3 |
YR3 |
Z1 |
Z2 |
0 |
00000 |
0 |
~ |
0 |
~ |
0 |
~ |
0 |
0 |
1 |
00001 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
2 |
00010 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
3 |
00011 |
0 |
~ |
0 |
1 |
0 |
1 |
0 |
0 |
4 |
00100 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
5 |
00101 |
0 |
1 |
0 |
~ |
0 |
1 |
0 |
0 |
6 |
00110 |
0 |
1 |
0 |
1 |
0 |
~ |
0 |
0 |
7 |
00111 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
8 |
01000 |
0 |
~ |
0 |
~ |
1 |
0 |
0 |
1 |
9 |
01001 |
0 |
~ |
0 |
~ |
~ |
0 |
0 |
1 |
10 |
01010 |
1 |
0 |
~ |
0 |
0 |
~ |
0 |
1 |
11 |
01011 |
1 |
0 |
0 |
1 |
~ |
0 |
1 |
0 |
12 |
01100 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
13 |
01101 |
~ |
0 |
0 |
~ |
~ |
0 |
1 |
0 |
14 |
01110 |
~ |
0 |
~ |
0 |
0 |
~ |
0 |
1 |
15 |
01111 |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
~ |
16 |
10000 |
1 |
0 |
0 |
~ |
0 |
~ |
1 |
0 |
17 |
10001 |
0 |
~ |
0 |
~ |
~ |
0 |
1 |
1 |
18 |
10010 |
0 |
~ |
~ |
0 |
0 |
~ |
0 |
0 |
19 |
10011 |
0 |
~ |
~ |
0 |
~ |
0 |
0 |
1 |
20 |
10100 |
~ |
0 |
0 |
~ |
0 |
~ |
1 |
0 |
21 |
10101 |
~ |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
22 |
10110 |
~ |
0 |
~ |
0 |
0 |
~ |
1 |
1 |
23 |
10111 |
0 |
1 |
~ |
0 |
~ |
0 |
0 |
1 |
24 |
11000 |
1 |
0 |
0 |
~ |
1 |
0 |
0 |
0 |
25 |
11001 |
0 |
~ |
1 |
0 |
~ |
0 |
0 |
0 |
26 |
11010 |
0 |
~ |
~ |
0 |
0 |
~ |
0 |
1 |
27 |
11011 |
0 |
~ |
~ |
0 |
~ |
0 |
0 |
0 |
28 |
11100 |
0 |
1 |
1 |
0 |
0 |
~ |
0 |
1 |
29 |
11101 |
~ |
0 |
0 |
~ |
~ |
0 |
0 |
0 |
30 |
11110 |
~ |
0 |
~ |
0 |
1 |
0 |
1 |
1 |
31 |
11111 |
~ |
0 |
~ |
0 |
~ |
0 |
1 |
1 |
18
6.2. Карты Карно и минимизированные ФАЛ.
Минимизация функций переключения и выходов триггера методом карт Карно представлена на рисунках 6-а и 6-б. Выделим максимальные контуры каждой из функций переключения и выходов. Далее запишем функцию в виде: дизъюнкция конъюнкций переменных, входящих в контур.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
YS1 x1x2 y2 x1x2 y1 y2 y3 x1 x2 y2 y3 |
YR1 x1 x2 x2 y1 y2 y3 x2 y2 y3 |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
YS 2 x2 y1 y3 x1x2 y1 y3 x1 x2 y1 y3 |
YR2 x1 x2 x1 y3 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
YS 3 x2 y1 y2 x1x2 y1 y2 |
YR3 x1 x2 x2 y1 y2 |
||||||||||||
Рисунок 6-a. Карты Карно
19
Z1 x1x2 y2 y3 x1x2 y1 y2 x1x2 y1 y2 x1 y1 y2 y3 x1 x2 y2
Z2 x2 y1 y2 y3 x1x2 y1 y2 x1 x2 y3 x2 y2 y3 x1 y1 y2
Рисунок 6-б. Карты Карно
Выпишем полученные функции:
YS1 x1x2 y2 x1x2 y1 y2 y3 x1 x2 y2 y3 ;
YR1 x1 x2 x2 y1 y2 y3 x2 y2 y3 ;
YS 2 x2 y1 y3 x1x2 y1 y3 x1 x2 y1 y3 ;
YR2 x1 x2 x1 y3 ;
YS 3 x2 y1 y2 x1x2 y1 y2 ;
YR3 x1 x2 x2 y1 y2 ;
Z1 x1x2 y2 y3 x1x2 y1 y2 x1x2 y1 y2 x1 y1 y2 y3 x1 x2 y2 ;
Z2 x2 y1 y2 y3 x1x2 y1 y2 x1 x2 y3 x2 y2 y3 x1 y1 y2 .
20