2014-02-02
1543
Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:
1. Каждому состоянию автомата а m (m = 1,2,..., M) ставится в соответствие целое число N m, равное числу переходов в состояние а m (N m равно числу появлений а m в поле таблицы переходов или числу дуг, входящих в а m при графическом способе задания автомата).
2. Числа N 1, N 2,..., N m упорядочиваются по убыванию.
3. Состояние а s с наибольшим N s кодируется кодом:
, где R -количество элементов памяти.
4. Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00... 01, 00... 10,..., 01... 00, 10... 00.
5. Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.
В результате получается такое кодирование, при котором чем больше имеется переходов в некоторое состояние, тем меньше единиц в его коде. Т.к. для D -триггеров функции возбуждения однозначно определяются кодом состояния перехода, то очевидно, что выражения для функций возбуждения будут проще. Этот метод особенно эффективен при отсутствии минимизации функций возбуждения, что имеет место в реальных автоматах с большим количеством внутренних состояний и входных переменных.
|
|
|
В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже) при кодировании на базе D -триггеров.
| a 1 | a 2 | a 3 | a 4 | a 5 | a 1 | a 2 | a 3 | a 4 | a 5 | |||
| Z 1 | a 1 | a 1 | a 5 | a 3 | a 1 | Z 1 | w 1 | w 2 | w 1 | w 1 | w 1 | |
| Z 2 | a 2 | a 3 | a 2 | a 3 | a 3 | Z 2 | w 1 | w 3 | w 4 | w 2 | w 2 | |
| Z 3 | a 3 | a 4 | a 2 | a 4 | a 2 | Z 3 | w 2 | w 2 | w 2 | w 1 | w 3 |
|
a 1 ~ N 1 = 3 N 3 a 3 = 000
a 2 ~ N 2 = 4 N 2 a 2 = 001
a 3 ~ N 3 = 5 N 1 a 1 = 010
a 4 ~ N 4 = 5 N 4 a 4 = 100
a 5 ~ N 5 = 1 N 5 a 5 = 011
Аналогично кодированию внутренних состояний для D -триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал w i, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:
w 1 ~ N 1 = 6 N 1 w 1 = 00
w 2 ~ N 2 = 5 N 2 w 2 = 01
w 3 ~ N 3 = 2 N 3 w 3 = 10
w 4 ~ N 4 = 2 N 4 w 4 = 11
Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.
