Построение функциональной схемы конечного автомата

В общем виде структура конечного автомата задается функциональным преобразователем (F) и блоком элементов памяти (ЭП). Как уже говорилось, потенциальные выходы автомата (микрокоманды) реализуются как функции состояния, запоминаемого в ЭП, а импульсные выходы реализуются в функциональном преобразователе F. Структурная схема управляющего автомата, таким образом, может быть представлена рис. 12.

Прежде чем приступать к реализации автомата рис. 11, заметим, что его граф переходов не полностью определен; переходы под воздействием сигнала “а” не имеют выходных сигналов, а из состояния “отображение времени” переход под воздействием сигнала “b” вообще не определен. Неопределенность первого типа, очевидно, означает следующее: в результате перехода под воздействием сигнала “а“ неявно предполагается, что на выходе возникает нейтральный сигнал, которому не соответствует никакой микрокоманды. Очевидный метод устранения этой неопределенности – это явное введение такого сигнала. Второй вид неопределенности - отсутствие перехода из состояния отображения времени под воздействием сигнала “b”- также должен быть устранен. Поскольку в этом состоянии внешний сигнал “b” может быть подан, следует явно определить реакцию автомата на этот сигнал. Примем следующее решение: в упомянутом состоянии автомат на входной сигнал “b” не реагирует, т.е. остается в том же состоянии, выдавая на выход нейтральный сигнал (обозначим его z3). Полностью определенный граф переходов управляющего автомата электронных часов представлен на рис. 13.

                          Рис. 12                                                                                           Рис. 13

Этому графу переходов соответствует следующая таблица переходов.

Таблица 1

Для реализации автомата в соответствии с графом переходов (рис. 13) необходимо закодировать входы, выходы и состояния автомата двоичными наборами, после чего из графа или таблицы переходов можно легко построить таблицы истинности выходов схемы F и FL. В нашем случае для кодирования трех состояний достаточно двух двоичных разрядов. Выберем кодирование так:

Отображение времени ........ 00

Коррекция часов             ........ 01

Коррекция минут       ........ 11

Два входных сигнала “a” и “b” можно закодировать одним двоичным разрядом: x=1 для “a” и x=0 для “b”. Кодирование выходных импульсных сигналов проведем так, чтобы разряды кода соответствовали импульсным управляющим микрокомандам i1 и i2: пусть двоичный разряд у1 соответствует микрокоманде i1. Тогда:

                               y1 y2  

z1 закодируем 1   0

z2 закодируем 0   1

z3 закодируем   0   0

Кодировка выходных потенциальных сигналов проста: каждый разряд кода соответствует одной потенциальной управляющей микрокоманде. Таких команд две, L1 и L2, поэтому теперь можно легко построить таблицы истинности для преобразований F и FL; обозначая q1 и q2 - двоичные разряды кода текущего состояния, а Q1 и Q2 -двоичные разряды кода следующего состояния, составляем Таблицы 2 и 3.

Таблица 2

Таблица 3

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

Рис. 9.14

Таблицы 9.2 и 9.3 задают частично определенные функции. Недоопределенность функций можно использовать для их минимизации. Такой прием здесь допустим, поскольку неопределенность вызвана наличием неиспользованного кода “10” внутреннего состояния автомата. При правильной работе устройства, модель которого представлена графом переходов на рис. 13, его переход в такое состояние из установленного начального состояния никогда не произойдет.

В результате минимизации неполностью определенных логических функций с помощью карт Карно получаем:

  Q1 = Øx q1 \/ x Øq2;          Q2 = q1 \/ x Øq2 \/ Øx q2;

   y1 = Øx q1;                            y2 = Øx Øq1 Øq2 ;

   L1 = Øq1;                             L2 = q1 \/ Øq2;

По полученным формулам легко могут быть построены функциональные схемы F и FL.

Выходы схемы F используются в процессе функционирования электронных часов только в моменты переключения автомата из одного состояния в другое. В теории автоматов переходы между состояниями предполагается мгновенными, в то время как в реальной схеме время перехода имеет вполне определенную длительность, определяемую инерционностью электрических цепей: задержкой появления сигнала на выходе схемы F и временем переключения элементов памяти. Время задержки в современных схемах весьма мало: в ТТЛ-схемах оно составляет величину порядка десятков наносекунд. Обычным приемом, позволяющим решать проблемы, возникающие в переключательных схемах вследствие немгновенности срабатывания, является использование синхронизации - синхроимпульса с длительностью, перекрывающей время переключения схемы. Такой синхроимпульс (обозначим его s) в асинхронных схемах должен формироваться в момент внешних воздействий (в нашем случае при нажатии кнопок “a” и “b”), потому он будет вырабатываться схемой “Преобразователь внешних воздействий” рис. 10. Для хранения номера состояния в периоды между моментами переходов обычно используется триггеры.

Триггер - устройство с двумя устойчивыми состояниями. Основная его функция - хранить один бит информации неограниченное время до тех пор, пока эта информация не будет изменена воздействием на вход триггера. Существует довольно много разновидностей триггеров, различающихся по входным условиям смены состояния. Коротко опишем алгоритм работы D-триггера, который мы будем использовать далее (см. рис. 15). Когда на выходе Q - “1”, а на выходе Q - “0”, говорят, что триггер установлен в единичное состояние. В противном случае (Q - “0”, Q - “1”), считается, что триггер сброшен в нулевое состояние. На выходе Q триггера всегда устанавливается уровень напряжения, противоположный уровню напряжения на Q.

Рис. 15

Непосредственная установка или сброс триггера осуществляется подачей напряжения низкого уровня на входы S (Set-установка) или R (Reset - сброс) соответственно. Подавать логический ноль на оба входа сразу недопустимо. Если низкий уровень присутствует на R или S, то сигналы на входах D и C никак не влияют на состояние триггера. Однако в функциональном плане более важными являются именно входы D (data) и C (clock). Триггер работает так, что сигнал от входа D передается на выход Q в момент положительного перепада напряжения на С. При этом во время постоянного уровня напряжения или в момент отрицательного перепада напряжения на С значение Q не может измениться. Чтобы триггер переключался правильно, уровень на входе D следует зафиксировать заранее, перед приходом тактового перепада на С. Минимальное время между появлением сигнала на D и на С называется защитным интервалом. При работе в таком режиме, на входах R и S должен присутствовать уровень логической единицы.

Использование элементов памяти при реализации конечного автомата имеет некоторые особенности. Дело в том, что в момент переключения автомата необходимо одновременно подавать на вход схемы F (рис. 14) код старого состояния и запоминать код нового, получаемый с выхода этой схемы. Иными словами, существует (возможно, малый) период времени, когда в блоке памяти должны храниться как код старого состояния, так и код нового состояния, получившегося в результате преобразования F. Для разрешения этого противоречия, можно для каждого разряда кода состояния использовать два триггера. Эти триггеры соединяются последовательно (см. рис. 16), и простым приемом достигается то, что информация о номере состояния на выходе F при одном переключении автомата будет использоваться на входе F при следующем переключении. Рассмотрим, как это делается (рис. 16).

Сигналы x и s появляются практически одновременно. На выходе F после появления x на входе устанавливается код следующего состояния (пара Q1 и Q2), который необходимо запомнить в триггерах Т1-Т2. Необходимо помнить, что в тот момент, когда на тактовый вход С поступает положительный перепад напряжения, сигнал на информационном входе D должен быть установлен заранее. Поэтому на С входы триггеров T1 и T2 мы будем подавать синхроимпульс s с - задержкой t1 такой, что t0 < t1 < ts. Здесь t0 - это сумма задержки сигнала в блоке F и защитного интервала триггера, а ts - продолжительность синхроимпульса s. Положительный перепад напряжения на тактовые входы С триггеров T3-T4 надо подать только после окончания действия синхроимпульса. Это можно сделать инверсией сигнала, который мы подаем на С входы Т1-Т2.

Рис. 16

Требуемый выход устройства управления электронных часов - управляющие микрокоманды - получаются из кодов состояний и выходов автомата довольно просто. Потенциальные микрокоманды, как функции состояний автомата, снимаются с выходов логической схемы FL (см. рис. 16), являющейся, фактически, дешифратором. Импульсные микрокоманды являются функцией выходных сигналов управляющего автомата. В нашем случае кодировка выходов автомата выбрана так, что каждый разряд выходного сигнала является одной из искомых микрокоманд, и дополнительного функционального преобразователя строить не надо. Однако для того, чтобы эти микрокоманды имели импульсную форму, определим микрокоманду i как конъюнкцию выхода у схемы F и синхроимпульса s.