Теория автоматов

В случае автомата Мура КС2 служит для  преобразования слова внутренних переменных автомата в соответствующую ему микрокоманду. Однако выполнение этого преобразования является скорее функцией операционного автомата. Это связано с тем, что код состояния автомата имеет меньшую длину, чем число различных микроопераций y_j, 1≤i≤n, выполнение которых инициируется автоматом.

Канонический метод структурного синтеза цифровых автоматов включает следующие этапы:

1. задание абстрактного автомата отмеченной таблицей переходов – выходов;
2. кодирование элементов множества состояний, входов и выходов;
3. создание кодированных таблиц переходов и выходов;
4. выбор элементов памяти;
5. создание расширенной таблицы переходов – выходов с внесением  в нее функций возбуждения элементов памяти;
6. выбор логического базиса для проектирования цифрового автомата;
7. определение МДНФ для функций возбуждения элементов памяти и функций выходов автомата;
8. построение логической схемы автомата в выбранном логическом базисе.

Элементы памяти в цифровых автоматах

В качестве элементов памяти цифровых автоматов используется автомат  Мура с двумя состояниями, в котором  значение выходного сигнала совпадает с текущим состоянием автомата.  Таким элементом памяти является триггер. На схемах триггер обозначается прямоугольником, состоящим из двух полей: на левом указаны информационные входы (один или два), а также входы начальной установки и синхронизации, на правом - выходы триггера и его условное обозначение "Т", Рис. 4.

 

 

 

 

Триггер предназначен для хранения одного бита, или одного разряда  двоичного числа. Для хранения многоразрядных чисел используют линейки триггеров, называемые регистрами. Состояния триггера и соответствующие им выходы обозначаются 0 и 1. Наиболее распространенными являются D- триггер, Т - триггер, имеющие один информационный вход, RS и - JK- триггеры. Имеющие два информационных входа. Обозначения входов:

R₀ (reset) - раздельный вход установки в 0;

S₁ (set) - раздельный вход установки в 1;

K₀ - вход установки универсального триггера в состояние 0;

J₁ - вход установки универсального триггера в состояние 1;

T - счетный вход;

D (delay) - установка триггера в состояние, соответствующее логическому уровню на этом входе;

C - управляющий (синхронизирующий вход).

Выходы:  Q - прямой,`Q - инверсный.

По характеру реакции на входные  воздействия различают синхронные и асинхронные триггеры.

Асинхронный триггер  - входные  сигналы управляют состоянием триггера непосредственно с момента подачи их на входы.

Синхронный триггер - входные сигналы  действуют на состояние триггера только при подаче синхроимпульса на управляющий вход С.

Матрицы переходов триггеров приведены  в таблице 18.

Таблица 22 Матрицы переходов RS, JK, D и Т триггеров

qt®qt+1	J	K	R	S	D	T
0 ® 0	0	*	*	0	0	0
0 ® 1	1	*	0	1	1	1
1 ® 0	*	1	1	0	0	1
1 ® 1	*	0	0	*	1	0

 

Проектирование автомата Мили

Кодированная таблица переходов-выходов

Первый этап канонического метода проектирования цифровых автоматов состоит в переходе от таблицы переходов-выходов абстрактного автомата к кодированной таблице переходов - выходов. Рассмотрим этот переход применительно к автомату Мили.

Таблица 23 Отмеченная таблица переходов-выходов автомата Мили

Z A	z1	z2	z3
a0	a0/w1	a1/w2	a2/w3
a1	a1/w2	a0/w1	-/-
a2	a2/w2	a1/w3	a0/w1

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

Способ кодирования может быть выбран произвольно. Пример кодирования  приведен в Табл. 20.

Таблица 24 Таблицы кодирования

A	[ai]		Z	[zj]		W	[wk]
a0	00		z1	01		w1	01
a1	01		z2	10		w2	10
a2	10		z3	11		w3	11

Далее необходимо составить кодированные таблицы переходов и кодированные таблицы выходов.  Кодированные таблицы переходов- выходов составляются непосредственно по отмеченной таблице переходов – выходов абстрактного автомата, Табл. 20

Таблица 25 Кодированная таблица переходов выходов автомата Мили

[Z] [A]	01	10	11
00	00/01	01/10	10/11
01	01/10	00/01	-/-
10	10/10	01/11	00/01

 
Состояния автомата из множества  А кодируются двумя битами. Это  означает, что для хранения кода состояния автомата и выработки нового состояния, в которое автомат перейдет в следующем такте автоматного времени, потребуется два элемента памяти, т.е. два триггера. Триггер может переключиться в новое состояние только после прихода синхронизирующего сигнала. Для того, чтобы обеспечить правильное переключение триггеров, соответствующее таблице переходов автомата, необходимо подать на его информационные входы сигналы, обеспечивающие заданный переход. Например, в выделенной клетке таблицы 21 первый элемент памяти должен переключиться из состояния 1 в состояние 0, а второй элемент памяти – из состояния 0 в состояние 1. Исходное состояние триггера определяется по крайнему левому столбцу таблицы. Чтобы обеспечить нужное переключение триггеров, на их входы необходимо подать сигналы в соответствии с матрицей переходов  выбранного триггера. Следовательно, следующий шаг проектирования состоит в выборе элементов памяти. Сигналы, подаваемые на информационные входы элементов памяти, называются функциями возбуждения элементов памяти. Функции возбуждения элементов памяти записываются в таблицу, формат которой аналогичен формату кодированной таблицы переходов, табл. 22. Для определенности выберем в качестве элементов памяти RS – триггеры.

Таблица 26 Функции возбуждения первого элемента памяти R₁S₁

[Z]/ (x1,x2) [A]    (t1,t2)	01	10	11
00	*0	*0	01
01	*0	*0	*/*
10	0*	10	10

 

Таблица 27 Функции возбуждения второго элемента памяти R₂S₂

[Z]/ (x1,x2) [A]    (t1,t2)	01	10	11
00	*0	01	*0
01	0*	10	*/*
10	*0	01	*0

 

Переменные t₁,t₂, кодирующие состояния автомата, называются внутренними переменными автомата, в переменные x₁,x₂, кодирующие входные сигналы – внешними переменными.

Очевидно, что таблицы 21, 22 и 23 задают булевы функции, реализовав которые, мы получим логическую схему цифрового автомата.  Для  минимизации этих функций запишем их в более привычном виде. Для выбранных элементов памяти и абстрактного автомата, заданного таблицей 19, число булевых функций, которое необходимо реализовать равно 6: R₁,S₁, R₂, S₂, y₁, y₂. Здесь y₁, y₂ – выходные сигналы автомата Мили, определяемые непосредственно по таблице 21.

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

Логическая схема управляющего автомата при таком способе проектирования и без ограничений на число выходов логических элементов является двухслойной: первый слой – конъюнкторы, второй – дизъюнкторы. При применении реальных выпускаемых промышленностью интегральных схем глубина схемы может увеличиться из-за реализации многоместных операций конъюнкции и дизъюнкции последовательно соединенными элементами.

Таблица 28 Логические функции автомата Мили

t1t2x1x2	R1S1	R2S2	y1y2
0000	**	**	**
0001	*0	*0	01
0010	*0	01	10
0011	01	*0	11
0100	**	**	**
0101	*0	0*	10
0110	*0	10	01
0111	**	**	**
1000	**	**	**
1001	0*	*0	10
1010	10	01	11
1011	10	*0	01
1100	**	**	**
1101	**	**	**
1110	**	**	**
1111	**	**	**

 

Минимизируя полученные функции, получим:

R₁=t₁x₁;

S₁= `t₁x₁x₂;

R₂=t₂;

S₂=`t<sub>2</sub>`x₂;

Рисунок 5 Логическая схема автомата Мили

Проектирование автомата Мура

Пусть автомат Мура задан отмеченной таблицей переходов – выходов

Таблица 29 Отмеченная таблица переходов- выходов автомата Мура

Z A	z1	z2	z3	W
a0	a0	a1	a2	w1
a1	a1	a0	-	w2
a2	a2	a1	a0	w3

Пусть кодирование элементов множества  состояний А и множества входов Z задано Табл. 20. Элементы множества выходов кодировать не требуется, так как пока автомат находится в некотором состоянии a_i, он вырабатывает соответствующий этому состоянию сигнал w_i. Так как таблица переходов в данном  примере совпадает с таблицей переходов автомата Мили, то при выборе  в качестве элемента памяти RS-триггера функции возбуждения элементов памяти будут Такими же, как и в автомате Мили. Логическая схема автомата мура  приведена на рис.

Рисунок 6 Логическая схема автомата Мура

Принцип микропрограммного управления в цифровых автоматах

Применительно к ЭВМ  объектом управления называется любое  цифровое устройство, предназначенное для выполнения каких-либо операций над данными. К таким устройствам, называемым операционными, относятся, например, процессоры, каналы ввода-вывода, контроллеры внешних устройств и др. Операционное устройство состоит из исполнительной части (операционного автомата) и управляющей части (управляющего автомата), который управляет работой исполнительного устройства.  Принцип микропрограммного управления состоит в следующем.

1. Любая операция, реализуемая операционным устройством, рассматривается как сложное действие, разделяемое на последовательность  элементарных неделимых актов обработки информации в течение одного такта автоматного времени, называемых микрооперациями. Множество микроопераций, выполняемых в одном такте автоматного времени, называется микрокомандой. Если в некотором такте работы  операционного устройства не выполняется никаких микроопераций, то соответствующую микрокоманду обозначают y_e.
2. Для управления порядком выполнения микрокоманд используются логические условия, которые в зависимости от результатов преобразования данных в операционном устройстве могут принимать значения 0 и 1.  Множество логических условий (осведомительных сигналов) будем обозначать символами X={x₁,x₂,…,x_n}.
3. Процесс выполнения микроопераций описывается с помощью микропрограммы, представленной в виде граф-схемы алгоритма (ГСА). Микропрограмма определяет порядок проверки значений логических условий и следования микроопераций. Микропрограмма используется как форма представления функции операционного устройства и определяет порядок функционирования структурных элементов операционного устройства во времени.