|
|
12.4. Соединение автоматов |
|
|
|
Т а б л и ц а 12.5 |
|
|
Ух |
У'г |
|
у' |
У\ |
Уг |
|
y'l |
Уг |
Уг |
Здесь, |
например, |
5(qj, Jc,) = 5((Й2, с,), х,) = (5, (й,, JT, ), бг (Ci, J^i)) = |
—г |
1 |
'' |
1 |
' ' l ^ l |
«1 |
1 |
|
''J'"3 |
|
|
|
|
Та б л и ц а 12.6 |
•?! |
<?] |
<?< |
« 5 |
9 6 |
''s'-i |
6,C| |
6|C2 |
6jC| |
62C2 |
6,C| |
V 2 |
6,C, |
'г''! |
6,c, |
Функпия выходов X задается таблицей 12.7.
|
|
|
|
|
Т а б л и ц а 12.7 |
|
'/1 |
Яг |
Я} |
Я> |
9s |
Яь |
«1 |
>т 1 |
Уг |
Уг |
Уу |
Уг |
y-i |
'= |
Уг |
У1 |
Уг |
У\ |
Уг |
Ух |
Здесь, например, 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 е 6 2 ! ; |
|
Х = Х; |
|
|
фугжция переходов: |
Y = Y; |
|
|
|
|
|
5(У X JT) = (5, ( 0 >; X), 5; (бз X Х,, ( й |
X X))); |
функция выходов X: |
|
|
|
М</,„,*,) = >^2(9,„2Д|(9тГ.*,)).ИЛИ Х{в^Х) = Х^(в2 |
>iXx(Q, X X)) . |
в качестве примера |
рассмотрим те же автоматы |
S, |
н S2, заданные |
таблицами 12.8, 12.9. |
|
|
|
12 Методы описанип и синтеза цифровых автоматов
|
|
|
Т а б л и ц а 128 |
|
|
|
1 а б л и ц а 129 |
|
|
', |
6, |
|
'ъ/л |
|
", |
|
С, |
^2 |
|
|
*| 1У\ |
|
|
|
•••Jy, |
••2/л |
|
|
»2 |
hly\ |
|
h/y, |
|
" 2 |
|
•=11Уг |
< • , / > ' , |
|
Результирующим апюматом 1Юслелователыю1о соединения автомаюв |
S| |
и 5 ; |
будетавтома! ,V. для Koiopoio |
|
|
|
|
|
|
е |
= {(А,,e,),(/),,t, ),(/>,.C|),(*j,Cj),(A„<;|),(*3.С; |
)) = {</,. •</„); |
|
Функция переходов 5 определяется таблицей 12.10. |
I |
а б л м и а 12 1(1 |
|
|
|
Ч, |
Чг |
Чг |
|
Ч, |
_ j |
' / 1 |
|
|
Х; |
|
* , ' • , |
IV; |
Ь,г, |
|
|
* 2 < - : |
/м-, |
|
•ъ |
|
Ь,е, |
|
* , < • |
, |
|
|
|
|
|
Здесь, например, |
|
|
|
|
|
|
|
|
|
5(?,.->c,) = S ( ( / ' , . ' i ) . |
v , ) - ( 8 , ( / ) , , v , ) . 5 J ( ^ , , X , x ( / , J , , , ) ) - |
|
|
|
= ( ^ . f i , ( Г | , > • г ) ) = ( / J | , t J ) = ( / J . |
|
|
|
Функция выходов X определяется табл. 12,11. |
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
1211 |
|
|
|
Ч, |
Чг |
41 |
4t |
|
Ч^ |
|
Чк |
|
|
.Т| |
У, |
У2 |
J'2 |
У: |
|
У 2 |
|
У1 |
|
|
^1 |
J'l |
.•'2 |
V'l |
Уг |
|
У, |
|
у-1 |
|
Здесь, |
например, |
|
Х((/,, ,i|) = X((A2,c,),X|) = Х2(С|. Х, х(Л,,,\:|)) = |
|
Соединение автомаюв с обрагиой связью представлено па рис. 12.7, е. |
В |
этом |
случае |
автоматы |
S^-{Q^^X^,Y^,b^,W |
и |
.Sj ={(?;, F,, K j . S i . Х , | . |
|
|
|
Имеется |
некоторый функционш!ьиый преобразователь у, являющийся ав |
томатом |
без памяти, коюрый реализует отображение у: X x F , -^Х^. В |
этом случае, по крайней мере, один из автоматов S, или S, должен |
быть |
автоматом Мура. Пусть ,S'j - - автомат Мура, у которого К^ = X^iQi). |
Тогда |
12 4. Соединение автоматов
результирующим автоматом такого соединения с обратной связью будет новый автомат S = {Q, X, Y, 5, X), для которого
f = а X Sz = {<7„ = (<7,„1, <7.,2) I <7»| е а , ?„2 е б г } ;
Х = Х; Y = 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.
|
|
Т а б л и ц а 12.12 |
|
Т а б л и ц а |
12.13 |
|
I'l |
*; |
*, |
|
"1 |
''г |
|
|
|
|
/'1 |
Ь,/У, |
ki/yi |
bjy, |
|
С[ |
С; |
Г2 |
' ь / л _ |
*,Av, |
Ь./Уг |
У1 |
f i |
С г |
|
|
|
|
Уг |
сг |
«2 |
|
|
|
|
У} |
'•i |
f| |
Функциональный Преобразователь у задан таблицей 12.14
|
|
Т а б л и ц а |
12.14 |
|
^i |
^2 |
Jfl |
V| |
P I |
Pi |
Pi |
"г |
Рг |
Р2 |
PI |
Резулыирующим автоматом соединения с обратной связью будет ав томат S = {Q, X, Y, 5, X}, для которого
У = В х С = {(/'1.^-1 ).(*!.'•2).(*2.С,),(*2,С2),(*з.С,).(*З.С2)} = {9|.92 •.•9б};
1' = {Л.>'2.>'з}-
функция переходов 5:QxX-*Q |
определяется следующим образом |
(табл. 12,15): |
|
|
12 Memodhi OIHN ami. |
|
I цифровых автоматов |
|
|
|
|
|
|
|
|
Таб л и п а 12 15 |
|
</l |
4l |
Яг |
44 |
|
1^ |
'/. |
" l |
h,c, |
|
l,,c. |
h,C, |
|
h,c, |
Ait4 |
ъ |
b,c, |
|
h^cj |
^iW |
, |
b,c, |
h,c. |
V j |
b,c, |
|
Л,С2 |
b.. |
|
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 |
_'Л |
44^ _ |
'/1 |
'/6 |
г. |
1-, |
* 2 |
. ''} |
|
|
|
|
|
|
v. |
г, |
.1'2 |
>*, |
|
|
. V, |
1'1 |
_1^^: |
[^ .''I |
|
|
13 л о м случае, например.
M'?,.V|)-X((/.,,r,). г,)-Х,(А,,т(л-,,Х,(с,))).
=? ^ , f Л , , y ( V , . l • | ) ) - X | ( / ) , , / 7 , ) = _V2.
12.5.Ciiiiic) управляющею автомата
По функциональному начиачсиию основные устройства ЭВМ можно условно разделить ма две каюгорни: операционные устройство (ОУ) и управляющие устройства ( У У ) . Отдельные части операцнониото устройст ва функционирукм в 01гре;1елегтой последовательности в зависимости or алгоритма выпо^тяемой операции. Управляющее устройство по сигишгу операции вырабатывав! необходимые сигналы, но которым запускается выполнение заданной мнкросчшрацнн. Совокупность микроопераций, объе диненных а/п'оригмом операции. состав;гяет микроиро! рамму операции, которая, в свою очередь, являемся связующим звеном между коман;юй (ко дом операции) и операциоппым устройством (аппаратными средствами), предназначенным для преобраишання информации.
12 5 Синтез управляющего автомата
Управляющее устройство состоит из отдельных логических схем, вы рабатывающих управляющие сигналы в заданной последовательности. Та кое управляющее устройство можно рассматривать как управляющий ав томат типа Мура или Мили.
Чтобы 1юстроить схему угтравляющего автомата, нужно задать микро программу рабо1ы операционного устройства. Микропрограмма может бьпь чадана в виде граф-схемы (рис. 12.8, а). Микропрограмма выполняет ся при начальном ус;говии И = I. Условия определяют последовательность вl.мк)JПleиия микроопераций. Посмотрим, как связать граф-схему микроnpoi раммы с арюматом Мура или Мили.
Vz?2,=Zj
1'ис. 12.8. Гра(|)-схема операционного aaxoMaia (а), i раф-переходев iimoMata Мура {в), граф-переходов ав-roMaia Мили (в)
)\^ш авюмак! Мура выходной сигнал зависит только от внутреннего сосюямия. I.e. в нашем случае v = F{Q). Поэтому каждая операторная
И я Ла/тин! Мсюдупсскиеукагаиия к лабораюрнымра&тгам. Ч, 2, МВТУ, 1987.С 14-16.
12 Методы описания и синтеза цифровых авточитов
вершина граф-схемы алгоритма должна быть отмечена символом исходно го состояния автомата 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 ( r e . условия 2,): v ^ F ( P . Z ) . PaiMeiKa граф-схемы для авгомата Мили дела ется иначе, чем для автомага Мура. Символом t/y отмечакпся вход нерпой вершины графа, следующей за начальной, и вход конечной верншны. Вы
ходы |
других онера1орги>1х |
вернин! |
отмечаются симво;гом </,, |
! 1а |
рис. |
12.8. с/ автома! |
Мили огмемеп символами, взяпимн и скобки |
! раф |
переходов автомат |
Мили |
ноказаи па |
рис, 12.8. «. В авюмакгх Мили |
фу!)кции выходюв, tro коюрым вырабатываются сигналы микрооисратгп. определяются но (|)ормуле
' • ; ~- V ( / , ( V Z ^ ) .
I к
где q, —- состояние автомага, со11ровождающегося выработкой cm нала г^ : 7j( — логическое условие, oпpeдeJrяющee выработку сн1нала v^ при пере ходе автомата из состояния с/,.
В случае безусловною перехода автомата из сосюяния </, стнал v^
определяется только згшченнем q^.
После построения аиюмата Мура или Мили фуикииопированне управляющего автомата представляют в виде таблиц переходов и вы ходов. Для ЭТ010 проводят кодирование состояний автомата двоичггыми кодами, определяют тин и количество три1 геров, Затем 1Ш таблице пе реходов устанавливают значения сигналов на входах триггеров, при которых осуществляются переходы; определяют функции возбуж.чеиня
/2 6 Логическое проектирование управляющего автомата
триггеров и проводят их минимизацию (упрощение). По найденным выражениям строится схема управляющего автомата на выбранных )лемеи lax.
12.6.Логическое проектирование управляющего автомата
PacCMoipMM мегодику синтеза управляющего автомата на конкретном примере. Предположим, что требуется создать логическую схему для управления цифровым замком. Срабатывание реле замка происходит в ре- !yju>iaie иоомередного набора комбинации цифр (трех из десяти кнопок) в cipoioi'i IrocJreдoвaleльнocти. Возвращение автомата в исходное состояние происходиf ири срабатывании двери в момент ее приоткрывания. Синтез авюмаи! проводшся в necKOJibKo этапов .
L A i i i u i in условия задачи. Очевидно, схема должна содержать не 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 ирепко
12 Методы описания и синтеза цифровых автоматов
Входными сигналами мог>т быть сигналы, поступающие от любой из Ю кнопок. Для простоты принимаем, что автомат реагирует избирательно
|
|
|
|
|
|
|
лишь на перечисле11иые си! налы. |
|
|
|
М н о ж е с т в о |
в ы х о д н ы х |
с и г н а л о в |
{/,): |
|
/| |
— сигнал, |
приволягции в состояние «открыто» реле |
замка (мри |
У| - О считаем, что автомат iie разрешает замку открываться); |
|
/з |
— «сигнал TpCBOi н». он может возбуждать схему запуска звуково! о |
генератора (попросту говоря, вюгючмть сит иализацию). |
|
М н о ж е с т в о |
л о г и ч е с к и х |
у с л о в и й |
п е р е х о д о в |
{г,}; |
Z| — про1пел ли cHi пал |
г, ? |
|
|
|
2, |
- прошел JH1 cvri нал |
v, ? |
|
|
|
2, |
— прошел ли сигнал |
v, ? |
|
|
|
7^ — открыта ли дверь?
Ввиду очевидной связи между условиями и входными сигналами бу дем сами условия обозначать так же, как и входные сигналы (л-,}.
2. Рйзработка алгоритма функционирования автомата.
Алгоритм функционирования автомата В1юлне поня1ен: переход в со стояние OTKpbiToio замка ироисходиг в гом и только в том случае, когда введены верные цифры кода.
Введем операторы. кои>рые потребуются для заштси алгоритма:
V, " |
ожидать ввода сигнала 1-й 11ифры кода; |
|
1'2 — ожидать ввода сит нала 2-й цифры кода; |
|
г, - |
ожидать ввода CHI нала 3-й цифры кода; |
|
V., |
выдать выходной сипгал /, = I; |
|
Vj — выдать вьгход!ЮЙ «сигнал тревоти» /з - |
! . |
В дальнейшем станет ясно, зачем операторы |
v,,...,r, определяются |
столь стран!юй, на первый вз1 ляд, формулировкой.
Ввиду простоты алгоритма перейдем сразу к состояник! ею графсхемы (ГСА) без записи микропрограммы (рис. 12.9).
Операторы v,,...,v^, указывают на «зависание» автомата, т.е. ожтгдание ввода очередной информации (рис. 12.9 — траф-схема ajnopHiMa функционирования •электронного замка).
П р и м е ч а н и е i СЛ не обратас! переход автомата в начальное сосюягтне ш иеонрсделеиного сосгояння.
12 6 Логическое проектирование управляющего автомата
© ®
Рис. 12.9. 1 раф-схема алюртма ф)11К!1НчиироRiUHifl i.iieKipoiinoH) iaMKa
3. Сишез цифровою автомата.
С'ишеч ироводтся но одному из двух вариантов. С и н т е з а в т о м а г а М у р а .
В с()01ве1С1Вии с зем. что выходной сигнал в автомате Мура чавист nuihKo or состояния, но не зависит от входного сигнала, выполним отметку ГСЛ по следующим правилам:
—символом ^1) отмечаем вершины «Начало» и «Конец»;
—• отмечаем все операторные вершины символами ij,, ^^ и т. д.;
—различные вершины отмечаем различными символами. Символы q, обозначают состояние автомата.
Следуя or вершины к вершине всеми возможными путями, подучаел граф переходов автомата Мура (рис. 12.10).
Состояние i/й является любым нештатным (неопределенным), в которо) попадает автомат при сбое или выключении питания. Если сбой наступил по CJie ввода правильной первой цифры кода, то на попытку ввести правильную*
12 Методы описания и синтеза цифровых автоматов
вторую цифру автомат либо не будет реагировать, оставаясь в сосгояпии ^6. либо будет воспринимать ее как неправильную первую цифру (при этом сработаег сигнализация), если ич состояния q^^ автомат перешел в состояние д^ по дуге jr^. Индивидуум же. набирающий код, остался бы при этом в полном неведении, отчего авгомат столь иеделнкапю обошелся с ним. Поэтому преду сматриваем q^ -*<?2 по условию х^х^х^ (аналогично д/1Я д^, -^q^: -^iT^.v^).
PiK. 12.10. 1 раф riepevu.ioii звюмага М)ра
Сброс автомата в начальное состояние при вюиочеиии питания можно обеспечить следующим образом. Заметим, что из двух вершин графа (кроме ?;) выходят дуги к вершине (/,, по одному и тому же условию х,, («дверь открыта»). Так нельзя ли обеспечить х, = 1 при включсггин писания даже в том случае, когда дверь заперта? Сделаем так: пусть при иодаче пшаиня срабатывает одиовибратор, выход которого соединим с одттм из HXOJVOB дизъюнктора, а на другой вход подадим иепосредстветю сигнал D с кон такта двери. Выход схемы и даст требуемый управляющий сигнал .v,.
Имея граф переходов автомат, переходим к составлению таб.мнны пе реходов (выходов), предварительно определив число трииеров Л', («на мять» автомата) и закодировав сосюяния
A', = |logjA'„r,
где Л',^ — число состояний, я скобки [ Y означают ближайшее целое свер
ху (в нашем случае Л", = 3 ):
