Выхованец В.С. Теория автоматов
Подождите немного. Документ загружается.
118
Пример:
Рассмотрим импульсный автоматный граф:
Преобразуем данный автомат в асинхронный автоматный граф.
Как видно из рисунка, каждое состояние (1 и 2) расщепляется на два состояния (10,
11 и 20,21). Причем, состояния 10 и 11 имеют один и тот же выходной знак 0, а состояния
20 и 21 – знак 1.
Из состояния 1 в состояние 2 имеется дуга
a
0
→
a
1
, следовательно, из состояния 10
имеется дуга в состояние 21, помеченная знаком
a
1
. И к состоянию 21 добавляем петлю,
помеченную знаком
a
1
.
Аналогично строятся остальные дуги.
Тема 5.5. Синхронные схемы
Синтез синхронных автоматов, свободных от критических состязаний.
Введение тактового сигнала позволяет исключить из рассмотрения переходные
процессы.
Структурная схема синхронного автомата имеет вид:
Тактовый сигнал
С выполняет функцию временного селектирования (импульсного
воздействия) сигналов элемента памяти
D в дискретные моменты времени, поэтому
необходимо, чтобы значения сигнала Q
+
были истинными только в моменты импульсного
воздействия тактового сигнала
C.
Запишем систему уравнений, которая описывает синхронный автомат:
( ) () ()()
( ) () ()()
( ) () ()
⎪
⎩
⎪
⎨
⎧
∪=+
=+
=+
+
Δ
+
Λ
dctqdctqtq
tatqtq
tatqtb
D
τ
δτ
λτ
,
,
2/11/0
a
0
→
a
1
a
0
→
a
1
a
1
→
a
0
a
1
→
a
0
10
11
0
20
21
1
a
1
a
1
a
0
a
0
a
1
a
1
a
0
a
0
Q
+
Δ
A
Λ
Q
B
D
C
119
Основным условием синтеза синхронных автоматов, свободных от критических
состязаний является то, что минимальное значение периода тактового сигнала
C должно
быть не меньше максимального времени переходного процесса. При этом
комбинационные схемы можно синтезировать и с критическими состязаниями и
использовать произвольное кодирование внутренних состояний автомата.
Синхронный элемент памяти.
В качестве синхронного элемента памяти могут быть использованы импульсные или
асинхронные потенциальные автоматы. Пример синтеза D триггера был рассмотрен ранее.
Поведение синхронного элемента памяти можно описать уравнением (
3):
dcQdcQQ ∪=
+
Если воспользоваться выражением (2)
xddxx ∪=∇ ;
То можно записать:
cQcQQ ∇∪∇=
+
(15)
Рассмотрим синхронный элемент памяти, реализующий выражение (15), в цепи
обратной связи
Очевидно, что значение выходного сигнала
Q определяется значением сигнала,
поступающего на вход
D, в момент изменения тактового сигнала C с 1 на 0 (
∇
c=1) и с 0 на
1 (
∇
c=1).
∇
c
Δ
D
С
T
τ
τ
р
=
τ
С
Q
+
A
Q
Апериодическая схема
СПИСОК ЛИТЕРАТУРЫ
1. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. – М.:
Радио и связь, 1988.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е
изд., перераб. и доп. – М.: Энергоатомиз-дат, 1988. – 480 с.: ил.
3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учебное пособие для
втузов. –
СПб.: Политехника, 1996. – 885 с.
4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.:
Наука, 1985.
5. Горбатов В.А. Основы дискретной математики: Учебное пособие для студентов
вузов. – М.: Высш.шк, 1986.
6. Брой М. Информматика. Теоретическая информатика, алгоритмы и структуры
данных, логическое программирование, объектная ориентация: В 4-х ч. Ч. 4. –
М.: Диалог-
МИФИ, 1998. – 224 с.
7. Братчиков И.Л. Синтаксис языков программирования. – М.: Наука, 1975. – 232 с.
121
Учебное издание
Выхованец Валерий Святославович
Теория автоматов
Учебное пособие для вузов
Редактор О. Д. Выхованец
Компьютерный набор и верстка Д. П. Епифанов, А.В. Булда, С.П. Алешков
Компьютерная графика Л. А. Стоянова