Основы информатики_Савельев А.Я_Учебник_2001

/ л 7. Посяедовательностный автомат

ты самой схемы. Опасность подобной ситуации состоит в том, что из-за различия временных задержек сигналов в рааличных цепях может про­ изойти опережение одного из входных сигналов и схема ложно срабо­ тает. Такой режим называется «гоночным» состоянием (или состязани­

ем) и	вызывает отказ схем. Поэтому разработчик	должен
предусмотреть невозможность возникновения ситуации,		когда
S-R-\,	т . е . в нормально разработанной схеме такое состояние не
должно	возникать.

Б. С и н х р о н н ы й Я5-триггер {рис. 11.23), Рассмотренная ранее схема может быть использована только в асин­

хронных автоматах. Для применения Д5-триггера в синхронных автома­ тах добавляют специальный тактовый вход, который заставляет схему сраба­ тывать в точно определенные моменты времени. Если на тактовом входе тригге­ ра стоит О, то в точках схемы А и В со­ стояние не изменяется даже при измене­

нии состояний входов R и S. Входы R и S влияют на состояние триггера только при состоянии тактового входа, равном

	1. Работа	синхронного		триггера		описы­	Рис. 11.23. Схема
							синхронного триггера
	вайся таблицей		11.13.
	В таблице 11.13 символом				1„ обозначен момент времени до появления
	синхроимпульса,		а символом		Г„^|	— момент после появления синхроим­
	пульса.
							Т а б л и ц а 11.13
	Входы		Момегп времени
			1			г,+1	Примечание
	,V	R	а,	а	а.1	а.,
	0	0	0	1	0	1
	0	0	1	0	1	0	БЕЗ ИЗМЕНЕНИЙ
	1	0	0	1	1	0
	1	0	1	0	i	0	УСТАНОВКА 1
	0		0	1	0	1
	0		1	0	0	1	УСТАНОВКА 0
	1		0	1	*	*
	1		1	0	*	*	} НЕ СТАБИЛЬНО

287

/ / Логическое описание и анализ электронны'^

^ Е

Рис. I .24. Схема

D- 1иггера

В. i)-TpHrrep (рис. 11.24).

Если к схеме 7?5-триггера подключить инвертор так, чтобы вход R синхронного y?.S'-TpHrrepa был всегда инверсным по отношению к входу S, то такая схема будет иметь один вход Д а новая схема называться D- триггером (см. рис. 11.24). Поскольку всегда R^S , гоночное состояние не может возникнуть. Действие О- триггера описывается таблицей 11.14.

		ьЧ	1—»		S3
в	S а	S а	1	S 0а
с	R а'	R а'		R 0'

Рис. 11.25. Схема регистра на U-триперах

£>-1 ()иггер работает как элемент памяти емкостью 1 бит. Если несколь­ ко Д-тр jrrepoB присоединены к одному источнику синхросигналов, то они могут хранить группу разрядов двоичного числа и такая группа триперов итываеуся регистром. Простой Д-триггер называется в литературе защел­ кой (lat h). Схема регистра показана на рис. 11.25. Г'руттирование 1риггеров в р( гистры может осуществляться несколькими путями, например носледова ельным соединением RS- или Д-триггеров.

				Т а б п if li а
Пх[,.д	а,	/„		'...
(-		&	Q,..<	й ' , . 1
	0	1	0	1
(I	1	0	{)	1
1	0	1	1	(1
1|	1	0	1

Г. J ^-триггер.

Этс10Дин из наиболее сложных типов фиггерных схем, широко ис- пользук-дихся на практике (рис. 11.26). Фактически ^Г-триггер является универсальным триггером: оп может работать как любой из описанных выще т[ иггеров. Особеииостью этого типа триггеров является ю, чро со­ стояние J = К=\ четко определено: в этом состоянии Q = Q'. Схема имеет

117 Последовательностный автомат

ОДИН тактовый и два управляющих входа. Действие схемы описывается таблицей 11.15.

			'..		Т а б л и ц а 11.15
	Входы				'„.1
J	к	й,	а,	а,.,	им.
0	0	0	1	0	1
0	о	1	0	1	0
1	0	0	1	1	0
1	0	1	0	1	0
0	1	()	1	0	1
()	1	1	0	0	1
1	1	0	1	1	0
1	1	1	0	0	1

Однако таблица 11.15 ие полностью описывает работу схемы. Это под­ тверждается таблицей 11.16.

Рис. 11.26. Схема УЛ^-триггера

Сущее 1 вую г два 1 ипа Ж-триггеров: первый — АК-триггер с главным и подчине1И1ым элементами, второй — с синхронизацией перепадов напря­ жения. Работа триггеров второго типа гораздо сложнее, и поэтому при про­ ектировании трип еров чаще возникают ошибки. На рис. 11.26 представле­ на схема .УА-1ри11ера первого типа на элементах И—НЕ. Фактически это два си1!хронных Л5-триггера, соединенных по типу главного и подчиненно-

/ / Логическое описание и анализ электронных схем

го и охваченных обратной связью. Опишем работу триггера с помощью бу­ левых выражений: выходной параметр — й,»! • входные переменные — ./, К. (^„ .Такое oiincaHHc может быть получено только для тех состояний, ко­ торые не имеют неопределенных действий:

	0(1	01	10	II
а,	О	О	I	I
й,	1	0	0	1

с помощью карты Кар|ю получим у,,^, ~ J • Q„ '^ К • Q„ . Время пере­ ключения триггера зависит от его конструкции и существенно различно для триггеров первою и второго типов. Следовательно, при проектировании нужно стремиться к тому, чтобы исгюльзовать в составе одного устройства однотипные rpni геры ./А".

			Т а б л и ц а 11.16
		Bita'iciiHe	Реакция па следующий имгтульс
	.;	к
			й„,=а
	0	0
	1	0	Устаионка {J,^_,y - !
	0	1	Сброс у „ , | = 0
	1	1	Переключение g,^, = (?„

Задание для самоконтроля

I. В чем iaKjHO'iaescs смысл пнеления jK>iHiieeKoio оператора схемм? 1.11ай1и миппмальпук) ф(5рму пе полное!|.ю оггределеппой функции:

а) /,(х,. X,. v,) = v ( l " . 2 , 3 " . 4 . 5 . 7 ' ) :

в)	f,(x,x,x,x,)	^	v(0.	I". 2, 4. 6, 7". 8, 9,10", 12, U " ) ;
n)	y i ( . ' i ' : ' i t < )	=	v ( l ' -	2. 5", 6', 8'. 12. 15).

3. Пай I и метолом каскалоа набор миггимальиых функций для следующих уравнений.

а) /,{.х,х,х,)=	,1В+ВС+АС\	6) /,{х,Х2Х,)=~4В+ВС;
/г(.1,л,.х,)=	ABC + 7ВГ ;	/2(х,Х2Х,}=АВС	:
/,(i|.t,.T,)=	/1+ Й + Г .	/ , ( 1 | V J ) =	ISC+ /«ВГ

290

119Разновидности триггерных схем

4.Д-ЧЯ заданной системы уравнений:

2|(/+|) = ^Цч\}^2{и^\)У2г

iiocfpoHifa >лск1ронную схему на элементах И, ИЛИ, НЕ и триггерах.

5. Ис11ол!,1>я элементы И. ИЛИ, НЕ и триггеры, синтезировать логическую схему, задан-

тю ciiciCMOH \равнсний:
	У2 ,*!	=-^2,1*1 "^ Ук,-
6. Сишсшропап. jiu! ическую схему, заданную следующей тaбJtицeй состояний:
.',,				Т а б л и ц а 11,17
	у, ,	Л,г-1	Л,<.|	У2^,.1
0	0	0	I	I
0	0	1	0	0
(1	1	0	1	0
I)	1	1	0	0
1	()	0	1	0
1	(1	1	0	0
1	1	0	1	0
1	1	1	0	0

291

12. МЕТОДЫ ОПИСАНИЯ И СИНТЕЗА ЦИФРОВЫХ АВТОМАТОВ

12.1. Основные понятия теории автоматов

Термин автомат, как правило, используется в двух аспектах. С од­ ной стороны, автомат — устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ — автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математиче­ скую модель реальных технических автоматов [3, 4, 6]. В этом аспекте автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний t?~ { 9 I ( 0 5 ? 2 ( ' ) , - - - , 9 H ( 0 } 5 В которые он под воздействием входных сигна­ лов переходит скачкообразно, т. е. практически мгновенно, минуя itpoMcжуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.

Автомат называется конечным, ecjrn множество его внутренних со­ стояний и множество значений входных сигналов — конечные множества.

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

Входные сигналы в цифровых автоматах предсташгяются в виде ко­ нечного множества мгновенных сигналов. Теоретически это означает, что входные сигналы не имеют длительности, хотя практически это не так. 1 а- кое допущение упрощает рассмотрение процессов, происходящих в авгоматах, так как все события (состояния) должны относиться к фиксироватиюму моменту времени ^ Условно также принимается, что число выходных сиг­ налов >'(/) конечно и они возникают в результате действия входных сигна­ лов. При этом следует учитывать, что одновременно с появлением выход­ ного сигнала происходит скачкообразный переход авюмата из состояния ^,(0 в состояние ^2(0-

292

12 I Основные понятия теории автоматов

Цифровой автомат называется правильным, если выходной сигнал y(t) определяется только его состоянием q(t -1) или qif) и не зависит от вход­ ных сигналов.

Пусть имеется цифровой автомат с одним входом (рис. 12.1). Матема­ тической мoдeJrыo цифрового автомата является абстрактный автомат, за­ данный совокупностью шести объектов;

1) конечное множество X входных сигналов (входной алфавит автомата):

X = {x,(t),x^(t),...,x„(t));

2) конечное множество Y выходных сигналов (выходной алфавит ав­ томата);

»' = {>'|(0,>'2(0,...,л(0);

3)произвольное множество Q состояний автомата:

е= {9,(0,92(0,.-.«.(О);

4)начальное состояние автомата q^,, как элемент множества Q:

5)функция R{q, х) (функция перехода автомата из одного состояния в друюе);

6)([(ункция X(q, х) (функция выходов автомата).

X.{x,(t).,.x,(i)}

y^y,W УМ

«'{?,") •?5('))

Рис. I2.I. Абстрактный автомат с одним входом

иодним выходом

Впача1н,пый момент времени 1„ автомат находится в состоянии q„. В каждый момент времени ( автомат способен принять входной сигнал x{t) и выдать соответствующий выходной сигнал y(t).

Через понятие «абстрактный автомат» реализуется некоторое отобра­ жение множества слов входного алфавита X в множество слов выходного алфавита Y.

Понятие состояния автомата используется для описания систем, вы­ ходы которых зависят не только от входных сигналов в данный момент

293

J2 Методы описания и синтеза цифровых автоматов

времени, но и от некоторой предыстории, т. е. сигналов, которые поступили на входы системы ранее. Состояние автомата соответствует некоторой па­ мяти о прошлом, позволяя устранить время как явную переменную и выра­ зить выходные сигналы как функцию состояний и входных сигналов.

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, так как каждому интервалу дискретности / будет соответствовать свой выходной сигнал >'(/). При этом предполага­ ется, что вьгходной сигнал на одном из выходов автомата может появиться только после соответствующего этому же моменту времени вход1гого сиг­ нала с одновременным переходом из состояния g{t~l) всостояние q{t).

Время для цифрового автомата имеет также важное значение. Дпя реше­ ния задач анализа и синтеза цифровых автоматов обычно вводится автомат­ ное время. Функционирование автомата рассматривается через дискрегные интервалы времени конечной продолжительности {интервал дискретности).

Суш,ествуют два способа введения автоматного времени, по которым цифровые автоматы делят на два класса. В синхронных автоматах момен­ ты времени, в которых фиксируются изменения состояний автомата, зада­ ются специальным устройсгвом — генератором синхросигналов, выдаю- ш,им импульсы через равные промежутки времени (постоянный интервал дискретности). В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены и зависят от каких-то со­ бытий. В таких автоматах интервал дискретности является переменным.

Общая теория автоматов при сделанных выше допущениях разбивается на две большие части — абстрактную теорию автоматов и структурную теорию автоматов. Различие между ними заключается в том, что в абст­ рактной теории мы отвлекаемся от структуры как самого автомата, так и его входных и выходных сигналов. Не интересуясь способом построения автомата, абстрактная теория изучает лишь те переходы, которые претерпе­ вает автомат под воздействием входных сигналов, и те выходные сигналы, которые он при этом выдает. Абстрактная теория автоматов близка теории алгоритмов, является ее дальнейшей детализацией.

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

Автоматы классифицируют по двум наиболее распространенным при­ знакам.

1. Объем памяти. Памятью автомата называют число его состояний.

294

12 I. Основные понятия теории автоматов

Рассмотренные выше автоматы Поста (или Тьюринга) являются беско­ нечными автоматами, так как имеют неограниченную память на ленте. Ко­ нечными автоматами являются отдельные части Э В М или вся машина.

2. Mexaim3M случайного выбора. В детерминированных автоматах поведение и структура автомата в каждый момент времени однозначно оп­ ределены текущей входной информацией и состоянием автомата. В веро­ ятностных автомотах они зависят от случайного выбора,

В теории авюматов установлено, что для осуществления различных преобразований информации совсем не обязательно каждый раз строить iroBbie автоматы: в принципе эго можно сделать на универсальном автома­ те с HOMOiHbFO программы и соответствующего кодирования.

В теории автоматов наиболее гюлно описаны синхронные автоматы. В зависимости oi с1ЮСоба определения выходного сигнала в синхронных ав­ томатах cyijjecTByiOT две возможности:

1) выходной сигнал y{t) однозначно определяется входным сигналом х{1) и состоянием q{t-\) автомата в предшествующий момент;

2) ВЫХОД1ЮЙ сигнал у(1) однозначно определяется входным сигналом x(t) и сосюяиием </(/) в дат1ый MOMeirr времени. Следовательно, закон функцио­ нирования абстрактного автомата может быть задан следующим образом:

](ля автомат а первого рода
\q(t) = b(q(t-\),x(t%
\y(t) = X(qil-\),x(l)\t	= \a,.-\
.)1ля авюмага вгорою рода
iq(t)^4q(t^\),X(t)),
\y(t) = X(q(l),x(t)),t	= \X--

]\s\st да;н,1тен111его анализа целесообразно рассмотреть вопрос о взаимоошошении автоматов первого и второго родов.

Предположим, что произвольный автомат S второго рода задан урав­

нениями (12.2). Для этого автомата построим новую функцию
	X,(q„x) = ^(q(t-\),x(t)),x(t)).
I la основании закона функционирования (12.2)
y(t)	= %(b(q(t-\),x(t)),	x(l) = X^(q(t-\),x(t)).	(12.3)
11олучили новый автомат R первого рода, заданный той же			функцией
перехода b(q.x)	и функцией выходов	Xf(q,x).

12. Методы описания и синтеза цифровых автоматов

Таким образом, для каждого автомата S второго рода существует экви­ валентный ему абстрактный автомат R первого рода, функция выходов ко­ торого получается в результате подстановки функции переходов автомата S в его сдвинутую функцию выходов:

Xf(q,x)-X(&(q,x),x).

Для дальнейшего изложения примем, что произвольные автоматы пер­ вого рода [формула (I2.I)] называются автоматами Мили^ а частный слу­

чай	автоматов второго рода, для	которых сдвинутая функция вь!ходов
X(q,	X) не зависит от второй переменной х, — автоматами Мура.
	Закон функционирования автоматов Мура задается в виде:
	\q(t) =	&(q(t-\),x(t)).	(12.4)
	ЯО = М?(0).

В отличие от автомата Мили, выходной сигнал в автомате Мура зави­ сит только от текущего состояния автомата и в явном виде не зависит от входного сигнала.

Между моделями Мили и Мура существует соответствие, гюзволяющее преобразовать закон функционирования одного из них в другой или обратно. Такое преобразование порождает пару описаний законов функ­ ционирования, эквивалентных в том смысле, что им соответствует одина­ ковая зависимость между входной А'и выходной У последовагелык)С1ями.

Совмещенная модель автомата {С-автомат). Абстрактный С-авто- мат — математическая модель дискретного устройства, для которого за­

даны следующие параметры:
^	= {^,, ...,^,}	— множество состояний;
X	= {Xf{i)...x,Xl)]	— входной алфавит;
' ' = { > ' | ( 0 - Л ( 0 )		—выходной алфавит типа I;
t/ = {М| (О. • • и„, (')}		— выходной алфавит типа 2;
b:QxX-*Q		— функция переходов, реализующая отображение
		D.czQxX	в й
X, .Qx X ->У		— функция выходов, реализующая огображеиие
		D^^QQXX	т Г;
X-^.Q-^U		— функция выходов, реализующая отображеЕГие
		Й!^ с g	на t/;
q^eQ		— начальное состояние автомата.

296