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

Автомат Мура

yg

y2

y1

y1

y3

y2

Автомат Мили

xj / ai

a0

a1

a2

a3

a4

xj\ai

a0

a1

a2

a3

x1

a2

a1

a3

a4

a2

x1

a1/y1

a2/y3

a3/y2

a0/y1

x2

a3

a4

a4

a0

a1

x2

a0/y2

a0/y1

a3/y1

a2/y3

x1

x2

x2

x2

x1

x1

x2

x2

x2

x1

a0

a2

a4

a1

a4

a2

a0

a1

a0

a0

a0

a1

y2

y1

y2

y1

y2

y1

y1

y2

y2

y2

y1

2. Графический способ Рис.9. Автомат Мили Рис.10. Автомат Мура

Элементарные автоматы (ЭА)

ЭА используются для построения схем более сложных автоматов и соединяются между собой логическими элементами.

Вкачестве ЭА используют триггеры различных типов.

1.T-триггер

Автомат Мура с двумя устойчивыми состояниями и одним входом T, который изменяет своё состояние на противоположное всякий раз, когда на вход поступает единица.

Таблица переходов T-триггера:

T-триггер
Yg	0	1
xj / ai	0	1
T = 0	0	1
T = 1	1	0

На практике используют матрицу переходов:

	T-триггер
T	Q(t)	Q(t+1)
0	0	0
1	0	1
1	1	0
0	1	1

Рис.11. Схема T-триггера

2.D-триггер

Повторяет сигнал на входе: Q(t) не учитывается.

	D-триггер
D	Q(t)	Q(t+1)
0	0	0
1	0	1
0	1	0
1	1	1

11

Рис.12. Схема D-триггера

3.RS-триггер

Автомат Мура с двумя входами S и R и двумя выходами. Если S = 1, то Q = 1.

Если R = 1, то Q = 0.

Одновременная подача S = 1 и R = 1 запрещена. При S = 0 и R = 0 Q не меняется.

	RS-триггер
R	S	Q(t)	Q(t+1)
Дельта	0	0	0
0	1	0	1
1	0	1	0
0	Дельта	1	1

Рис.13. Схема RS-триггера

4.JK-триггер

ЭА Мура с двумя устойчивыми состояниями и одним выходом. При J = K = 1 триггер меняет своё состояние на противоположное. При других комбинациях функционирует аналогично RS-триггеру.

	JK-триггер
J	K	Q(t)	Q(t+1)
0	Дельта	0	0
1	Дельта	0	1
Дельта	1	1	0
Дельта	0	1	1

Рис.14. Схема JK-триггера Рис.15 Рис.16

Структурная схема КА

Автомат представляет собой композицию запоминающей части, состоящей из элементов памяти (триггеров) и комбинационных схем.

Рис.17

R=]log2 (M+1)[ - число элементов памяти, M - число

L=]log2 F [ -, F - число входных сигналов

N=]log2 G [ - число входных сигналов, G - число выходных сигналов

12

Пусть необходимо синтезировать автомат Мили, заданного совмещённой таблицей переходов и выходов.

xj \ ai	a0	a1	a2
x1	a1 / y1	a1 / y2	a1 / y2
x2	a2 / y3	a2 / y3	a0 / y1

В качестве ЭА будем использовать JK-триггер, в качестве логических элементов — И, ИЛИ, НЕ.

A=a0, a1, a2 →M +1=3

X=x1, x2 F=2

Y = y1, y2, y3 G=3

R=]log2 3[=2→Q1 ,Q2

1. L=] log2 2[=1→α N =] log23[=2→Z1 ,Z2

Таким образом необходимы два элементарных автомата Q1, Q2, один … a, два … Z1 и Z2.

2.Кодирование …

Сучётом кодирования таблица запишется следующим образом:

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

		t			t+1
Альфа	Q1	Q2	Z1	Z2	Q1	Q2
0	0	0	0	0	0	1
0	0	1	0	1	0	1
0	1	0	0	1	0	1
0	1	1	-	-	-	-
1	0	0	1	0	1	0
1	0	1	1	0	1	0
1	1	0	0	0	0	0
1	1	1	-	-	-	-

4.

		t			t+1				t
Альфа	Q1	Q2	Z1	Z2	Q1	Q2	J1	K1	J2	K2
0	0	0	0	0	0	1	0	Дельта	1	Дельта
0	0	1	0	1	0	1	0	Дельта	Дельта	0
0	1	0	0	1	0	1	Дельта	1	1	Дельта
0	1	1	-	-	-	-	-	-	-	-
1	0	0	1	0	1	0	1	Дельта	0	Дельта
1	0	1	1	0	1	0	1	Дельта	Дельта	1
1	1	0	0	0	0	0	Дельта	1	0	Дельта
1	1	1	-	-	-	-	-	-	-	-

5.Синтез комбинационной части автомата

13

Р18

Технические особенности КА

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

1.Необходимость синхронизации работы КА. Причём синхронизируются не только входные сигналы, но и функции возбуждения. Поэтому в автомат вводят две серии СИ

— СИ1, СИ2, сдвинутых на половину периода друг против друга. Под действием СИ1 формируются входные сигналы, а под действием СИ2 изменяется состояние автомата.

Рис.19 Тогда структурная схема автомата примет вид: Рис.20

Данная схема используется в случае применения асинхронных RS-триггеров в элементах память КА. В случае использования синхронных триггеров в них уже имеются элементы И как, например, в синхронном RS-триггере.

Рис.21

Использование RS-триггеров или других синхронных триггеров в качестве элементов памяти облегчает синхронизацию автоматов.

2.Возникновение неустойчивых состояний или «гонок» в автомате. Пусть в графе автомата мы имеем следующий участок.

Рис.22

Вданном случае оба перехода выполняются под воздействием одного и того же входного сигнала xj. Возможен случай, когда автомат за один промежуток работы перейдёт из состояния ai в состояние as и дальше в состояние af, хотя должен остаться в состоянии as. “Гонки» в автоматах возникают в случае, когда изменение состояния памяти автомата зависит от переключения нескольких триггеров. Каждый из триггеров будет пытаться переключиться быстрее и в этом случае память, а следовательно и автомат, может оказаться в некотором промежуточном состоянии, пока не переключатся все триггеры. Для устранения такого эффекта используют дублирование памяти в автомате. Тогда структурная схема будет выглядеть следующим образом:

Рис.23

14

Под воздействием СИ1 переключатся в новое состояние триггеры первого ряда. Под воздействием СИ2 — состояние из триггеров первого ряда переписывается в триггеры второго ряда. Так как СИ2 сдвинуто относительно СИ1 на половину периода, сигнал о состоянии автоматов снимается с триггеров второго ряда, то при СИ1 состояние автомата не изменяется и ожидает прихода СИ2. В таком случае исключены неустойчивые состояния автоматов и «гонки» внутри него. Поэтому в качестве элементов памяти удобно использовать двухступенчатые триггеры.

Эквивалентные автоматы

Два автомата Sa и Sb с одинаковыми входными алфавитами называются эквивалентными.

Для любого автомата Мили существует эквивалентный ему автомат Мура и наоборот.

Алгоритм перехода от автомата Мили к эквивалентному автомату Мура Пусть дан конечный автомат Мили Sa = {Aa, Xa, Ya, δa, λa}.

δa(a, x) — функция переходов. λa(a, x) — функция выходов.

Требуется построить эквивалентный ему автомат Мура Sb = {Ab, Xb, Yb, δb, λb}, у которого Xb = Xa, Yb = Ya.

Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида (am, yg), где yg — выходной сигнал, приписанный к дуге, входящей в состояние am.

Например, для вершины am имеем пары: Рис.24

(am, y1) (am, y2) (am, y3)

Если такие пары мы образуем для всех вершин, то получим множество состояний автомата Мура.

Ab = {(a0, y1), (a0, y2), …, (am, yg)} = {b1, b2, …, bm}, bi = {ai, yi}

δb и λb определим следующим образом: каждому состоянию автомата Мура поставим в соответствие выходной сигнал yg = λb [(ai; yg)] = λb[bi]

Если в автомате Мили … при этом выдавался выходной сигнал yр = λa(ai; xj), то будет переход (ai, yg) → (as, yp).

Рис.25. Автомат Мили

15

Рис.26. Автомат Мура

Переход от автомата Мура к автомату Мили

Пусть дан автомат Мура Sb = {Ab, Xb, Yb, δb, λb}. Необходимо построить эквивалентный ему автомат Мили.

Xa = Xb Ya = Yb Aa = Ab δa = δb

λa (ai, xj) = λb (δb (ai, xj))

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

	Автомат Мура
xj / yi	y1	y1	y3	y2	y3
xj / ai	a0	a1	a2	a3	a4
x1	a1	a4	a4	a2	a2
x2	a3	a1	a1	a0	a0

Тогда эквивалентный ему автомат Мили запишется следующим образом:

		Автомат Мили
xj / ai	a0	a1	a2	a3	a4
x1	a1 / y1	a4 / y3	a4 / y3	a2 / y3	a2 / y3
x2	a3 / y2	a1 / y1	a1 / y1	a0 / y1	a0 / y1

Синтез типовых узлов ЭВМ Регистры

Регистром называется устройство, предназначенное для приёма, хранения и передачи информации.

Регистры также могут выполнять сдвиг числа влево или вправо на заданное число разрядов, преобразование последовательного кода в параллельный и обратно. В зависимости от способа ввода информации различают регистры параллельного, последовательного и параллельно-последовательного действия.

16

Регистры параллельного действия Запись числа в них выполняется во все разряды одновременно, т. е. параллельным

кодом.

Регистр строится на триггерах, число которых равно числу разрядов регистра. В основном на RS- и D-триггерах.

Рассмотрим n-разрядный регистр, в который необходимо записать n-разрядное двоичное число X = Xn-1 Xn-2 … X1 X0. Регистр построен на RS-триггерах с асинхронными входами предустановки.

Рис.27

Прямой и обратный коды каждого разряда числа поступают одновременно на входы S и R триггера. Запись числа осуществляется по синхронизирующему сигналу C. Для чтения прямого хода необходимо подать единицу на Чтпр (чтение прямое). Для чтения обратного хода

— единицу на Чтобр. Если Чтпр = Чтобр = 1, то будет прочитано число в парафазном параллельном ходе. Сброс регистра осуществляется при подаче единицы на установку нуля: Уст. «0» = 1.

Регистры последовательного действия В этом случае используется передача кода по одному каналу разряд за разрядом.

Основу последовательных регистров составляют регистры сдвига, которые осуществляют сдвиг двоичного числа влево или вправо на один или несколько разрядов.

Рассмотрим синтез двухразрядного сдвигающего регистра на D-триггерах.

Регистр должен работать следующим образом. В момент прихода синхроимпульса C число в регистре сдвигается на один разряд вправо. При этом сдвигаемые разряды поступают на выход регистра, а в освободившиеся разряды вводятся числа со входа.

Пусть дана кодированная таблица переходов и функций возбуждения:

α	Q1(t)	Q2(t)	Q1(t+1)	Q2(t+1)	D1	D2		α \ Q1Q2		00		01		11		10
0	0	0	0	0	0	0		0		0		0		0		0
								1		1		1		1		1
0	0	1	0	0	0	0
										D1 = α
0	1	0	0	1	0	1
0	1	1	0	1	0	1		α \ Q1Q2		00		01		11		10
1	0	0	1	0	1	0
								0		0		0		1		1
1	0	1	1	0	1	0
								1		0		0		1		1
1	1	0	1	1	1	1
									D2 = Q1
1	1	1	1	1	1	1

Тогда схема будет выглядеть следующим образом: Рис.28

17

При C=1 во второй D-триггер записывается информация, хранящаяся в первом триггере. А в первый триггер записывается очередной разряд числа, поступающего на вход регистра.

При C=0 записанная информация появляется на выходах триггеров. Аналогичным образом можно построить регистр сдвига на JK-триггерах. Рис.29

При работе такой схемы после n сдвигов во всех триггерах будут нули, потому что на входах первого триггера имеется комбинация J = 0, K = 1, что соответствует режиму установки нуля в триггере. И этот ноль при C=1 записывается в первый триггер, по приходе следующего синхроимпульса он записывается во второй триггер. Регистр сдвига на электрических схемах обозначается следующим образом:

Рис.30

Счётчики

Счётчиком называется тепловой узел ЭВМ, предназначенный для подсчёта числа входных сигналов (импульсов).

Счётчики бывают суммирующие, вычитающие и реверсивные (могут суммировать и вычитать).

Основные характеристики счётчиков:

1.Быстродействие, оцениваемое максимальной частотой поступления входных импульсов F = 1/T, T – период следования счётных импульсов.

Рис.31

2.Модуль счёта, или коэффициент подсчёта K: Kmax = 2n.

Суммирующий счётчик

Рассмотрим трёхразрядный суммирующий асинхронный счётчик, построенный на T- триггерах. Такой счётчик переключается последовательно разряд за разрядом. Тогда схема счётчика представляет собой последовательное соединение трёх триггеров. На вход первого триггера поступают счётные импульсы, второго — сигнал с выхода первого. Для построения таких счётчиков используют двухступенчатые синхронные T-триггеры, которые переключаются по заднему фронту синхроимпульса.

Рис.32

Временная диаграмма работы такого счётчика для случая переключения T-триггеров по заднему фронту синхроимпульсов:

18

Рис.33 Максимальная частота работы этого счётчика определяется по формуле:

F≤ 1

tсчёта +ntn +tопр

tсчёта - …

n tn – время полного переключения n разрядов счётчика. tопр — длительность сигнала опроса.

Вычитающий счётчик. Реверсивный счётчик

Вычитающие счётчики представляют собой последовательно соединённые T- триггеры. На вход первого триггера поступают счётные импульсы и каждым счётным импульсом триггер переключается в противоположное состояние. Второй триггер переключается тогда, когда первый переходит из нуля в единицу. Третий триггер переключается тогда, когда второй переходит из нуля в единицу и т. д.

Если мы строим счётчики на T-триггерах, переключающихся по переднему фронту, то сигнал с инверсного выхода предыдущего триггера нужно подать на прямой вход последующего триггера.

Рис.34. Структура трёхразрядного вычитающего счётчика

2n

K = 8 000 0 001 1 010 2 011 3

1004

1015

1106

1117

Рис.35

19

Реверсивные счётчики

Для построения реверсивного счётчика необходимо соединить схемы суммирующего и вычитающего счётчика. Тогда реверсивный счётчик будет иметь следующий вид:

Рис.36. Реверсивный счётчик

При подаче единицы на шину управления I счётчик работает как суммирующий. Прямой выход первого триггера соединяется со входом T второго триггера.

Так как на шине II — ноль.

…

А на выходе элемента I — единица.

При подаче единицы на шину II всё в точности наоборот и счётчик работает в режиме вычитания.

Рассмотренные счётчики — счётчики с последовательным переносом информации (асинхронные счётчики).

Счётчики с одновременным, сквозным и групповым переносом

Для ускорения процесса счёта необходимо, чтобы перенос информации из одного разряда в другой происходил не последовательно, а одновременно по приходе каждого счётного импульса. При этом счётные импульсы должны подаваться одновременно на входы всех триггеров.

Проведём синтез такого счётчика на основании кодированной таблицы переходов трёхразрядного счётчика и таблицы функций возбуждения.

α	Q3(t)	Q2(t)	Q1(t)	Q3(t+1)	Q2(t+1)	Q1(t+1)	T3	T2	T1
1	0	0	0	0	0	1	0	0	1
1	0	0	1	0	1	0	0	1	1
1	0	1	0	0	1	1	0	0	1
1	0	1	1	1	0	0	1	1	1
1	1	0	0	1	0	1	0	0	1
1	1	0	1	1	1	0	0	1	1
1	1	1	0	1	1	1	0	0	1
1	1	1	1	0	0	0	1	1	1

20