Структурный синтез. Элементарные автоматы

 

Структурным синтезом занимается структурная теория автоматов. Основная цель этой теории – нахождение общих приемов построения сложных структурных схем автоматов из более простых автоматов, называемых элементарными автоматами. На практике в большинстве случаев применяют элементарные автоматы с двумя внутренними состояниями. В процессе синтеза элементарные автоматы соединяют между собой с помощью логических элементов.

Первая задача, решаемая при структурном синтезе, заключается в выборе системы элементов, из которых должны строиться заданные автоматы. Для того чтобы можно было построить схему любого конечного автомата, эта система элементов должна быть структурно полной.

Теорема о структурной полноте формулируется следующим образом:

Для того чтобы система элементов была структурно полной, необходимо и достаточно, чтобы она содержала какую-либо функционально полную систему логических элементов и хотя бы один элементарный автомат с двумя устойчивыми состояниями, обладающий полной системой переходов и выходов.

Полнота переходов в автомате означает, что для любой пары состояний a_i и a_j существует хотя бы один входной сигнал, который переводит автомат из состояния a_i в состояние a_j, причем i = j и , т.е. в каждом столбце таблицы переходов должны встречаться все состояния. Полнота выходов автомата означает, что в каждом состоянии автомат выдает выходной сигнал, отличный от сигналов, выдаваемых в других состояниях.

Требование полноты системы выходов связано с необходимостью различать внутренние состояния элементарных автоматов, так как в автомате, не обладающем полной системой выходов, различить состояния невозможно и, следовательно, невозможно обеспечить заданные условия функционирования схемы, построенной на его основе.

Если элементарный автомат не имеет полной системы переходов, то это значит, что отсутствует переход хотя бы одного вида. Поэтому построить на основе такого элементарного автомата схему, в которой бы осуществлялись все возможные переходы из одного состояния в другое, нельзя. Таким образом, для построения любого конечного автомата необходимо иметь элементарные автоматы, обладающие полной системой, как переходов, так и выходов.

Рассмотрим конкретные типы элементарных автоматов, имеющих полную систему переходов и выходов и нашедших применение в вычислительной технике.

В настоящее время, как правило, используются элементарные автоматы, имеющие следующие особенности:

1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями.

2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1.

3. Элементарные автоматы могут иметь в общем случае несколько физических входов.

В качестве элементарных автоматов (элементов памяти) в вычислительной технике используются триггеры различных типов.

Триггеры – это электронные устройства, обладающие двумя устойчивыми состояниями равновесия и способные скачком переходить из одного устойчивого состояния в другое под воздействием внешних управляющих сигналов.

Состояние называется устойчивым, если слабое внешнее воздействие не нарушает этого состояния.

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

Для удобства использования в схемах вычислительных устройств триггеры обычно имеют два выхода – прямой Q (называется выход 1) и инверсный (называется выход 0). Когда состояние триггера отображается парой сигналов Q и , то это значит, что состояние представляется в парафазном коде. Выходные сигналы триггеров определяются внутренними состояниями. Двум внутренним состояниям соответствуют два различных выходных сигнала, которые по существу и позволяют физически различать состояния элементарных автоматов.

Триггер (рис. 1.2) в общем случае можно представить как устройство, состоящее из ячейки памяти (ЯП) и логического устройства управления (ЛУ), преобразующего входную информацию в комбинацию сигналов, под воздействием которых ЯП принимает одно из двух устойчивых состояний.

Рис. 1.2. Обобщённое устройство тригера.

Информационные сигналы поступают на входы А и В логического устройства управления и преобразуются в сигналы, поступающие на внутренние входы S и R ячейки памяти. Процесс преобразования информационных сигналов осуществляется под воздействием сигналов, подаваемых на вход V разрешения приёма информации и вход С синхронизации, обеспечивающей тактируемый приём информации.

При наличии входа С триггер называют синхронным, а при его отсутствии – асинхронным.

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

Синхронный триггер имеет синхронизирующий вход С для подачи сигнала, разрешающего переключение триггера. Если С = 0, то триггер сохраняет своё состояние независимо от значений сигналов на его остальных управляющих входах. Триггер переключается только в момент поступления сигнала С = 1.

Триггеры могут иметь статические или динамические входы. Как статические, так и динамические входы могут быть прямыми или инверсными.

Входы называются статическими, если они имеют непосредственную связь с источником входных сигналов. Сигналом для управления статическим триггером с прямыми статическими входами является уровень лог. «1», а для управления триггером с инверсными входами – уровень лог «0».

Входы называются динамическими, если они соединены с источником входных сигналов через развязывающие цепи: магнитные, электронные или RC – цепи. Они реагируют только на перепады входных сигналов. Если срабатывание триггера происходит при изменении входного сигнала от «0» к «1», то входы называются прямыми, а если при изменении сигнала от «1» к «0», то – инверсными.

Входы и называются входами асинхронной установки триггера. Они предназначены для подачи приоритетных сигналов установки триггера в исходное состояние (0 или 1) в начале цикла работы, независимо от воздействия информационных сигналов, то есть в обход схемы управления.

Законы функционирования триггеров задаются таблицами переходов. В зависимости от набора управляющих входов, которыми могут быть оснащены триггеры, выделяют следующие основные типы триггеров: RS -триггеры, D -триггеры, T -триггеры, JK -триггеры.

 

RS-триггеры

Наибольшее применение находят триггеры с раздельным запуском, которые называются RS – триггерами. Их условное графическое обозначение приведено на рис. 1.3.

а) б)

Рис. 1.3. а) RS – триггеры с прямыми входами; б) RS – триггеры с инверсными статическими входами.

В простейшем RS – триггере информационные сигналы подаются непосредственно на входы S и R ячейки памяти.

Входы, на которые подаются запускающие импульсы, называются установочными. Буквой S (Set – установка) обозначают вход, на который подаётся сигнал, устанавливающий триггер в единичное состояние (, ). Буквой R (Reset – сброс) обозначают вход, на который подаётся сигнал сброса, переводящий триггер в состояние «0» (, ). Буквой обозначается прямой выход, а - инверсный.

Функционирование логических устройств последовательностного типа описывается таблицами переходов, которые отличаются от таблиц истинности тем, что в них учитываются только результативные переходы, когда изменение комбинации сигналов на входе приводит к изменению выходного состояния. Однако таблица переходов может быть сведена к таблице истинности, если состояние внутренних элементов памяти считать входными сигналами.

Полная таблица функционирования (таблица истинности) приведена в таб. 1.5, в которой предыдущее состояние триггера до подачи входных сигналов является одним из входных сигналов. Выходное состояние триггера после подачи входных сигналов обозначено символом .

Таблица 1.5

S	R			Режим работы
				хранение «0»
				хранение «1»
				подтверждение «0»
				сброс в «0»
				установка в «1»
				подтверждение «1»
			Ф	запрещенное состояние
			Ф	запрещенное состояние

 

Графы асинхроного RS -триггера представлен на рис. 1.4.

Рис. 1.4. Графы асинхронного RS -триггера.

 

Таблица истинности позволяет применить рассмотренную методику синтеза логических устройств комбинационного типа для синтеза устройств последовательностного типа, в том числе и RS – триггеров.

Для минимизации структурной формулы RS - триггера заполним карту Карно, приведённую на рис. 1.5.

 

|SR
			Ф
			Ф

Рис. 1.5. Карта Карно для минимизации структурной формулы RS – триггера.

 

В соответствии с теорией минимизации неопределённых логических функций, для определения прямого значения функции неопределённые значения карты Карно «Ф» (рис 1.5) заменим «1», а для определения инверсного значения – заменим «0». Для получения функции минимизация производится по нулям.

|SR
	0	0

 

|SR
			1
1				1

 

 

Минимизированные значения функций и на элементах основного базиса имеют вид:

Для реализации триггера на элементах ИЛИ-НЕ проинвертируем функцию :

Структурная схема триггера, полученная в соответствии с этим выражением, и его условно графическое обозначение (УГО) приведены на рисунке рис. 1. 6, а, б.

В структурной формуле установочные сигналы S и R представлены в прямом коде, следовательно исполнительными значениями сигналов являются уровни лог. «1», то есть триггер на элементах ИЛИ-НЕ имеет прямые статические входы.

Для реализации триггера на элементах И-НЕ дважды проинвертируем функцию :

 

Как следует из полученного выражения, исполнительными значениями сигналов здесь являются лог. «0», поэтому RS – триггер на элементах И-НЕ имеет инверсные статические входы. Структурная схема триггера и его условно графическое обозначение (УГО) приведены на рисунках рис. 1. 6, в, г.

Рис. 1. 6 RS – триггеры: а), б) – на логических элементах ИЛИ-НЕ,

в), г) – на логических элементах И-НЕ.

 

При разработке цифровых схем, в которые входят RS – триггеры, необходимо учитывать наличие запрещённого состояния входных сигналов для RS – триггеров на элементах ИЛИ-НЕ , а для RS – триггеров на элементах

И-НЕ . Условие нормального функционирования для обоих схем RS – триггеров можно записать в следующем виде: .

Если в разрабатываемой схеме такое сочетание входных сигналов в принципе возможно, то эту ситуацию необходимо исключить путём включения во входную цепь дополнительных логических элементов, или использовать другие типы триггеров, не имеющих запрещённого состояния.

Рассмотренные RS – триггеры являются асинхронными поскольку управляющие сигналы воздействуют на триггер непосредственно с началом своего появления на их входах.

На рис.1.7 представлены временные диаграммы асинхронного одноступенчатого RS–триггера со статическим управлением.

 

Рис.1.7 Временные диаграммы асинхронного RS–триггера.

 

Синхронные (синхронизируемые, стробируемые, тактируемые) RS-триггеры имеют на каждом входе дополнительные схемы совпадения импульса синхронизации С с информационными сигналами сброса и установки.

На рис. 1. 8 представлены функциональная схема синхронного RS -триггера на основе логических элементов И-НЕ (а) и его условное графическое изображение.

 

Рис. 1.8 Функциональная схема синхронного RS -триггера (а) и
его условное графическое изображение (б)

 

Таблица переходов синхронного RS -триггера.

 

Таблица 1.6

C	R	S	Qt+1	Режим
			Qt	Хранение
			Qt
			Qt
			Qt
			Qt	Хранение
				Установка "1"
				Установка "0"
			*	Запрещ. режим

 

Граф синхронного RS -триггера представлен соответственно на рис. 1.9

 

 

Рис. 1.9. Граф синхронного RS -триггера

 

В устройствах современной цифровой техники, для работы в схемах с синхронизацией режима, разработаны синхронные RS – триггеры, представленные на рис. 1.10.

 

Рис. 1. 10 Синхронные RS – триггеры: а) на элементах ИЛИ-НЕ,

в) на элементах И-НЕ и их УГО б) и г).

 

Синхронные RS – триггеры имеют три входа: S, R и С. Применение синхронизации не устраняет неопределённое состояние триггера, возникающее при одновременной подаче единичных сигналов на все три входа. Поэтому условием нормального функционирования является следующее неравенство: .

Кроме трёх основных входов, синхронные RS – триггеры снабжаются ещё входами асинхронной установки состояния триггера – и , которые называются входами асинхронной установки триггера. Они предназначены для подачи приоритетных сигналов установки триггера в исходное состояние (0 или 1) в начале цикла работы независимо от воздействия сигналов на входах S и R, то есть в обход схемы управления.

На рис.1.11 представлены временные диаграммы синхронного одноступенчатого RS–триггера со статическим управлением.

 

 

Рис. 1. 11 Временные диаграммы синхронного RS–триггера.