- •1. СТАНОВЛЕНИЕ ТЕОРИИ АВТОМАТОВ
- •1.1. Взаимосвязь теории автоматов и других
- •1.2. Подходы к определению конечного автомата
- •1.3. Сущность метода "черного ящика"
- •1.4. Основные задачи теории автоматов
- •2. ФОРМАЛЬНАЯ КЛАССИФИКАЦИЯ АБСТРАКТНЫХ АВТОМАТОВ И ИХ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
- •2.1. Словесные определения автоматов
- •2.2. Формальное определение абстрактного автомата
- •2.3. Формальная классификация автоматов
- •2.4. Математические модели автоматов
- •2.4.1. Модель Мили
- •2.4.2. Модель Мура
- •2.4.3. Модель совмещенного автомата (С-автомата)
- •2.4.4. Модель микропрограммного автомата
- •3. СТРУКТУРНЫЕ МОДЕЛИ ПЕРВОГО УРОВНЯ АБСТРАКТНЫХ АВТОМАТОВ
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3. Структурная модель С-автомата
- •3.4. Структурная модель микропрограммного автомата
- •4. СПОСОБЫ ЗАДАНИЯ АБСТРАКТНЫХ И СТРУКТУРНЫХ АВТОМАТОВ
- •4.1. Начальные языки
- •4.1.1. Язык регулярных выражений алгебры событий
- •4.1.2. Язык логических схем
- •4.1.3. Язык граф – схем алгоритмов
- •4.2. Автоматные языки
- •4.2.1. Таблицы переходов и выходов
- •4.2.2. Матрицы переходов и выходов
- •4.2.3. Граф автомата
- •4.3.2. Язык временных диаграмм
- •5. Минимизация абстрактных автоматов
- •6. МАТЕМАТИЧЕСКИЕ ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •6.1. Формальное определение алгебры логики
- •6.2. Аксиомы, теоремы и законы алгебры логики
- •6.2.1. Аксиомы алгебры логики
- •6.2.2. Теоремы алгебры логики
- •6.2.3. Законы алгебры логики
- •6.3. Основные понятия и определения
- •6.4. Формы представления логических функций
- •6.4.1. Словесная форма представления логических функций
- •6.4.2. Табличная форма представления логических функций
- •6.4.3. Аналитическая форма представления логических функций
- •7. Минимизация логических функций
- •7.1. Методы минимизации логических функций на основе прямых аналитических преобразований СДНФ
- •7.2. Метод испытания импликант
- •7.3. Визуальные методы минимизации логических функций
- •7.3.2. Метод минимизации частично определенных логических функций с помощью карт Карно
- •7.4. Машинно-ориентированные методы минимизации логических функций
- •7.5. Групповая минимизация системы логических функций
- •8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ
- •9. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ
- •9.1. Программируемые логические матрицы
- •10. КОНЕЧНЫЕ ФУНКЦИОНАЛЬНЫЕ ПРЕОБРАЗОВАТЕЛИ
- •11. СИНТЕЗ И АНАЛИЗ ТИПОВЫХ КОМБИНАЦИОННЫХ АВТОМАТОВ
- •11.1. Шифратор (coder) и его синтез
- •11.2. Дешифратор и его синтез
- •11.3. Мультиплексор и его синтез
- •11.4. Синтез демультиплексора (распределителя)
- •12. Элементарные автоматы с памятью и их синтез
- •12.1. Понятие функционально полной системы элементарных автоматов
- •12.2. Разновидности триггеров
- •12.3. Обобщённая характеристика триггеров
- •12.4. Синтез однотактного асинхронного RS-триггера
- •12.4.1. Синхронный однотактный RS-триггер
- •12.5. Синхронный однотактный D-триггер
- •12.6.1. Принцип построения двухтактного триггера
- •12.6.2. Однотактный Т-триггер
- •12.6.3. Двухтактные Т-триггеры
- •12.7. Двухтактный JK-триггер
- •12.8. Двухтактные RS-триггеры и D-триггеры
- •Рис. 12.28. Синхронный двухтактный RS-триггер
- •Рис. 12.30. УГО синхронного двухтактного RS-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
На рисунке 11.16 представлено условное графическое обозначение демультиплексора.
|
y0 |
x |
|
|
DMX |
A0
yk
Am
Рис. 11.16. Условное графическое обозначение демультиплексора
12. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ С ПАМЯТЬЮ И ИХ СИНТЕЗ
В [29] отмечалось, что структура первого уровня абстрактных конечных автоматов, функционирование которых задается моделями Мили или Мура, представляется композицией двух функциональных частей: логического преобразователя (ЛП) и блока памяти (БП) так, как представлено на рис. 12.1.
X(t) |
ЛП |
Y(t) |
|
|
|
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
Y1 |
Y2 |
|
X1 |
Z1 |
Z2 |
X2 |
X2 |
|
Рис. 12.2. Граф элементарного автомата Мура
где Z1 – первое состояние автомата; Z2 – первое состояние автомата;
X1 – входной сигнал, переводящий автомат из состояния Z1 в состояние Z2;
X2 – входной сигнал, переводящий автомат из состояния Z2 в состояние Z1;
Y1 – выходной сигнал, формируемый автоматом в состоянии Z1;
Y2 – выходной сигнал, формируемый автоматом в состоянии Z2.
Как видно из рис.12.2 элементарный полный автомат Мура является асинхронным, так как каждое его состояние является устойчивым.
12.2. Разновидности триггеров
Разновидности триггеров, используемых в практической цифровой схемотехнике, иллюстрирует рис. 12.3.
Рассмотрим перечисленные разновидности триггеров
[25, 27, 30].
149
|
RS |
|
JK |
|
T |
|
D |
|
|
|
||||
по логике |
|
|
|
|
комбинированные |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
работы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тпо способу
р |
записи |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
асинхронные |
|
|
|
синхронные |
|
|
|||||||||
и |
информации |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
г |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
г |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
е |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
р |
по внутренней |
|
|
одноступенчатые |
|
двухступенчатые |
|
||||||||||
|
|
(однотактные) |
|
|
(двухтактные) |
|
|||||||||||
ы |
организации |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
по управлению |
(статическое) |
|
|
(динамическое) |
||||||||||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|||||||||||
|
|
уровнем |
(0 или 1) |
|
|
перепадом (срезом или фронтом) |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 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