Материал: Kursovaya_TDU
Рассмотрим первый цикл работы: из состояния (а1, 1) со значением входов x1x2 = 00 и выходов z1z2 = 00 схема под воздействием входного сигнала 11 переходит в состояние (а2, 2) со значением выходов z1z2 = 01. Затем под воздействием входного сигнала 01 схема переходит в состояние (а3, 3) со значением выходов z1z2 = 01. В состояние 4 (а4, 4) схема переходит под воздействием входного сигнала 10 со значением выходов z1z2 = 01. Потом схема переходит в состояние 5 (а2, 5) со значением выходов z1z2 = 11. Завершается циклическая вход-выходная первая последовательность подачей входного сигнала 00 и переходом схемы в начальное состояние (а1, 1).
Затем таблица переходов расширяется с учетом второй и третьей вход-выходных последовательностей. При этом их начальные состояния совпадают с начальным состоянием первой последовательности.
Построим граф переходов (рис. 8).
Для начала вводятся обозначения: вершина графа представляет собой круг, поделенный по диаметру пополам горизонтальной чертой, над чертой пишутся номера состояний, под чертой – значения выходов. Дуги графа – все возможные переходы из данного состояния в другое, включая устойчивые состояния.
Итак, для примера рассмотрим построение графа для первой вход- временной последовательности: из состояния 1, 00 под входным воздействием 11 схема переходит в состояние 2, 00, далее под воздействием 01 схема переходит в состояние 3, 11, затем под входным воздействием 10 – в состояние 4, 01, под воздействием 01 – в состояние 5, 10, наконец, под воз- действием 00 – в исходное состояние 1, 01. Устойчивые состояния на графе показываются дугами, исходящими и входящими в одну и ту же вершину графа с подписью значений входов схемы. Аналогично строится граф для оставшихся циклов работы схемы.
Рис. 8. Граф переходов.
4. Минимизация числа строк таблицы переходов.
4.1. Нахождение максимальных подмножеств совместимых строк (мпсс тп).
Находятся
множества
– множества строк, в которых в столбце
j
проставлено состояние i
или знак безразличного состояния (~).
Если в столбце есть только одно устойчивое
состояние, то множество
не составляется. В соответствии с этим
правилом выписаны подмножества
совместимых по столбцам строк:
Е22={1,2,3,6,7} Е213 ={3,6,7,12,13} Е412={2,5,8,9,11,12,13}
Е25={3,4,5,6,7} Е44={2,3,4,5,8,9,13} Е33={2,3,4,5,9,10,11,12,13}
Е29={3,6,7,8,9} Е47 ={2,5,6,7,8,9,13} Е36={1,4,5,6,9,10,11,12,13}
Е211={3,6,7,10,11} Е410={1,2,5,8,9,10,13} Е38={4,5,7,8,9,10,11,12,13}
Находятся
множества
для всех четверок
.
Е2,3,4={2,3} Е5,3,4={3,4,5} Е9,3,4={3,9}
Е2,6,4= ø Е5,6,4={4,5} Е9,6,4={9}
Е2,8,4= ø Е5,8,4={4,5} Е9,8,4={8,9}
Е2,3,7={2} Е5,3,7={5} Е9,3,7={9}
Е2,6,7= {6} Е5,6,7={5,6} Е9,6,7={6,9}
Е2,8,7={7} Е5,8,7={5,7} Е9,8,7={7,8,9}
Е2,3,10={2} Е5,3,10={5} Е9,3,10={9}
Е2,6,10= {1} Е5,6,10={5} Е9,6,10={9}
Е2,8,10= ø Е5,8,10={5} Е9,8,10={8,9}
Е2,3,12= {2} Е5,3,12={5} Е9,3,12={9}
Е2,6,12= ø Е5,6,12={5} Е9,6,12={9}
Е2,8,12= ø Е5,8,12={5} Е9,8,12={8,9}
Е11,3,4= {3} Е13,3,4={3,13}
Е11,6,4 = ø Е13,6,4={3,13}
Е11,8,4= ø Е13,8,4=1{3}
Е11,3,7= ø Е13,3,7=1{3}
Е11,6,7= {6} Е13,6,7={ 6,13 }
Е11,8,7={7} Е13,8,7={7,13}
Е11,9,10={10} Е13,3,10={13 }
Е11,6,10={10} Е13,6,10={ 13 }
Е11,8,10={10} Е13,8,10={13}
Е11,3,12={11} Е13,3,12={ 12,13 }
Е11,6,12={11} Е13,6,12={12,13}
Е11,8,12={11} Е13,8,12={12,13}
Из
полученных множеств исключаются те,
которые полностью входят в другое
множество. Оставшиеся множества
являются максимальными подмножествами
совместимых строк, они обозначаются
латинскими буквами:
Е2,3,4={2,3}= A Е11,3,10={10}= К
Е5,3,4={3,4,5}= B Е11,3,12 ={11}= L
Е5,6,7={5,6}= C Е13,3,12={12,13}= М
Е5,8,7={5,7}= D Е2,6,10 ={13 }= N
Е9,8,7={7,8,9}= E
4.2. Составление таблицы покрытий.
Столбцы таблицы соответствуют множествам A,B, …, O, а строки – строкам первичной таблицы переходов. На пересечении строки и столбца ставится знак «+», если данная строка таблицы переходов входит в данное подмножество совместимых строк.
Решение задачи покрытия.
Находится минимальное множество столбцов W такое, что каждая строка (состояние) входит хотя бы в одно из них. Для этого составляется алгебраическое выражение Q типа конъюнкция дизъюнкций. Каждая дизъюнкция образуется как дизъюнкция тех столбцов, в которых стоит метка «+» в данной строке (табл. 2).
Таблица 2
Таблица покрытий:
S |
A |
B |
C |
D |
E |
K |
L |
M |
N |
1 |
|
|
|
|
|
|
|
|
+ |
2 |
+ |
|
|
|
|
|
|
|
|
3 |
+ |
+ |
|
|
|
|
|
|
|
4 |
|
+ |
|
|
|
|
|
|
|
5 |
|
+ |
+ |
+ |
|
|
|
|
|
6 |
|
|
+ |
|
|
|
|
|
|
7 |
|
|
|
+ |
+ |
|
|
|
|
8 |
|
|
|
|
+ |
|
|
|
|
9 |
|
|
|
|
+ |
|
|
|
|
10 |
|
|
|
|
|
+ |
|
|
|
11 |
|
|
|
|
|
|
+ |
|
|
12 |
|
|
|
|
|
|
|
+ |
|
13 |
|
|
|
|
|
|
|
+ |
|
4.3. Нахождение минимального множества таблицы покрытия.
С использованием правил повторения и поглощения выражение Q приводится к виду дизъюнкция конъюнкций. Выбирается любая из минимальных конъюнкций W.
В данном случае: W=ABCEKLMN. Объединение строк первичной таблицы переходов:
W= ABCEKLMN ={1}{2,3}{3,4,5}{5,6}{7,8,9}{10}{ ø }{2,13}
Далее исключается повторение цифр:
W`={1}{2,3}{4,5}{6}{7,8,9}{10}{11}{12,13}.
Строится таблица с учетом объединения строк (табл. 3).
Таблица 3
Минимизированная таблица переходов:
S |
x1 x2 |
|||
00 |
01 |
10 |
11 |
|
1 |
(1),00 |
2,01 |
6, 00 |
10, 10 |
2,3 |
~ |
(2),01 |
(3),10 |
~ |
4,5 |
1,00 |
(5),10 |
~ |
(4),11 |
6 |
~ |
~ |
(6),00 |
7,01 |
7,8,9 |
1,00 |
(9),00 |
(8),01 |
(7),01 |
10 |
~ |
11,01 |
~ |
(10),10 |
11 |
~ |
(11),01 |
~ |
12,11 |
12,13 |
1,00 |
(13),10 |
~ |
(12),11 |
4.4. Построение минимизированной таблицы переходов.
Производится перенумерация строк. Она заключается в присвоении каждой строке таблицы порядкового номера. Затем цифры состояний внутри клеток таблицы заменяются цифрами, присвоенными тем подмножествам, в которые эти состояния входят.
Для таблицы 2 имеем:
Q=
A*(А
˅ В)*В*(B
˅ С)*С*Е*Е*Е*K*L*М*N=A*B*C*E*K*L*M*N