Лекция 14
Проектирование
последовательных схем.
Минимизация.
Минимизация количества
состояний
• Идентичные состояния – это состояния,
с одними и теми же выходными
сигналами, которые могут быть
объединены
• Эквивалентные состояния – это
состояния, которые можно свести к
одному, если в схеме уже имеются
другие такие же состояния или уже
были сделаны таковыми
Эквивалентные состояния
• Два состояния называются
эквивалентными, и, следовательно,
могут быть заменены одним, если
выполняются следующие условия:
– Выходные сигналы (текущие для модели
Мура и следующие для модели Мили),
связанные с этими двумя состояниями,
одинаковые;
– Соответствующие следующие состояния
также одинаковы или эквивалентны.
Несовместимые по выходу
состояния
• Два состояния называются
несовместимыми по выходу, если не
выполняется условие одинаковости
выходных сигналов, связанные с этими
двумя состояниями
• Несовместимые по выходу (output
incompatible) состояния не могут быть
объединены
• Такие пары исключаются
Таблица состояний модели Мура
Текущее
состояние
1
2
3
4
5
6
7
Следующее состояние, х1х2
00
01
11
10
Выходное
значение,
Z
5
5
3
5
6
3
7
3
3
4
3
7
3
1
2
1
4
2
1
1
1
1
4
5
2
1
7
5
0
0
1
0
0
0
1
«Потенциально эквивалентные»
состояния
• Состояния 3 и 7 имеют одинаковые выходные
значения, поэтому совместимы друг с другом
по выходу, при этом они несовместимы по
выходу со всеми остальными
• Зато состояния 1, 2, 4, 5 и 6 совместимы по
выходу между собой
• Пары 3 и 7, и пары, образуемые состояниями
1, 2, 4, 5 и 6 являются «потенциально
эквивалентными»
Пары эквивалентных состояний
Потенциально
эквивалентные пары
Требуемая
эквивалентность
Несовместимость по
выходу
1, 2
(1, 2), (1, 4)
1, 4
(1, 2)
1, 5
(5, 6), (3, 7), (1, 2)
Х
1, 6
(3, 5), (1, 2), (1, 7)
Х
2, 4
(1, 2)
2, 5
(5, 6), (3, 7), (1, 4)
Х
2, 6
(3, 5), (4, 7)
Х
3, 7
(3, 7), (1, 4)
4, 5
(5, 6), (3, 7), (1, 2)
Х
4, 6
(3, 5), (1, 2), (2, 7)
Х
5, 6
(3, 6), (3, 7), (1, 7)
Х
Эквивалентные пары
• Из таблицы видно, что эквивалентными
парами будут: (1, 2), (2, 4), (1, 4) и (3, 7)
• Состояния 5 и 6 не объединяются с
другими и значит остаются
• Эквивалентность состояний означает:
1≡2≡4и3≡7
• Проведем замену: А для состояний 1, 2 и 4,
В – 3 и 7, С – 5, D – 6
Минимизированная таблица
Мура
Следующее состояние х1х2
00
01
11
10
Выходное
состояние,
Z
А
C
B
A
A
0
В
B
A
A
C
1
С
D
B
A
A
0
D
B
B
A
B
0
Текущее
состояние
Минимизация таблиц состояний
модели Мили
• Для минимизации таблиц состояний
модели Мили используется та же
процедура, что и в случае модели Мура.
• Единственное отличие заключается в
том, что для совместимости по выходу
состояний необходимо, чтобы
выходные значения их следующих
состояний совпадали во всех столбцах
Упрощение диаграммы
состояний
• При использовании большого количества входов,
становится практически невозможной запись
входных состояний в диаграмме состояний
• (например из состояния 1 в состояние 2
переключается при комбинации на входах 0101):
abcd
0101
• Диаграмма с использованием выражений перехода
Диаграмма состояний модели
Мура для JK-триггера
J K
0
0
1
1
0
1
0
1
Qn+1
Qn
0
1
Qn
Прямое назначение переменных
• Если использовать для каждого из
состояний свою переменную, то
количество триггеров увеличится, но
упростится вид функции следующего
состояния
y0y1y2
• Состояние 0 = 1 0 0
• Состояние 1 = 0 1 0
• Состояние 2 = 0 0 1
Квазипрямое назначение
• Назначение при котором за начальным
состоянием резервируется кодовая
комбинация 00…00
• Это позволяет легко обеспечивать
начальную инициализацию триггеров
• Кроме того, в этом случае для описания
n состояний достаточно n-1
переменных
