Проектирование управляющих автоматов. Управляющий автомат с жесткой логикой

1.

Проектирование
управляющих
автоматов.
Управляющий автомат с
жесткой логикой

2.

Синтез управляющих автоматов (УА).
Управляющий автомат с жесткой логикой.
1
Для УА входными
являются
осведомительные
сигналы, а
выходными –
управляющие (для ОА
– наоборот).

3.

При синтезе операционного автомата используется содержательная ГСА (для ОА
важно содержание микроопераций и осведомительных сигналов)
Микропрограмма
подсчета числа единиц
в n-разрядном слове А
Начало
y0 А(1:n):=T(1:n)
y1 C(1:m):=00...0
x1
A(1:n)=00...0
0
1
A1
y2 C(1:m):=C(1:m)+1
Y2
y3 А(1:n):=A(2:n).0
Конец
m = log2 n
Y1
1
x2
0
y3 А(1:n):=A(2:n).0 Y3
2

4.

Была получена следующая структурная схема
операционного устройства:
Затем по ней была разработана принципиальная схема операционного автомата для
n=8.

5.

Принципиальная схема ОУ
?
18

6.

Для синтеза управляющего автомата (УА) содержание микроопераций и
3
осведомительных сигналов не важно. Важно знать в какие моменты времени при
каких условиях (значениях осведомительных сигналов) какие управляющие сигналы
должны быть выданы.
Вид ГСА для синтеза УА:

7.

ГСА описывает работу
последовательностной
схемы – автомата, который
меняет свое состояние в
каждом такте работы под
воздействием
осведомительных сигналов.
Состояниями будем считать
операторные вершины ГСА.
В каждом состоянии автомат
вырабатывает
определенные управляющие
сигналы. Построим по ГСА
граф, описывающий работу
автомата. Сначала
рассмотрим переходы из
состояний S0 и S1.
Автомат МУРА
Выходные сигналы зависят только от
состояний (не зависят от входных
сигналов автомата).
4

8.

Вспомним…
Автомат Мура:
Sслед f ( Sтек , x1 , x2 ,..., xn );
yi f ( Sтек );
Автомат Мили:
Sслед f ( Sтек , x1 , x2 ,..., xn );
yi f ( Sтек , x1 , x2 ,..., xn );

9.

5
Переходы из S2.

10.

6
Переходы из S3.

11.

Итак, ГСА по сути является графом состояний
управляющего автомата. Каждую
операторную вершину ГСА считаем
состоянием автомата. В каждом такте
работы автомата происходит смена
состояния автомата под воздействием
входных сигналов {xi}. В каждом состоянии
(кроме начального) автомат выдает
соответствующее этому состоянию
множество выходных сигналов {yj}.
7
Т.к. состояний
всего четыре,
номер
состояния
можно
закодировать
двумя
двоичными
переменными
z 1 и z 2.

12.

Для хранения номера текущего состояния автомат должен быть снабжен
запоминающими элементами. Для перехода в следующее состояние –
комбинационными схемами, меняющими уровни сигналов на входах
запоминающих элементов. Для выработки выходных сигналов {yj} –
соответствующими комбинационными схемами. Такая схема называется
последовательностной (в отличие от комбинационной).
8
Возьмем для нашего примера в качестве запоминающих
элементов D-триггеры. Комбинационная схема должна
реализовывать следующие функции:
yi fi ( z1 , z2 );
D j f j ( z1 , z2 , x1 , x2 ).
Значения управляющих сигналов y0,
y1, y2, y3 зависят только от номера
текущего состояния, который
задается переменными z1 и z2.
Значения функций возбуждения
входов D1 и D2, переключающих
триггеры в следующее состояние,
зависят от номера текущего
состояния и значений входных
сигналов x1 и x2. По каждому
синхроимпульсу автомат
переключается в следующее
состояние.

13.

Обобщенная схема управляющего автомата с
жесткой логикой
ЗЧ может быть
реализована на
отдельных
триггерах (D или
JK) или на
микросхеме
регистра.
i = 1,2,…, n1, j = 1,2,…, n2, k = 1,2,…, n3, m = 1,2,…, n4,
где n1 – число осведомительных сигналов в микропрограмме,
n2 – число управляющих сигналов в микропрограмме,
n3 – число функций возбуждения входов ЗЧ (число входов
запоминающих элементов, используемых для переключения автомата в
следующее состояние),
n4 – число булевых переменных, кодирующих состояние автомата.
n4= log2 N , где N – число состояний автомата.
9

14.

Этапы синтеза УА с жесткой логикой
1. Разметка ГСА .
Символами состояний Si обозначаются операторные вершины ГСА. Начальная
и конечная вершины обозначаются символом S0 (считаем, что после подачи сигнала
запуска B (например, с кнопки) автомат работает в цикле до выключения сигнала
запуска.
Примечание: граф
переходов можно не
строить (особенно если
ГСА большая), т.к. вся
информация о переходах
автомата содержится в
ГСА (по сути граф-схема
алгоритма и является
графом, описывающим
работу управляющего
автомата).
Как было показано выше
это – разметка для
автомата Мура.
10

15.

Виды путей в ГСА:
1) S i /{ yi } K j S m /{ ym };
2) S i /{ yi } K j S0 /
K j − некоторая
конъюнкция
входных
сигналов,
приводящая к
переходу из
состояния Si в
состояние Sm .
1
2
K j x1 x2
K j x1

16.

2. Построение структурной таблицы переходов УА
11
В – входной
сигнал,
инициирующий работу
УА (кнопка).
На этот сигнал
домножаются все
переходы из
S0 .
Если кнопка В
выключена,
автомат не
работает
(никуда не
переходит).

17.

18.

12
Обязательными отметками помечаются строки таблицы переходов для
последующего составления функций возбуждения входов триггеров.
При расставлении отметок D анализируется только код состояния
перехода. Отметки ставятся для триггеров, выходы которых в новом
состоянии должны выдавать “1”.
При реализации запоминающей части на JK-триггерах анализируются
и код исходного состояния и код состояния перехода. Отметка Ji ставится в
тех строках таблицы переходов, где i-ый триггер переходит из “0” в “1”, а
отметка Кi, где i-ый триггер переходит из “1” в “0”.
Проверить, все ли пути из некоторого состояния отражены в таблице
переходов, можно следующим образом: дизъюнкция конъюнкций,
записанных в столбце «Входной сигнал» для строк, отражающих переходы
из этого состояния, должна быть равна 1 (переход происходит в любом
случае!).

19.

3. Получение функций возбуждения входов триггеров и выходных сигналов.
13.а
Функция возбуждения входа равна дизъюнкции конъюнкций, соответствующих
строкам таблицы переходов, отмеченным соответствующей обязательной
отметкой.
Конъюнкция, соответствующая строке таблицы переходов – это код исходного
состояния, домноженный на входной сигнал. Например, первой строке таблицы
переходов соответствует конъюнкция
z1 z2 B.
Коды состояний:
S0 00 z1 z2 ; S1 01 z1 z2 ; S2 10 z1 z2 ; S3 11 z1 z2 .

20.

13.б
Коды состояний:
S0 00 z1 z2 ; S1 01 z1 z2 ; S2 10 z1 z2 ; S3 11 z1 z2 .
Функции для построения ЗЧ на D-триггерах:
D1 z1 z2 x1 x2 z1 z2 x1 x2 z1 z2 x1 x2 z1 z2 x1 x2 z1 z2 x1 x2
z1 z2 x1 x2 z1 z2 x1 x2 x1 ( z1 z2 z1 z2 z1 z2 ) x1 ( z1 z2 )
D2 z1 z2 B z1 z2 x1 x2 z1 z2 x1 x2 z1 z2 x1 x2
z1 z2 B x1 x2 ( z1 z2 z1 z2 z1 z2 ) z1 z2 B x2 x1 ( z1 z2 )

21.

Функции для построения запоминающей части на JKтриггерах:
14
J1 z1 z2 x1 x2 z1 z2 x1 x2 z1 z2 x1
J 2 z1 z2 B z1 z2 x1 x2
K1 z1 z2 x1 z1 z2 x1 z1 z2 x1 x2 z1 x1 z1 z2 ( x1 x1 x2 )
z1 x1 z1 z2 ( x1 x2 )
K 2 z1 z2 x1 x2 z1 z2 x1 z1 z2 x1 z1 z2 x1 x2 z1 z2 ( x1 x2 )
z1 z2 ( x1 x2 ) z2 ( x1 x2 )

22.

Выходные сигналы автомата зависят только от состояния, в котором находится
автомат. Такой автомат называется автоматом Мура [1]. Функции для выходных
сигналов автомата можно получить прямо из ГСА:
15
y0 y1 z1 z2 ;
y2 z1 z2 ;
y3 z1 z2 z1 z2 z1.
Преимущество
автомата Мура –
простые функции
выходных сигналов
(зависят только от
состояния, в котором
находится автомат).

23.

4. Построение
принципиальной схемы
УА.
Если логика
работы
автомата
задается схемой,
построенной на
логических и
запоминающих
элементах, то
изменить эту
логику, не меняя
схему, нельзя (в
этом смысле она
жесткая!).
16

24.

Проектируем для рассматриваемой микропрограммы
Автомат МИЛИ
S0
Sслед f ( Sтек , x1 , x2 ,..., xn );
yi f ( Sтек , x1 , x2 ,..., xn );
S1
В отличие от автомата Мура, отметки
состояний ставятся не возле
операторных вершин, а на дугах ГСА.
Правила расстановки состояний:
1) Выход начальной вершины и вход
конечной вершины отмечается
состоянием S0.
S0
2) Символом состояния Si отмечается
вход вершины, следующей за
операторной.
3) Вход вершины может быть отмечен
только одним символом состояния.

25.

Автомат МИЛИ
Для
кодирования
состояния
нужен 1 бит.
При такой разметке в одном и том же
состоянии автомат может выдавать
различные выходные сигналы (y) в
зависимости от конкретных значений
входных сигналов (х):
yi f ( Sтек , x1 , x2 ,..., xn );
Автомат Мили имеет, как правило,
меньше состояний, чем автомат
Мура, построенный по той же ГСА.
Хорошо, если уменьшение числа
состояний приводит к уменьшению
числа внутренних переменных,
кодирующих состояние (как в нашем
примере).
Виды путей в ГСА
1) S i K j { yn } S m ;
2) S i K j S 0

26.

Таблица переходов
В связи с сокращением числа состояний
сократилось и число строк в таблице переходов
y0 z B ;
y1 z B y0 ;
y2 z x1 x2 x2 y3 ;
y3 z x1 x2 z x1 x2 z x1
D z B z x1 x2 z x1 x2 y0 y 3 ;
J z B y0 ; K z x1 .

27.

Схема управляющего автомата (модель Мили)

28.

Автомат Мура
Автомат Мили

29.

Методы уменьшения сложности УА с жесткой
логикой
Сложность схемы оценивается по числу входов логических и запоминающих
элементов, из которых она состоит.
1. Выделение узлов в ГСА
Узлом называется вход условной вершины, если в нее
ведет не менее двух путей, и хотя бы один из них проходит
через условную вершину.
Если в качестве узла Qi выделяется вход условной
вершины, уже отмеченный состоянием aj , то отметка
узла ставится за отметкой состояния ближе ко входу
условной вершины.
Применение аппарата узлов позволяет выделить общие
части в электрической схеме на этапе составления
структурной таблицы переходов автомата.

30.

S0
Пусть будет автомат
Мили.
Сделаем разметку
состояний.
S1
S2
S3
S0

31.

При построении путей из состояния в состояние нужно
иметь в виду, что на пути в состояние обязательно
должна быть операторная вершина (y),
Исключение – путь в S0.
Как много
трудных путей
из-за обилия
условий,
следующих одно
за другим!
Это путь из S2
в S2 , а не в S1 !
Граф состояний УА

32.

Число переходов:
из S0 – 2; из S1 – 3;
из S2 – 5; из S3 – 2.
Всего 12 строк в
таблице переходов.
Граф без узлов

33.

Граф с узлами
Число переходов: из S0 – 2; из S1 – 1;
из S2 – 2; из S3 – 1; Q1 – 2; из Q2 – 2.
Всего 10 строк в таблице переходов.

34.

Сравнение
12 строк в таблице переходов,
повторение операционных
микрокоманд на разных переходах,
более сложные конъюнкции входных
сигналов.
10 строк в таблице переходов,
отсутствие повторения операционных
микрокоманд на разных переходах,
простые конъюнкции входных
сигналов.

35.

Виды путей в ГСА:
1) S i K j { yn } S m ;
2) S i K j S 0 ;
3) S i K j Qm ;
4) Qm K j { yn } S k ;
5) Qm K j S0 ;
6) Qm K j Qn .
На пути в состояние (1, 4) обязательно
должна быть операторная вершина (y),
Исключение – путь в S0 (2,5).
Путь из состояния в узел или из узла в узел – это только часть (причем,
не заключительная) пути из состояния в состояние, поэтому на таких
путях (3,6) управляющие сигналы (y) не вырабатываются.
Внимание! Узлы – условные точки на ГСА. Они как бы разбивают путь из состояния в
состояние на несколько частей. На переход в узел отдельный такт не тратится!
Такт занимает целый переход из состояния в состояние.

36.

Структурная таблица переходов УА с узлами
?

37.

Расстановка обязательных отметок
при переходе из узла в состояние
Нужно рассматривать полный путь из состояния в состояние через узел (узлы).

38.

На основании таблицы переходов получены функции
узлов F(Q1), F(Q2), функции возбуждения входов
запоминающих элементов управляющего автомата D1,
D2, функции выходных сигналов управляющего автомата
y1, y2, y3, y4.
F Q z z
zz x;
D z z x B F Q x
1
1
1
1
2
2
1
2
3
1
1
Y x B z z ;
Y F Q x z z B ;
1
3
1
1
1
2
2
1
2
F Q z z x z z F Q x
D z z B F Q x ;
1
2
2
;
2
1
2
3
2
1
2
2
1
2
;
1
F Q x F Q x z z x B
Y F Q x .
Y
2
4
1
1
2
2
1
1
2
2
Максимальная глубина схемы УА без узлов (наибольшее количество ЛЭ, через
которые проходит сигнал от входа к выходу) равна 2 (каждая функция – это
дизъюнкция конъюнкций).
Посчитаем максимальную глубину схемы УА с узлами:
F(Q1) – 2 (дизъюнкция конъюнкций);
F(Q2) – 4;
D2, y2 – 6 (максимальная глубина).
1
;

39.

Схема УА
с узлами
Недостаток:
выделение узлов увеличивает
глубину схемы, а, значит, и
время срабатывания УА!
Достоинства применения
узлов:
1) за счет выделения общих
частей в функциях возбуждения
входов триггеров и выходных
сигналов уменьшается число
входов логических элементов
(сложность схемы);
2) Сокращение времени
проектирования УА:
общие части не надо
выделять «вручную»;
число строк в таблице
переходов, как правило,
сокращается за счет выделения
узлов.

40.

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

41.

Построение УА на
распределителе сигналов
(РС)

42.

Распределитель сигналов (РС) – это операционный
элемент, вырабатывающий выходные сигналы
0 , 1 , ... , n 1 , принимающие единичные
, 1 , ... , n 1
значения в моменты времени
0
соответственно.
t t
t
Специфика применения распределителей сигналов
состоит в том, что они обычно используются для
построения управляющих, а не операционных
автоматов. На РС удобно строить запоминающую
часть автомата, работающего по линейной или
легко линеаризуемой микропрограмме. При этом с
выходов i (i 0, 1, 2,..., n 1) РС снимаются
сигналы состояний автомата. Выход n 1 может
использоваться для перевода (сброса) РС в
состояние 0 . РС может быть переведен в
состояние 0 и специальным управляющим
сигналом y 0 .
Граф переходов
распределителя
Состояния РС сменяются последовательно
(единица переходит на очередной выход) по
синхросигналу С.

43.

n 2k
Примечание. Если
, то после значения
нулевое значение на счетчике устанавливается
автоматически.

44.

Граф переходов «неуправляемого» РС
Граф переходов управляемого РС (пример)
x=1
0
1
2
3
Управляемый РС в зависимости
от значения некоторого
осведомительного сигнала
может изменять естественную
последовательность смены
состояний (тактов).

45.

n = 4 = 22
x=1
0
1
2
Если число состояний
k
РС n 2 , то после
значения (n 1)
нулевое значение на
счетчике
устанавливается
автоматически.
3

46.

47.

Элементный базис – микросхемы К155ИЕ7 (счетчик), К155ИД4 (сдвоенный дешифратордемультиплексор).
Для реализации РС используется режим 3x8 дешифратора К155ИД4. По очередному
синхросигналу код на счетчике К155ИЕ7 увеличивается на 1, а на соответствующем
выходе дешифратора появляется уровень логического нуля, т.е. распределитель
переходит в следующее состояние i . Объясните нумерацию состояний на выходах
дешифратора.
Если осведомительный сигнал х, анализируемый в такте 3, равен нулю, то за
состоянием 3 следует состояние 4 (РС следует по большому циклу). Если
осведомительный сигнал х, равен 1, то после состояния 3 РС должен вернуться в
состояние 1 (РС следует по малому циклу). Для осуществления такого перехода
используется режим параллельной загрузки счетчика. На входах параллельной загрузки
( D1 D4) фиксируется код состояния
1 . Сигнал 1 3 x c , поданный на вход PE ,
переводит счетчик в режим параллельной загрузки.

48.

49.

50.

В качестве запоминающей части УА,
реализующего линейную микропрограмму,
очень удобно использовать распределитель
сигналов. РС будет осуществлять смену
состояний УА.
А если в микропрограмме есть
разветвления?
За разветвления придется платить. Чем?
Временем или деньгами (усложнением
схемы УА).
Если разветвлений немного – ничего
страшного;-)

51.

Пример ГСА с разветвлением и циклом
Как упростить
схему РС?
x1=0
x1
2
Из такта 1 РС
всегда переходит в
такт 2.
Если x1=1, в такте
2 вырабатывается
y3, иначе такт 2
будет «пустым»
За разветвление
можно
заплатить не
аппаратным
усложнением
схемы РС, а
временем.
С циклом это
не получится!
Только
аппаратная
реализация!

52.

Получены следующие функции для выходных сигналов
управляющего автомата y1, y2, y3, y4 , а также функции
переключения распределителя в нулевое состояние (такт)
0 и в третье состояние 3 :
y ;
y ;
y x
y ;
1
1
3
0= 6
Мы произвели
линеаризацию
микропрограммы
за счет
добавления
пустого такта и
аппаратной
реализации цикла
при помощи
сигнала 3
3
2
1
3
2
4
4
0
6
5
1
3
;
; Используется
шестой выход РС.
задержать,
x .Нужно
чтобы не стерлось
3
4
2
состояние 4 (успел
отработать y4) !

53.

Схема УА
Нужно
раскрыть
схему РС – лр1!
Счетчик лучше
строить на JKтриггерах (мы уже
не ограничены
возможностями
макета).
Задержать!

54.

Пример с
разветвляющейся МП

55.

2 3
4 х3Переобозначить!
1
0
0 1
0
0
0
1
1
2
3 4
5
Каждой микрокоманде сопоставляется такт, номер которого на 1 больше
максимального номера такта предшествующей микрокоманды.
При синтезе УА на РС входные сигналы, приходящие в соответствующих тактах
запоминаются на триггерах.

56.

Каждой микрокоманде Yi сопоставляем путь Xi :
X 1 1;
X 2 X 1 x1 x1;
X 3 X 2 x1;
X 4 X 3 X 1 x1 x2 x1 x1 x2 x1 x2 ;
X 5 X 1 x1 x2 x1 x2 ;
X 6 X 5 X 4 x3 x1 x2 x3 ( x1 x2 )
x1 x2 x3 x1 x2 x1 x2 x3 ;
X К X 6 X 4 x3 x1 x2 x3 x3 ( x1 x2 )
x3 x1 x2 x3 x1 x2 1 !

57.

Y1 1 X 1 1
|
y1 , y3
Y2 2 X 2 2 x1
|
y2
Y3 3 X 3 3 x1
|
y4
Y4 4 X 4 4 ( x1 x2 ) |
y2 , y3 , y5
Y5 2 X 5 2 x1 x2
|
y4
Y6 5 X 6 5 ( x3 x1 x2 ) |
y5
Лучше Y5 вырабатывать в третьем такте, тогда
y4 Y3 Y5 3 ( x1 x2 )
− возможность упрощения
схемы УА.

58.

Y6 5 ( x3 x1 x2 )
Если значение одного из сигналов, например, x2, было изменено
микрокомандой Y5, то Y6 может не выработаться. Поэтому
осведомительные сигналы xi нужно запоминать на триггерах в
тех тактах, где они анализируются:

59.

Синтез УА на РС для циклических микропрограмм
2 3
4
Если времени жалко, эту ветвь можно также
реализовать аппаратно
Реализуем
аппаратно!

60.

Функционирование ОУ во времени.
16.б
Промежуток времени, достаточный для
реализации операционным устройством любой
микрокоманды, называется тактом. Другими
словами, такт – это период синхросерии С,
обеспечивающей стабильную работу ОУ. Так как
любое ОУ состоит из управляющего устройства
(управляющего автомата) и обрабатывающего
блока (операционного автомата), такт
операционного устройства в случае
последовательной работы УА и ОА
определяется формулой:
ТОУ = TУА + ТОА.

61.

ТОУ = TУА + ТОА.
16.в
ТУА время срабатывания УА (определяется максимальной глубиной схемы УА). Под
глубиной схемы понимается количество логических и запоминающих элементов,
через которые проходит электрический сигнал от входа схемы к выходу. Время
распространения сигнала от входа к выходу равно сумме задержек логических и
запоминающих элементов (справочные данные), через которые проходит сигнал.
ТОА время срабатывания ОА, определяемое по времени исполнения самой
длительной микрооперации. Самой длительной микрооперацией, скорее всего, будет
микрооперация сложения многоразрядных слов на двоичном сумматоре (время
суммирования зависит от способа распространения переноса в двоичном сумматоре).
Поскольку ОА после выполнения микроопераций вырабатывает осведомительные
сигналы, время срабатывания самой глубокой схемы вычисления осведомительного
сигнала также надо учесть при вычислении TОА.
Расчетное значение тактовой частоты определяется величиной
F=1/TОУ.
Рабочая частота FР (она должна быть немного меньше F) выбирается из
гостированного ряда частот {F} при условии, что FР ≤ 0,8F (справочник по кварцевым
генераторам).