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

Подождите немного. Документ загружается.

/ л

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

ты самой схемы. Опасность подобной ситуации состоит в том, что из-за

различия временных задержек сигналов в рааличных цепях может про-

изойти опережение одного из входных сигналов и схема ложно срабо-

тает. Такой режим называется «гоночным» состоянием (или состязани-

ем) и вызывает отказ схем. Поэтому разработчик должен

предусмотреть невозможность возникновения ситуации, когда

S-R-\,

т.е. в нормально разработанной схеме такое состояние не

должно возникать.

Б. Синхронный Я5-триггер {рис. 11.23),

Рассмотренная ранее схема может быть использована только в асин-

хронных автоматах. Для применения Д5-триггера в синхронных автома-

тах добавляют специальный тактовый

вход, который заставляет схему сраба-

тывать в точно определенные моменты

времени.

Если на тактовом входе тригге-

ра стоит О, то в точках схемы А и В со-

стояние не изменяется даже при измене-

нии состояний входов R и S. Входы R и S

влияют на состояние триггера только

при состоянии тактового входа, равном

Работа синхронного триггера описы-

вайся таблицей 11.13.

В таблице 11.13 символом 1„ обозначен момент времени до появления

синхроимпульса, а символом Г„^| — момент после появления синхроим-

пульса.

Рис. 11.23. Схема

синхронного триггера

Таблица 11.13

Входы

а,

Момегп

времени

г,

а.1

а.,

Примечание

БЕЗ ИЗМЕНЕНИЙ

УСТАНОВКА 1

УСТАНОВКА 0

} НЕ СТАБИЛЬНО

287

// Логическое описание и анализ

электронны'^

^Е

В.

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

Если к схеме 7?5-триггера подключить инвертор

так, чтобы вход R синхронного y?.S'-TpHrrepa был всегда

инверсным по отношению к входу S, то такая схема

будет иметь один вход Д а новая схема называться D-

триггером (см. рис. 11.24). Поскольку всегда R^S ,

гоночное состояние не может возникнуть. Действие О-

триггера описывается таблицей 11.14.

Рис.

I .24. Схема

D-

1иггера

а'

ьЧ

а'

1—»

Рис.

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

£>-1

()иггер работает как элемент памяти емкостью

бит. Если несколь-

ко Д-тр jrrepoB присоединены к одному источнику синхросигналов, то они

могут хранить группу разрядов двоичного числа и такая группа триперов

итываеуся регистром. Простой Д-триггер называется в литературе защел-

кой (lat h). Схема регистра показана на рис. 11.25. Г'руттирование 1ригге-

ров в р( гистры может осуществляться несколькими путями, например но-

следова ельным соединением RS- или Д-триггеров.

Т а б

п if

li а

Пх[,.д

/„

а,

'...

Q,..<

{)

й',.1

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

Этс10Дин из наиболее сложных типов фиггерных схем, широко ис-

пользук-дихся на практике (рис. 11.26). Фактически ^Г-триггер является

универсальным триггером: оп может работать как любой из описанных

выще т[ иггеров. Особеииостью этого типа триггеров является ю, чро со-

стояние J

К=\ четко определено: в этом состоянии Q

Q'. Схема имеет

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

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

таблицей 11.15.

Таблица 11.15

Входы

()

'..

й,

()

а,

'„.1

а,.,

им.

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

тверждается таблицей 11.16.

Рис.

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

Сущее

вую

два

ипа Ж-триггеров: первый — АК-триггер с главным и

подчине1И1ым элементами, второй — с синхронизацией перепадов напря-

жения. Работа триггеров второго типа гораздо сложнее, и поэтому при про-

ектировании трип еров чаще возникают ошибки. На рис. 11.26 представле-

на схема .УА-1ри11ера первого типа на элементах И—НЕ. Фактически это

два си1!хронных Л5-триггера, соединенных по типу главного и подчиненно-

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

го и охваченных обратной связью. Опишем работу триггера с помощью бу-

левых выражений: выходной параметр — й,»! • входные переменные — ./,

К. (^„ .Такое oiincaHHc может быть получено только для тех состояний, ко-

торые не имеют неопределенных действий:

0(1

01 10 II

а, О О I I

й, 10 0 1

с помощью карты Кар|ю получим у,,^, ~ J

•

Q„ '^ К

•

Q„ . Время пере-

ключения триггера зависит от его конструкции и существенно различно для

триггеров первою и второго типов. Следовательно, при проектировании

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

однотипные rpni геры ./А".

Таблица 11.16

Bita'iciiHe

Реакция па следующий имгтульс

й„,=а

Устаионка

{J,^_,y

Сброс у„,| =0

Переключение 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) yi(.'i':'it<) = v(l'- 2. 5", 6', 8'. 12. 15).

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

а) /,{.х,х,х,)= ,1В+ВС+АС\ 6) /,{х,Х2Х,)=~4В+ВС;

/г(.1,л,.х,)= ABC + 7ВГ ; /2(х,Х2Х,}=АВС :

/,(i|.t,.T,)= /1+

+ Г .

/,(1|VJ)=

ISC+ /«ВГ

290

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

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

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

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

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

тю ciiciCMOH \равнсний:

У2 ,*!

=-^2,1*1

Ук,-

6. Сишсшропап. jiu! ическую схему, заданную следующей тaбJtицeй состояний:

Таблица 11,17

.',,

у, ,

()

Л,г-1

Л,<.|

У2^,.1

291

12.

МЕТОДЫ ОПИСАНИЯ И СИНТЕЗА

ЦИФРОВЫХ АВТОМАТОВ

12.1.

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

Термин автомат, как правило, используется в двух аспектах. С од-

ной стороны, автомат — устройство, выполняющее некоторые функции

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

ЭВМ — автомат, так как после загрузки программы и исходных данных

ЭВМ решает заданную задачу без участия человека. С другой стороны,

термин «автомат» как математическое понятие обозначает математиче-

скую модель реальных технических автоматов [3, 4, 6]. В этом аспекте

автомат представляется как «черный ящик», имеющий конечное число

входов и выходов и некоторое множество внутренних состояний

t?~ {9I(05?2('),---,9H(0}5

В которые он под воздействием входных сигна-

лов переходит скачкообразно, т. е. практически мгновенно, минуя itpoMc-

жуточное состояние. Конечно, это условие не выполняется в реальности,

так как любой переходный процесс длится конечное время.

Автомат называется конечным, ecjrn множество его внутренних со-

стояний и множество значений входных сигналов — конечные множества.

В практике часто используется понятие цифрового автомата, иод ко-

торым понимают устройство, предназначенное для преобразования цифро-

вой информации.

Входные сигналы в цифровых автоматах предсташгяются в виде ко-

нечного множества мгновенных сигналов. Теоретически это означает, что

входные сигналы не имеют длительности, хотя практически это не так.

а-

кое допущение упрощает рассмотрение процессов, происходящих в авгома-

тах, так как все события (состояния) должны относиться к фиксироватиюму

моменту времени ^ Условно также принимается, что число выходных сиг-

налов >'(/) конечно и они возникают в результате действия входных сигна-

лов.

При этом следует учитывать, что одновременно с появлением выход-

ного сигнала происходит скачкообразный переход авюмата из состояния

^,(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)}

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

y^y,W

УМ

Рис.

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

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

В пача1н,пый момент времени

1„

автомат находится в состоянии q„. В

каждый момент времени ( автомат способен принять входной сигнал x{t) и

выдать соответствующий выходной сигнал y(t).

Через понятие «абстрактный автомат» реализуется некоторое отобра-

жение множества слов входного алфавита X в множество слов выходного

алфавита Y.

Понятие состояния автомата используется для описания систем, вы-

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

293

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

времени,

но и от некоторой предыстории, т. е. сигналов, которые поступили

на входы системы ранее. Состояние автомата соответствует некоторой па-

мяти о прошлом, позволяя устранить время как явную переменную и выра-

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

Работу абстрактного автомата следует рассматривать применительно к

конкретным интервалам времени, так как каждому интервалу дискретности

/ будет соответствовать свой выходной сигнал >'(/). При этом предполага-

ется,

что вьгходной сигнал на одном из выходов автомата может появиться

только после соответствующего этому же моменту времени вход1гого сиг-

нала с одновременным переходом из состояния g{t~l) всостояние q{t).

Время для цифрового автомата имеет также важное значение. Дпя реше-

ния задач анализа и синтеза цифровых автоматов обычно вводится автомат-

ное время. Функционирование автомата рассматривается через дискрегные

интервалы времени конечной продолжительности {интервал дискретности).

Суш,ествуют два способа введения автоматного времени, по которым

цифровые автоматы делят на два класса. В синхронных автоматах момен-

ты времени, в которых фиксируются изменения состояний автомата, зада-

ются специальным устройсгвом — генератором синхросигналов, выдаю-

ш,им импульсы через равные промежутки времени (постоянный интервал

дискретности). В асинхронных автоматах моменты перехода автомата из

одного состояния в другое заранее не определены и зависят от каких-то со-

бытий.

В таких автоматах интервал дискретности является переменным.

Общая теория автоматов при сделанных выше допущениях разбивается

на две большие части — абстрактную теорию автоматов и структурную

теорию автоматов. Различие между ними заключается в том, что в абст-

рактной теории мы отвлекаемся от структуры как самого автомата, так и

его входных и выходных сигналов. Не интересуясь способом построения

автомата, абстрактная теория изучает лишь те переходы, которые претерпе-

вает автомат под воздействием входных сигналов, и те выходные сигналы,

которые он при этом выдает. Абстрактная теория автоматов близка теории

алгоритмов, является ее дальнейшей детализацией.

В противоположность абстрактной теории, в структурной теории авто-

матов рассматриваются прежде всего структуры как самого автомата, так и

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

бы построения автоматов из элементарных автоматов, способы кодирова-

ния входных и выходных сигналов элементарными сигналами и т. п.

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

при-

знакам.

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

294

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

Рассмотренные выше автоматы Поста (или Тьюринга) являются беско-

нечными автоматами, так как имеют неограниченную память на ленте. Ко-

нечными автоматами являются отдельные части ЭВМ или вся машина.

Mexaim3M случайного выбора.

детерминированных автоматах

поведение и структура автомата

каждый момент времени однозначно оп-

ределены текущей входной информацией

состоянием автомата.

веро-

ятностных автомотах они зависят от случайного выбора,

В теории авюматов установлено, что для осуществления различных

преобразований информации совсем не обязательно каждый раз строить

iroBbie автоматы:

принципе эго можно сделать на универсальном автома-

те с HOMOiHbFO программы и соответствующего кодирования.

В теории автоматов наиболее гюлно описаны синхронные автоматы.

зависимости

с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его анализа целесообразно рассмотреть вопрос

взаимо-

ошошении автоматов первого и второго родов.

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

второго рода задан урав-

нениями (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олучили новый автомат

первого рода, заданный той же функцией

перехода 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