ПТЦА - Прикладная теория цифровых автоматов (стр. 13 из 20)
Другой способ ликвидации гонок заключается во введении двойной памяти. В этом случае каждый элемент памяти дублируется, причем перепись из первого элемента памяти во второй происходит в момент С = 0(рис.38.).
Сигналы обратной связи для получения функций возбуждения и функций выходов автомата снимаются с выхода второго триггера. Таким образом состязания могут возникнуть только между первыми триггерами, сигналы ОС (выходы вторых триггеров) не могут измениться до тех пор, пока С не станет равным 0. Но тогда CZf = 0, первый триггер перестанет воспринимать информацию, и гонок не будет.
Для устранения гонок используются специальные методы противогоночного кодирования, среди которых чаще всего применяется так называемое соседнее кодирование состояний автомата, при котором условие отсутствия гонок всегда выполнено. При соседнем кодировании любые два, состояния связанные дугой на графе автомата кодируются наборами, отличающимися состояниями лишь одного элемента памяти.
Соседнее кодирование не всегда возможно. Граф автомата, допускающее соседнее кодирование, должен удовлетворять ряду требований, а именно:
1) в графе автомата не должно быть циклов с нечетным числом вершин;
2) два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними.
Под состояниями второго порядка понимаются такие два состояния, путь между которыми по графу автомата состоит из двух ребер (независимо от ориентации). Примеры графов автоматов допускающих и не допускающих соседнее кодирование представлены на рис.39а. и 39б. соответственно.
При соседнем кодировании обычно пользуются картой Карно. В этом случае состояния, связанные дугой, располагают на соседних клетках карты (рис.40.).
Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.
Кодирование состояний и сложность комбинационной схемы автомата.
Анализ канонического метода структурного синтеза автомата показывает, что различные варианты кодирования состояний автомата приводят к различным выражениям функций возбуждения памяти и функций выходов, в результате чего сложность комбинационной схемы существенно зависит от выбранного кодирования. Среди множества существующих алгоритмов кодирования рассмотрим лишь два наиболее часто встречаемых:
1) алгоритм кодирования для D-триггеров;
2) эвристический алгоритм кодирования.
Алгоритм кодирования для 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 N3a3 = 000
a2 ~ N2 = 4 N2a2 = 001
a3 ~ N3 = 5 N1a1 = 010
a4 ~ N4 = 5 N4a4 = 100
a5 ~ N5 = 1 N5a5 = 011
Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал wi, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:
w1 ~ N1 = 6 N1w1 = 00
w2 ~ N2 = 5 N2w2 = 01
w3 ~ N3 = 2 N3w3 = 10
w4 ~ N4 = 2 N4w4 = 11
Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.
Эвристический алгоритм кодирования.
Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.
Введем некоторые определения.
Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из аi и аj или наоборот.
Обозначим q(i, j) число всевозможных переходов автомата из аi в аj. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).
Введем функцию w(i, j) = р(i, j)× d(i, j), где d(i, j) – число компонентов, которыми коды состояний аi в аj отличаются друг от друга (т.е. кодовое расстояние между кодами аi в аj).
Функция w(i ,j) имеет простой физический смысл. Перход автомата из аi в аj (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям аi и аj (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)×d(i ,j) =w(i ,j).