- •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-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
2.4.3. Модель совмещенного автомата (С-автомата)
Модель совмещенного автомата представляет собой комбинацию моделей Мили и Мура. Совмещенный автомат позволяет одновременно формировать выходные сигналы как "короткие", так и "длинные".
Абстрактный С-автомат - математическая модель дискретного устройства, для которого заданы следующие параметры:
Q={q1,...,qn} |
множество состояний; |
X={x1,...,xm} |
входной алфавит; |
Y={y1,...,yg} |
выходной алфавит типа 1; |
U={u1,...,uf} |
выходной алфавит типа 2; |
δ:Q><X→Q |
функция переходов, реализующая |
|
отображение Dδ Q><X в Q; |
λ1:Q><X→Y |
функция выходов, реализующая |
|
отображение Dλ1 Q><X на Y; |
λ2:Q→U |
функция выходов, реализующая |
q0 Q |
отображение Dλ2 Q на U; |
начальное состояние автомата. |
Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из выходных алфавитов Y и U (рис. 2.2).
Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов λ1 и λ2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:
q (t+1) = |
δ (q(t), |
|
y (t) = λ1 |
(q(t), x(t)); |
(2.6) |
u(t) = λ2 (q(t)). |
|
|
|
26 |
|
Выходной сигнал u=λ2(qs) формируется все время, пока автомат находится в состоянии qs. Выходной сигнал y=λ1(qs, xn) выдается во время действия входного сигнала xn при нахождении автомата в состоянии qs. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура, и наоборот.
U={u1,...,uf}
X={x1,..., xm}
Q={q1,....,qn} |
Y={y1,...,yg} |
|
Рис. 2.2. Модель совмещенного автомата с одним входом и двумя выходами (С-автомат)
2.4.4. Модель микропрограммного автомата
Принцип функционирования микропрограммного автомата (МП-автомат) удобно рассматривать во взаимодействии с управляемыми им функциональными блоками (ФБ) [5]. При этом среди ФБ целесообразно выделить два типа блоков: операторные (ОФБ) и логические (ЛФБ). МА-автомат вырабатывает последовательность выходных сигналов (воздействий) zai и zpj, которые управляют работой ОФБ и ЛФБ.
При воздействии на ЛФБj им вырабатывается одно из двух возможных значений проверяемого параметра pj, которое поступает на вход микропрограммного автомата. Следовательно, на вход pj воздействие может поступить лишь в том случае, если имеется воздействие на выходе zpj. Поэтому все входы МП-автомата разделяют на две группы: внешние r1,…,rk
27
и внутренние p1,…,pm. Выходы zp1,…,zpm можно назвать внут- |
||
ренними выходами, а za1,…,zak - внешними. |
|
|
Z p1 |
Z a1 |
ОФБ1 |
|
||
r1 |
|
|
Z pm |
Z ak |
|
rk |
|
ОФБk |
МП |
Z p1 |
|
|
ЛФБ1 |
|
|
|
|
p1 |
Z pm |
|
|
ЛФБm |
|
pm |
|
|
Рис. 2.3. Структурное представление микропрограммного |
||
автомата |
|
|
Наличие зависимости поступления воздействий на внутренние входы МП-автомата от его внутренних выходных воздействий является одной из основных особенностей МПавтомата. Второй особенностью является то, что при неизменном состоянии внешнего входа автомат вырабатывает последовательность сигналов на основных выходах.
Примем, что Q={q1,...,qn} множество внутренних состояний МП-автомата. Тогда его закон функционирования можно задать одним из следующих способов:
q (t + 1) = δ ((q(t), r(t), p(t)), |
|
Z a(t) = λ1((q(t), r(t), p(t)), |
(2.7) |
Z p(t) = λ2((q(t), r(t), p(t)), |
|
или |
|
q (t + 1) = δ ((q(t), r(t), p(t)), |
|
Z a(t) = λ1((q(t)), |
(2.8) |
Z p(t) = λ2((q(t)). |
|
28 |
|