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

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

12.4. Соединение автоматов

Таблица 12.5

у'

y'l

Ух

У\

Уг

У'г

Уг

Здесь, например, 5(qj, Jc,) =

5((Й2,

с,), х,) =

(5,

(й,,

JT,

), бг (Ci, J^i)) =

—г

«1

1 ''

''l^l

1 ''J'"3

•?!

''s'-i

6,C|

<?]

6,C|

<?<

6|C2

6,C,

Та

«5

6jC|

'г''!

блица 12.6

62C2

6,c,

Функпия выходов

задается таблицей 12.7.

«1

'/1

>т

Уг

Яг

Уг

У1

Я}

Уг

Я>

Уу

У\

Таблица 12.7

Уг

Яь

y-i

Ух

Здесь, например, X(q,, л:,) =

Х{{Ь-^,

с,), х,) =

ф(Х.|

(^2, jr,),

Х.2

(f|, Jf|)) =

" 'pCvi, >'") = У г

•

flocvieOoeanK'Jihuoe

соединение двух авгомагов представлено на рис. 12.7,6.

В лом случае первый авгомат S,, второй автомат ^2

> •''•

е. выходы первого ав-

томата яшгяюгся входом второго. Результирующим автоматом последователь-

ного соединения .V, и ^2 будет автомат S = {g, Л", У, 5,

X.j,

для которого

У = у, ху2,или е = {?„, =(?„!.?«2)1?ш1 6 0,?.,2е62!;

Х = Х;

фугжция переходов:

5(У

JT) =

(5,

X),

(бз

Х,, (й

X)));

функция выходов X:

М</,„,*,) = >^2(9,„2Д|(9тГ.*,)).ИЛИ Х{в^Х)

Х^(в2 >iXx(Q,

X)) .

в качестве примера рассмотрим те же автоматы S, н S2, заданные

таблицами 12.8, 12.9.

307

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

Таблица 128 1аблица 129

»2

*| 1У\

hly\

'ъ/л

h/y,

С,

•••Jy,

•=11У г

••2/л

<•,/>',

Результирующим апюматом 1Юслелователыю1о соединения автомаюв

S| и 5; будетавтома! ,V. для Koiopoio

е = {(А,,e,),(/),,t, ),(/>,.C|),(*j,Cj),(A„<;|),(*3.С; )) = {</,. •</„);

Функция переходов 5 определяется таблицей 12.10.

Х;

•ъ

Ч,

*,'•,

Ь,е,

Чг

IV;

Чг

Ь,г,

*,<•,

Ч, _j

'/1

*2<-:

I аблмиа 12 1(1

/м-,

Здесь, например,

5(?,.->c,) = S((/',.'i). v,)-(8,(/),,v,).5J(^,,X,x(/,J,,,))-

=(^.fi,(Г|,>•г))=(/J|,tJ)=(/J.

Функция выходов X определяется табл.

12,11.

Таблица 1211

.Т|

Ч,

У,

J'l

Чг

У2

.•'2

J'2

V'l

У:

Уг

Ч^

У,

Чк

У1

у-1

Здесь, например, Х((/,, ,i|) = X((A2,c,),X|) = Х2(С|. Х, х(Л,,,\:|)) =

Соединение автомаюв с обрагиой связью представлено па рис. 12.7, е.

В этом случае автоматы

S^-{Q^^X^,Y^,b^,W

и .Sj ={(?;, F,,

Kj.Si.

Х,| .

Имеется некоторый функционш!ьиый преобразователь у, являющийся ав-

томатом без памяти, коюрый реализует отображение у: XxF, -^Х^. В

этом случае, по крайней мере, один из автоматов S, или S, должен быть

автоматом Мура. Пусть ,S'j - - автомат Мура, у которого К^ = X^iQi). Тогда

308

Соединение автоматов

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

новый автомат S = {Q, X, Y, 5, X), для которого

f = а

Sz =

{<7„

(<7,„1,

<7.,2) I

<7»|

е а, ?„2 е бг};

Х = Х;

Y,;

функция переходов:

8(</,„.

^,) = (8| (««I.

У(:с,

Д2(<7,,2))).52(<7,,2 Д1 (9,„|. Г(^, Д2(9»2)))),

mnl,(QyZ}

b,(g,xy(XxX,(Q,))),b,(Q2xX,(Q,xy(Xxk,(Q,))));

функция выходов:

М?„,

Д:,) =

Я.,

(<7,„|, у( J^V,

>-2

(<7.,2 ))).

или X(QxX)

X,(Q^xy(XxX,(Q^))).

В качестве примера рассмотрим два автомата: S, ={JS, Л К^б,,

Я.,}

Sj = {С.!'.''-бгДгЬ''оторые заданы таблицами 12.12и

12,13.

/'1

Г2

I'l

Ь,/У,

'ь/л _

Таблица 12.12

ki/yi

*,Av,

bjy,

Ь./Уг У1

Уг

У}

Таблица 12.13

С[

сг

'•i

''г

С;

С г

«2

Функциональный Преобразователь у задан таблицей 12.14

Таблица 12.14

"г

Рг

Р2

Jfl

Резулыирующим автоматом соединения с обратной связью будет ав-

томат S = {Q, X, Y, 5, X}, для которого

У =ВхС = {(/'1.^-1 ).(*!.'•2).(*2.С,),(*2,С2),(*з.С,).(*З.С2)} = {9|.92 •.•9б};

= {Л.>'2.>'з}-

функция переходов 5:QxX-*Q определяется следующим образом

(табл. 12,15):

309

</l

h,c,

b,c,

Memodhi

OIHN

ami.

цифровых автоматов

Яг

l,,c.

h^cj

Л,С2

h,C,

^iW

b..

Таб

h,c,

b,c,

h,c,

липа

12 15

'/.

Ait4

h,c.

l,,c.

Здесь, например.

5(</,, V,)-«((/,,.с, ),v,) = (5,(6j,Y(,v,,X,(с,))));

52('-|Д|(*2Л(-1-,.Х,«, ))))--(й,(/,,.у(л-,,1', »).5,('-1Д| (''2-Y(<-|.'',))) =

= {И,ill,,у).И,(с,.I,(h,.p,)))-^(h,.b,{c;,x,))--{/,,.с,)^,,,.

Функция выходов Х:{}-^'Х -^ У задается таблицей 12.16.

afiJiililii

12 К.

'/1

'/6

лом

случае, например.

M'?,.V|)-X((/.,,r,). г,)-Х,(А,,т(л-,,Х,(с,))).

?^,fЛ,,y(V,.l•|))-X|(/),,/7,)

_V2.

г.

.V,

'/1

1-,

г,

1'1

_'Л 44^

* 2

.''}

.1'2

>*,

_1^^:

[^ .''I

12.5.

Ciiiiic) управляющею автомата

По функциональному начиачсиию основные устройства

ЭВМ

можно

условно разделить

ма две

каюгорни: операционные устройство

(ОУ) и

управляющие устройства (УУ). Отдельные части операцнониото устройст-

ва функционирукм

01гре;1елегтой последовательности

зависимости

алгоритма выпо^тяемой операции. Управляющее устройство

по

сигишгу

операции вырабатывав! необходимые сигналы,

но

которым запускается

выполнение заданной мнкросчшрацнн. Совокупность микроопераций, объе-

диненных а/п'оригмом операции. состав;гяет микроиро! рамму операции,

которая,

свою очередь, являемся связующим звеном между коман;юй

(ко-

дом операции)

операциоппым устройством (аппаратными средствами),

предназначенным для преобраишання информации.

12 5 Синтез управляющего автомата

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

рабатывающих управляющие сигналы в заданной последовательности. Та-

кое управляющее устройство можно рассматривать как управляющий ав-

томат типа Мура или Мили.

Чтобы 1юстроить схему угтравляющего автомата, нужно задать микро-

программу рабо1ы операционного устройства. Микропрограмма может

бьпь чадана в виде граф-схемы (рис. 12.8, а). Микропрограмма выполняет-

ся при начальном ус;говии И = I. Условия определяют последовательность

вl.мк)JПleиия микроопераций. Посмотрим, как связать граф-схему микро-

npoi раммы с арюматом Мура или Мили.

Vz?2,=Zj

1'ис. 12.8. Гра(|)-схема операционного aaxoMaia (а),

раф-переходе в

iimoMata Мура {в), граф-переходов ав-roMaia Мили (в)

)\^ш

авюмак! Мура выходной сигнал зависит только от внутреннего

сосюямия. I.e. в нашем случае v

F{Q). Поэтому каждая операторная

И я

Ла/тин!

Мсюдупсскиеукагаиия

лабораюрнымра&тгам.

Ч,

2, МВТУ, 1987.С 14-16.

311

Методы

описания

синтеза

цифровых

авточитов

вершина граф-схемы алгоритма должна быть отмечена символом исходно-

го состояния автомата q,. Па рис. 12.8, а слева от операторов дана отметка

граф-схемы, ин1срггрс1ируемой как автомат Мура. По :)1им отмегкам мож-

но построить граф переходов автомата Мура (рис, 12.8, б), где вершинами

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

стояния в друюе. Таким образом, функции выходов автомата Мура

\\ = V q^,

где q, - состояние авюмага, оГ)еспечива(ОН1ее вырабогку cMi нала г^ .

Переход авюмата w^ одного состояния в другое (гри отс>1С!вни jrom-

ческих условий (безусловный переход) происходит под действием синхро-

сигнала. Условный переход нропс.ходит в том случае, если

COOTBCICIBVIO-

щее условие z, - I.

Для построегн1я автомта Мшн1 следуе! ггомнть, чю выходной сиг-

нал зависит как от BnyrpcFHiero сос1оягн1я, так и от входною cni ruura (re.

условия 2,): v^F(P.Z). PaiMeiKa граф-схемы для авгомата Мили дела-

ется иначе, чем для автомага Мура. Символом t/y отмечакпся вход нерпой

вершины графа, следующей за начальной, и вход конечной верншны. Вы-

ходы других онера1орги>1х вернин! отмечаются симво;гом </,,

1а

рис.

12.8. с/ автома! Мили огмемеп символами, взяпимн и скобки ! раф

переходов автомат Мили ноказаи па рис, 12.8. «. В авюмакгх Мили

фу!)кции выходюв, tro коюрым вырабатываются сигналы микрооисратгп.

определяются но (|)ормуле

'•; ~- V(/,(VZ^).

I к

где q,

—-

состояние автомага, со11ровождающегося выработкой cm нала г^ :

7j( — логическое условие, oпpeдeJrяющee выработку сн1нала v^ при пере-

ходе автомата из состояния с/,.

В случае безусловною перехода автомата из сосюяния </, стнал v^

определяется только згшченнем q^.

После построения аиюмата Мура или Мили фуикииопированне

управляющего автомата представляют в виде таблиц переходов и вы-

ходов. Для ЭТ010 проводят кодирование состояний автомата двоичггыми

кодами, определяют тин и количество три1 геров, Затем

1Ш

таблице пе-

реходов устанавливают значения сигналов на входах триггеров, при

которых осуществляются переходы; определяют функции возбуж.чеиня

312

/ 2

6 Логическое проектирование управляющего автомата

триггеров и проводят их минимизацию (упрощение). По найденным

выражениям строится схема управляющего автомата на выбранных

)лемеи lax.

12.6.

Логическое проектирование управляющего автомата

PacCMoipMM мегодику синтеза управляющего автомата на конкретном

примере. Предположим, что требуется создать логическую схему для

управления цифровым замком. Срабатывание реле замка происходит в ре-

!yju>iaie иоомередного набора комбинации цифр (трех из десяти кнопок) в

cipoioi'i IrocJreдoвaleльнocти. Возвращение автомата в исходное состояние

происходиf ири срабатывании двери в момент ее приоткрывания. Синтез

авюмаи!

проводшся в necKOJibKo этапов .

LAiiiuiin условия задачи. Очевидно, схема должна содержать не

lojM.KO комбипациокпую, но и запоминающую часть, так как автомат

дол-

жен «помнить» Г1ред1иествующее состояние и в зависимости от него реаги-

ропаи,

гго-разиому па один и тот же входной сигнал. Кроме того, следует

мрииимагь I! расчсг то, что при подаче питания иа электронную схему ав-

\о\м\\ можс! \'Сгаповигься в любое состояние (в том числе и в состояние

«cpaOotaji» или некое нештатное состояние, из которого он может и не

Bi.iiirn). По)1ому для обеспечения работоспособности придется предусмот-

рен,

сброс aisioMaia в iia4ajibnoe состояние при включении питания, а также

при по5М(гжн1,1\ сбоях в функционировании. Переход в начальное состояние

опя тпк' юн п п случае открывания двери (кем-либо из выходящих), в про-

циесе набора кода индивидуумом, желающим проникнуть за охраняемую

лверь-

Условимся, чю авюмат должен выдавать «сигнал тревоги» при вводе

neijepnoii ци(|)ры, чю вполне может оказаться попыткой подобрать код.

Для разработки шпоритма функционирования автомата совершенно

iieo6\(viiiNio определить множества входных сигналов, выходных сигналов

и множество ус weuU перехода автомата из одного состояния в другое.

М и о

>1с

е с I в о входных сигналов {х,):

\, СИ! нал введенной иравилыюй 1-й цифры кода;

Y, сигнал введешюй правильной 2-й цифры кода;

V, сигнал введенной правильной 3-й цифры кода;

.V, сигнал, означающий «дверь открыта».

Пример ггплиионлсм [i I ирепко

313

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

Входными сигналами мог>т быть сигналы, поступающие от любой из

Ю кнопок. Для простоты принимаем, что автомат реагирует избирательно

лишь на перечисле11иые си! налы.

Множество выходных сигналов {/,):

/| — сигнал, приволягции в состояние «открыто» реле замка (мри

У| -

считаем, что автомат iie разрешает замку открываться);

/з

—

«сигнал TpCBOi н». он может возбуждать схему запуска звуково! о

генератора (попросту говоря, вюгючмть сит иализацию).

Множество логических условий переходов {г,};

— про1пел ли cHi пал г, ?

- прошел

JH1

cvri нал v, ?

— прошел ли сигнал v, ?

— открыта ли дверь?

Ввиду очевидной связи между условиями и входными сигналами бу-

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

(л-,}.

Рйзработка алгоритма функционирования автомата.

Алгоритм функционирования автомата В1юлне поня1ен: переход в со-

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

введены верные цифры кода.

Введем операторы. кои>рые потребуются для заштси алгоритма:

V, " ожидать ввода сигнала 1-й 11ифры кода;

1'2 — ожидать ввода сит нала 2-й цифры кода;

г, - ожидать ввода

CHI

нала 3-й цифры кода;

V., выдать выходной сипгал /, = I;

—

выдать вьгход!ЮЙ «сигнал тревоти» /з - ! .

В дальнейшем станет ясно, зачем операторы v,,...,r, определяются

столь стран!юй, на первый

вз1

ляд, формулировкой.

Ввиду простоты алгоритма перейдем сразу к состояник! ею граф-

схемы (ГСА) без записи микропрограммы (рис. 12.9).

Операторы v,,...,v^, указывают на «зависание» автомата, т.е. ожтгда-

ние ввода очередной информации (рис. 12.9 — траф-схема ajnopHiMa

функционирования •электронного замка).

Примечание i СЛ не обратас! переход автомата в начальное сосюягтне ш иеонрс-

делеиного сосгояння.

12 6 Логическое проектирование управляющего автомата

Рис.

12.9.

раф-схема

алюртма ф)11К!1Нчииро-

RiUHifl i.iieKipoiinoH) iaMKa

Сишез цифровою автомата.

С'ишеч ироводтся но одному из двух вариантов.

Синтез автомага Мура.

В с()01ве1С1Вии с зем. что выходной сигнал в автомате Мура чавист

nuihKo or состояния, но не зависит от входного сигнала, выполним отметку

ГСЛ по следующим правилам:

— символом ^1) отмечаем вершины «Начало» и «Конец»;

— •

отмечаем все операторные вершины символами ij,, ^^ и т. д.;

— различные вершины отмечаем различными символами.

Символы q, обозначают состояние автомата.

Следуя or вершины к вершине всеми возможными путями, подучаел

граф переходов автомата Мура (рис. 12.10).

Состояние i/й является любым нештатным (неопределенным), в которо)

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

CJie ввода правильной первой цифры кода, то на попытку ввести правильную*

31f

Методы

описания

синтеза

цифровых

автоматов

вторую цифру автомат либо не будет реагировать, оставаясь в сосгояпии ^6.

либо будет воспринимать ее как неправильную первую цифру (при этом сра-

ботаег сигнализация), если ич состояния

q^^

автомат перешел в состояние д^

по дуге jr^. Индивидуум же. набирающий код, остался бы при этом в полном

неведении, отчего авгомат столь иеделнкапю обошелся с ним. Поэтому преду-

сматриваем q^ -*<?2 по условию х^х^х^ (аналогично

д/1Я

д^, -^q^: -^iT^.v^).

PiK. 12.10.

раф

riepevu.ioii

звюмага

М)ра

Сброс автомата в начальное состояние при вюиочеиии питания можно

обеспечить следующим образом. Заметим, что из двух вершин графа (кроме

?;) выходят дуги к вершине (/,, по одному и тому же условию х,, («дверь

открыта»). Так нельзя ли обеспечить х, =

при включсггин писания даже в

том случае, когда дверь заперта? Сделаем так: пусть при иодаче пшаиня

срабатывает одиовибратор, выход которого соединим с одттм из

HXOJVOB

дизъюнктора, а на другой вход подадим иепосредстветю сигнал D с кон-

такта двери. Выход схемы и даст требуемый управляющий сигнал .v,.

Имея граф переходов автомат, переходим к составлению таб.мнны пе-

реходов (выходов), предварительно определив число трииеров Л', («на-

мять» автомата) и закодировав сосюяния

A', = |logjA'„r,

где Л',^ — число состояний, я скобки [ Y означают ближайшее целое свер-

ху (в нашем случае Л", = 3 ):

316