Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

101

6 АСИНХРОННЫЕ АВТОМАТЫ. ГОНКИ В АВТО-

МАТАХ

6.1 Понятие асинхронного автомата

Различия между синхронными и асинхронными автома-

тами обусловлены задержками распространения сигналов в

элементах, из которых построен автомат и физическими

принципами работы устройств в схеме автомата.

Синхронный автомат может изменять своё состояние

только в определённые моменты времени, а именно в момен-

ты поступления синхронизирующих импульсов.

В отличие от синхронных, асинхронный автомат пере-

ключается в момент изменения логического значения вход-

ных сигналов. Входные сигналы асинхронного автомата об-

ладают следующими свойствами:

-сигнал присутствует на входе автомата в каждый мо-

мент времени;

-длительность входного сигнала не ограничена и пре-

вышает некоторую минимальную величину.

изменения входного сигнала могут происходить в про-

извольные моменты времени.

При функционировании автомата могут появиться так

называемые состязания. Это явление возникает вследствие

того, что элементы памяти имеют различные, хотя и доста-

точно близкие, времена срабатывания. Различны также за-

держки сигналов возбуждения, поступающих на входные ка-

налы элементарных автоматов по логическим цепям

неоди-

наковой длины.

Если при переходе автомата из одного состояния в дру-

гое должны изменить свои состояния сразу несколько запо-

минающих элементов, то между ними начинаются состяза-

ния. Тот элемент, который выиграет эти состязания, т.е. из-

менит свое состояние ранее, чем другие элементы, может че-

рез цепь обратной связи

изменить сигналы на входах некото-

рых запоминающих элементов до того, как другие, участ-

102

вующие в состязаниях элементы, изменят свои состояния.

Это может привести к переходу автомата в состояние, не

предусмотренное его графом. Поэтому в процессе перехода

из состояния a

в состояние a

под действием входного сиг-

нала Z

автомат может оказаться в состоянии a

или a

: (ри-

сунок 6.1).

Рисунок 6.1 - Состязания в

автомате

Если затем при том же входном сигнале Z

автомат из а

и а

перейдет в а

, то такие состязания являются допустимы-

ми или некритическими.

Если же в этом автомате есть переход, например, из а

в а



≠ а

под действием того же сигнала z

, то автомат может

перейти в а

, а не в а

и правильность его работы будет на-

рушена (рисунок 6.2). Такие состязания называются критиче-

скими состязаниями или гонками и необходимо принимать

меры для их устранения.

103

Рисунок 6.2 - Гонки в автомате

6.2 Устранение гонок

Устранить гонки можно аппаратными средствами, либо

используя специальные методы кодирования. Один из спо-

собов ликвидации гонок состоит в тактировании входных

сигналов автомата импульсами определенной длительно-

сти. Предполагается, что кроме входных каналов х

, ..., х

имеется еще канал С от генератора синхроимпульсов, по ко-

торому поступает сигнал С = 1 в момент прихода импульса и

С = 0 при его отсутствии. В связи с этим входным сигналом

на переходе (a

, a

) будет не z

, а Cz

. Тогда, если длитель-

ность импульса t

меньше самого короткого пути прохожде-

ния тактированного сигнала обратной связи по комбинаци-

онной схеме, то

к моменту перехода в промежуточное со-

стояние a

сигнал C = 0, CZ

=0, что исключает гонки. Канал

С – это фактически синхровход триггера. Недостаток метода

– в трудности подбора требуемой длительности импульса,

т.к. она зависит от многих факторов, не поддающихся стро-

гому учету.

Другой способ ликвидации гонок заключается во введе-

нии двойной

памяти. В этом случае каждый элемент памяти

дублируется, причем перепись из первого элемента памяти

во второй происходит в момент С = 0(рисунок 6.3).

104

Рисунок 6.3 - Элемент с двойной памятью.

Сигналы обратной связи для получения функций возбу-

ждения и функций выходов автомата снимаются с выхода

второго триггера. Таким образом состязания могут возник-

нуть только между первыми триггерами, выходы вторых

триггеров не могут измениться до тех пор, пока С не станет

равным 0. Но тогда Cz

= 0, первый триггер перестанет вос-

принимать информацию, и гонок не будет.

Для устранения гонок используются специальные мето-

ды противогоночного кодирования, среди которых чаще все-

го применяется так называемое соседнее кодирование со-

стояний автомата, при котором условие отсутствия гонок

всегда выполнено. При соседнем кодировании любые два

состояния, связанные дугой на графе автомата,

кодируются

наборами, отличающимися состояниями лишь одного эле-

мента памяти.

Соседнее кодирование не всегда возможно. Граф авто-

мата, допускающее соседнее кодирование, должен удовле-

творять ряду требований, а именно:

1. В графе автомата не должно быть циклов с нечетным

числом вершин;

2. Два соседних состояния второго порядка не должны

иметь более двух состояний

, лежащих между ними.

Под состояниями второго порядка понимаются такие

два состояния, путь между которыми по графу автомата со-

стоит из двух ребер (независимо от ориентации). Примеры

105

графов автоматов допускающих и не допускающих соседнее

кодирование представлены на рисунке 6.4 (а) и (б) соответст-

венно.

При соседнем кодировании обычно пользуются картой

Карно. В этом случае состояния, связанные дугой, распола-

гают на соседних клетках карты (рисунок 6.5).

Легко видеть, что при соседнем кодировании на каждом

переходе переключается только один триггер, что принципи

ально устраняет гонки.

Анализ канонического метода структурного синтеза ав-

томата показывает, что различные варианты кодирования

состояний автомата приводят к различным выражениям

функций возбуждения памяти и функций выходов, в резуль-

тате чего сложность комбинационной схемы существенно

зависит от выбранного кодирования.

Рисунок 6.4 - Графы автоматов допускающие (а) и не допус-

кающие (б) соседнее

кодирование

~000 a

~010 a

~110 a

~111

106

~101 a

~001 a

~100

Рисунок 6.5 - Карта Карно для соседнего кодирования

Среди множества существующих алгоритмов кодирова-

ния рассмотрим имеются два наиболее часто встречаемых:

1) алгоритм кодирования для D-триггеров;

2) эвристический алгоритм кодирования.

Рассмотрим алгоритм кодирования для D-триггеров.

Согласно рассматриваемому алгоритму при кодирова-

нии необходимо выполнить следующее:

1. Каждому состоянию автомата а

(m = 1,2,...,M) ста

вится в соответствие целое число N

, равное числу перехо-

дов в состояние а

равно числу появлений а

в поле

таблицы переходов или числу дуг, входящих в а

при гра-

фическом способе задания автомата).

2. Числа N

, N

, ..., N

упорядочиваются по убыванию.

3. Состояние а

наибольшим N

кодируется кодом:

, где R-количество элементов памяти.

4. Следующие R состояний согласно списка пункта 2

кодируются кодами, содержащими только одну 1: 00 ... 01,

00 ... 10, ... , 01 ... 00, 10 ... 00.

Для оставшихся состояний опять в порядке списка п.2.

используют коды с двумя единицами, затем с тремя и так да-

лее пока не будут закодированы все состояния.

В результате

получается такое кодирование, при кото-

ром чем больше имеется переходов в некоторое состояние,

тем меньше единиц в его коде. Так как для D-триггеров

функции возбуждения однозначно определяются кодом со-

стояния перехода, то очевидно, что выражения для функций

возбуждения будут проще. Этот метод особенно эффективен

при отсутствии минимизации функций возбуждения,

что

имеет место в реальных автоматах с большим количеством

00 0...

123

107

внутренних состояний и входных переменных.

В частности, для автомата, заданного своими таблицами

переходов и выходов (см. ниже) при кодировании на базе D-

триггеров:

~ N

= 3 N

= 000

~ N

= 4 N

= 001

~ N

= 5 N

= 010

~ N

= 5 N

= 100

~ N

= 1 N

= 011

Аналогично кодированию внутренних состояний для D-

триггеров можно кодировать выходные сигналы для любого

типа триггеров, т.е. чем чаще вырабатывается

данный вы-

ходной сигнал w

, тем меньше единиц в его коде. Так для

данного автомата имеем:

~ N

= 6 N

= 00

~ N

= 5 N

= 01

~ N

= 2 N

= 10

~ N

= 2 N

= 11

108

7. МИКРОПРОГРАММИРОВАНИЕ

7.1 Операционный и управляющий автоматы

В ЭВМ для выполнения операций используются опера-

ционные устройства – каналы ввода-вывода, контроллеры,

процессоры, которые в процессе работы осуществляют пре-

образование их входных сигналов в выходные по некоторому

закону. Организация этих устройств основана на принципе

микропрограммного управления, который заключается в сле-

дующем:

1. Любая

операция, реализуемая устройством, рассмат-

ривается как сложное действие, которое разделяется на по-

следовательность элементарных действий над словами ин-

формации. Эти элементарные действия называются микро-

операциями. К микрооперациям относятся: передача инфор-

мации из одного регистра в другой, взятие обратного кода,

сдвиг, суммирование, инверсия, инкремент и/или декремент

значения в счетчике и т

.д.

2. Для управления порядком следования микроопераций

используются логические условия, которые в зависимости от

значений слов, преобразуемых микрооперациями, принима-

ют значения "ложь" или "истина" (1 или 0).

3. Процесс выполнения операций в устройстве описыва-

ется в форме алгоритма, который представляется в терминах

микроопераций и логических условий и называется микро-

программой. Микропрограмма определяет порядок

провер-

ки значений логических условий и следования микроопера-

ций, необходимый для получения требуемых результатов.

4. На основе микропрограммы определяется структура и

порядок функционирования устройства во времени.

В любом устройстве обработки цифровой информации

можно выделить два блока – операционный автомат (ОА) и

управляющий автомат (УА) (рисунок 7.1).

109

Операционный автомат (ОА) хранит слова информации,

выполняет набор микроопераций и вычисляет значения логи-

ческих условий, т.е. операционный автомат только хранит и

непосредственно обрабатывает данные. Для работы ОА ис-

пользует входные слова, вводимые в автомат в качестве опе-

рандов, формирует выходные слова, являющиеся результа-

тами операций. В процессе работы ОА может

использовать

внутренние слова – например, константы, или слова для хра-

нения вспомогательной информации при выполнении микро-

операций. ОА может выполнять микрооперации и вычислять

логические условия, но не определяет порядок следования

этих действий во времени. Т.е. ОА характеризует средства,

которые могут быть использованы для вычислений, но не сам

вычислительный процесс.

Рисунок

7.1

Порядок выполнения действий во времени в ОА, обу-

словленный алгоритмом выполнения операций, задает

управляющий автомат (УА), который генерирует последова-

тельность управляющих сигналов для ОА. С каждым управ-

110

ляющим сигналом связана одна микрооперация. Значения

логических условий, вычисляемые в ОА, передаются в УА.

Таким образом, в УА поступают коды операций, которые

нужно выполнить в устройстве, и коды логических условий

из ОА.

Т.о. любое операционное устройство – процессор, канал

ввода-вывода и т.д. – является композицией операционного и

управляющего автоматов. Операционный

автомат, реализуя

действия над словами информации, является исполнительной

частью устройства, работой которого управляет управляю-

щий автомат, генерирующий необходимые последовательно-

сти управляющих сигналов.

Порядок выполнения действий во времени задается опе-

раторной схемой алгоритма (микропрограммы), которая

обычно представляется в виде граф - схемы алгоритма (ГСА).

ГСА определяет вычислительный процесс последовательно

во времени, устанавливая

порядок проверки логических ус-

ловий х

-х

и порядок следования микроопераций у

-у

В ГСА обычно используют вершины следующих типов:

- вершина «начало» имеет один выход, входов

не имеет. Обозначает начало микропрограммы

- вершина «конец» имеет любое число входов,

выходов не имеет. Обозначает конец микро-

программы.

- операторная вершина имеет

любое число вхо-

дов, один выход. Внутри операторной машины

записывается одна микрокоманда - совокуп-

ность микроопераций, допускающих совмест-

ное (т.е. одновременное) выполнение.

- условная вершина имеет любое число входов

и 2 выхода. Внутри условной вершины записы-

вается булевое выражение, в зависимости от

значения которого осуществляется выбор на-

правления дальнейшего выполнения микропро-