Алгоритм кодирования для D-триггеров.
Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:
1.Каждому состоянию автомата аm (m = 1,2,...,M) ставится в соответствие целое число Nm, равное числу переходов в состояние аm (Nm равно числу появлений аm в поле таблицы переходов или числу дуг, входящих в аm при графическом способе задания автомата).
2.Числа N1, N2, ..., Nm упорядочиваются по убыванию.
3.Состояние аs с наибольшим Ns кодируется кодом:
, где R-количество элементов памяти.
4.Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.
5.Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.
В результате получается такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц в его коде. Т.к. для D-триггеров функции возбуждения однозначно определяются кодом состояния перехода, то очевидно, что выражения для функций возбуждения будут проще. Этот метод особенно эффективен при отсутствии минимизации функций возбуждения, что имеет место в реальных автоматах с большим количеством внутренних состояний и входных переменных.
В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже) при кодировании на базе D-триггеров.
| a1 | a2 | a3 | a4 | a5 | a1 | a2 | a3 | a4 | a5 | |||
| Z1 | a1 | a1 | a5 | a3 | a1 | Z1 | w1 | w2 | w1 | w1 | w1 | |
| Z2 | a2 | a3 | a2 | a3 | a3 | Z2 | w1 | w3 | w4 | w2 | w2 | |
| Z3 | a3 | a4 | a2 | a4 | a2 | Z3 | w2 | w2 | w2 | w1 | w3 |
|
a1 ~ N1 = 3 N3 a3 = 000
a2 ~ N2 = 4 N2 a2 = 001
a3 ~ N3 = 5 N1 a1 = 010
a4 ~ N4 = 5 N4 a4 = 100
a5 ~ N5 = 1 N5 a5 = 011
Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал wi, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:
w1 ~ N1 = 6 N1 w1 = 00
w2 ~ N2 = 5 N2 w2 = 01
w3 ~ N3 = 2 N3 w3 = 10
w4 ~ N4 = 2 N4 w4 = 11
Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.