На рисунке 11.16 представлено условное графическое обозначение демультиплексора.

A0

yk

Am

Рис. 11.16. Условное графическое обозначение демультиплексора

12. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ С ПАМЯТЬЮ И ИХ СИНТЕЗ

В [29] отмечалось, что структура первого уровня абстрактных конечных автоматов, функционирование которых задается моделями Мили или Мура, представляется композицией двух функциональных частей: логического преобразователя (ЛП) и блока памяти (БП) так, как представлено на рис. 12.1.

Q(t)

Q(t+1)

БП

S

Рис. 12.1. Структура первого уровня абстрактных конечных автоматов

146

где

X(t) - множество символов входного алфавита (входной алфавит);

Y(t) - множество символов выходного алфавита (выходной алфавит);

Q(t) - множество состояний автомата в момент времени t (алфавит состояний);

Q(t+1) - множество состояний автомата в момент времени t+1 (функция возбуждения блока памяти);

S - символ (сигнал) синхронизации, используемый в синхронных автоматах.

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

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

12.1. Понятие функционально полной системы элементарных автоматов

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

147

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

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

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

Автомат обладает полной системой переходов, если для

каждой пары его внутренних состояний zi и zj найдётся хотя бы один сигнал xk, который переведёт автомат из состояния zi

вzj .

Автомат обладает полной системой выходов, если для каждого zi вырабатывается сигнал yi, отличный от всех других выходных сигналов, соответствующий другим состояниям автомата.

Среди всех возможных автоматов с полной системой переходов и выходов элементарными полными автоматами являются такие, которые имеют всего два устойчивых состояния и два выходных сигнала. Такие элементарные автоматы называют элементарными автоматами Мура или триггерами. Граф элементарного автомата Мура представлен на рис. 12.2.

148

Рис. 12.2. Граф элементарного автомата Мура

где Z1 – первое состояние автомата; Z2 – первое состояние автомата;

X1 – входной сигнал, переводящий автомат из состояния Z1 в состояние Z2;

X2 – входной сигнал, переводящий автомат из состояния Z2 в состояние Z1;

Y1 – выходной сигнал, формируемый автоматом в состоянии Z1;

Y2 – выходной сигнал, формируемый автоматом в состоянии Z2.

Как видно из рис.12.2 элементарный полный автомат Мура является асинхронным, так как каждое его состояние является устойчивым.

12.2. Разновидности триггеров

Разновидности триггеров, используемых в практической цифровой схемотехнике, иллюстрирует рис. 12.3.

Рассмотрим перечисленные разновидности триггеров

[25, 27, 30].

149

Тпо способу

Рис. 12.3. Разновидности триггеров

RS-триггеры – триггеры с двумя установочными входами, при подаче активного сигнала на вход R (от англ. Reset – сбрасывать) происходит установка триггера в 0, а на вход S (от англ. Set - устанавливать) – установка триггера в 1.

T-триггеры – триггеры с одним счетным входом (от англ. Time - время), состояние которых изменяется на инверсное с приходом каждого импульса на его счетный вход.

D-триггеры – триггеры, осуществляющие прием информации по одному входу D (от англ. Delay - задержка), поэтому их еще называют триггерами задержки.

JKтриггеры – универсальные триггеры, при подаче активного сигнала на вход J (от англ. Jump - прыгать) происходит установка триггера в 1; а на вход K (от англ. Keep – хранить) – установка триггера в 0; при J=K=1 осуществляется поочерёдная установка триггера в 0 и в 1.

150

Особенностью комбинированных триггеров является то, что наряду с наличием у них синхронно управляемых входов, присутствуют также и входы асинхронной установки (S и R) триггеров в единичное “1” и нулевое “0” состояния. Входы асинхронной установки необходимы для приведения триггеров в некоторые исходные (начальные) состояния, которые в совокупности соответствуют начальному состоянию синтезируемого синхронного управляющего автомата. Сигнал, подаваемый на входы асинхронной установки триггеров для приведения их в начальные состояния, принято называть сигналом сброса (Reset) или начальной установки (Н.У.). Сигнал начальной установки должен воздействовать только на один из асинхронных входов (S или R) каждого триггера. Более подробно комбинированные триггерные схемы и их разновидности рассмотрены в [30].

Асинхронные триггеры – это триггеры, которые изменяют свое состояние непосредственно в момент появления соответствующего информационного сигнала.

Синхронные триггеры – это триггеры, реагирующие на информационные сигналы только после подачи соответствующего сигнала на вход синхронизации С (от англ. Clock - часы). Вход С обозначают еще терминами «такт» и «строб».

Одноступенчатые (однотактные) триггеры – тригге-

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

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

Триггеры, управляемые статическими входами – это триггеры, управляемые потенциалами (уровнями напряжения

0 или 1).

Триггеры, управляемые динамическими входами – это триггеры, управляемые перепадами потенциалов (фронтом или срезом сигнала).

151