Лупал А.М. Теория автоматов (часть 2)
Подождите немного. Документ загружается.
84
Qt Qt+
2
1
3
4
1
1
0
D
V
b
b
b
b
b
=
M
(7.9)
ãäå ýëåìåíòû b
1
è b
2
ìîãóò ïðèíèìàòü ëþáûå çíà÷åíèÿ, êðîìå êîìáèíà-
öèè b
1
=b
2
=1, ò. å. b
1
b
2
= 0, à ýëåìåíòû b
3
è b
4
äîëæíû óäîâëåòâîðÿòü
óñëîâèþ
b
3
b
4
= 0, ò. å. íåäîïóñòèìî, ÷òîáû b
3
= 0, à b
4
= 1 îäíîâðåìåí-
íî.
Ôóíêöèÿ âîçáóæäåíèÿ DV-òðèããåðà èìååò âèä
q
ýë
(t) = q
(1)
(t) q
(2)
(t) ∨
q
(2)
(t) Q(t) = Q(t+1)
èëè èíà÷å
Q(t+1) = D(t)V(t) ∨
V
(t)Q(t).
7.3. Ýëåìåíòàðíûé àâòîìàò ñ ÷åòûðüìÿ âõîäíûìè ñèãíàëàìè
Ýëåìåíòàðíûé àâòîìàò À
7
, ãðàô ïåðåõîäîâ êîòîðîãî ïðåäñòàâëåí íà
ðèñ. 7.20, èñïîëüçóåò â êà÷åñòâå âõîäíîãî àëôàâèòà àëôàâèò V
4
= {v
1
, v
2
,
v
3
, v
4
}, ñîäåðæàùèé âñå ÷åòûðå àáñòðàêòíûõ âõîäíûõ ñèãíàëà îïèñû-
âàåìîé ìîäåëè. Çàêîäèðîâàâ ñèìâîëû âõîäíîãî àëôàâèòà â ñîîòâåò-
ñòâèè ñ òàáë. 7.11, ïîñòðîèì íà îñíîâàíèè ðèñ. 7.20, òàáë.7.2 è 7.11 êî-
äèðîâàííûé ãðàô ïåðåõîäîâ àâòîìàòà (òàáë. 7.12) è ìàòðèöó ïåðåõîäîâ
(7.10) ýòîãî àâòîìàòà.
Qt Qt+
(0) (1)
0
1
1
0
qq
b
b
b
b
=
M
(7.10)
v
4
v
1
v
1
v
4
v
3
v
3
v
2
v
2
c
2
c
1
00
00
01
01
0
1
10
10
11
11
Ðèñ. 7.20
Ðèñ. 7.21
85
Òàáëèöà 7.11 Òàáëèöà 7.12
Àíàëèçèðóÿ ïåðåõîäû àâòîìàòà À
7
ïî òàáë. 7.12, ïðèõîäèì ê çàê-
ëþ÷åíèþ, ÷òî îí ôóíêöèîíèðóåò îäíîâðåìåííî êàê òðèããåð RS (ïðè
íóëåâûõ è ïðîòèâîïîëîæíûõ çíà÷åíèÿõ âõîäíûõ ñèãíàëîâ) è êàê òðèã-
ãåð Ò (ïðè q
(0)
= q
(1)
= 1). Ïîýòîìó àâòîìàò À
7
ñ÷èòàåòñÿ óíèâåðñàëü-
íûì òðèããåðîì òèïà JK, ãäå âõîäîì J ñ÷èòàåòñÿ âõîä q
(1)
, à âõîäîì K
âõîä q
(0)
.
Ôóíêöèÿ âîçáóæäåíèÿ òðèããåðà JK èìååò âèä
q
ýë
(t) = q
(1)
(t)
Q
(t) ∨
q
(0)
(t) Q(t) = Q(t+1)
èëè èíà÷å
Q(t+1) = J(t)
Q
(t) ∨
K
(t)Q(t).
Ñòðóêòóðíàÿ ñõåìà òðèããåðà ðåàëèçóåòñÿ îáû÷íî íà áàçå òðèããåðà òèïà
RS.  ýòîì ñëó÷àå âõîäû q
(0)
(t) è q
(1)
(t) RS-òðèããåðà áóäóò èìåòü çíà÷å-
íèÿ, îïðåäåëÿåìûå ñëåäóþùèìè ëîãè÷åñêèìè âûðàæåíèÿìè:
q
(0)
RS
(t) = R(t) = K(t) Q(t),
q
(1)
RS
(t) = S(t) = J(t)
Q
(t).
Äîñòàòî÷íî øèðîêîå ïðèìåíåíèå â öèôðîâûõ ñõåìàõ íàõîäèò ýëå-
ìåíòàðíûé àâòîìàò, ïîëó÷åííûé ïóòåì èçáûòî÷íîãî êîäèðîâàíèÿ âõîä-
íûõ àáñòðàêòíûõ ñèãíàëîâ àâòîìàòà À
7
, ïðåäñòàâëåííîãî â òàáë. 7.13.
Ëþáàÿ êîìáèíàöèÿ, ñîäåðæàùàÿ äâà åäèíè÷íûõ çíà÷åíèÿ ýëåìåí-
òàðíûõ ñòðóêòóðíûõ ñèãíàëîâ, ÿâëÿåòñÿ çàïðåùåííîé.
Òàáëèöà 7.13 Òàáëèöà 7.14
G
G
LG
G
L
L
L
!
L
LG
G
G
L
L
L
!
L
"
G
G
G
86
Íà îñíîâàíèè òàáë. 7.13 è 7.2 è ðèñ. 7.20 ïîëó÷èì êîäèðîâàííûé
ãðàô ïåðåõîäîâ àâòîìàòà (ðèñ. 7.22), êîäèðîâàííóþ òàáëèöó ïåðåõî-
äîâ (òàáë. 7.14) è ìàòðèöó ïåðåõîäîâ (7.11) ýòîãî àâòîìàòà.
Qt Qt+
(0) (1) (2)
11
22
00
0
0
00
qqq
b
bb
bb
b
=
M
(7.11)
Àíàëèçèðóÿ ïåðåõîäû àâòîìàòà ïî òàáë. 7.14, ìîæíî çàìåòèòü, ÷òî
ñèãíàëû q
(0)
è q
(1)
ðàáîòàþò àíàëîãè÷íî ñèãíàëàì R è S òðèããåðà òèïà
RS, à ñèãíàë q
(2)
èçìåíÿåò ñîñòîÿíèå àâòîìàòà íà ïðîòèâîïîëîæíîå àíà-
ëîãè÷íî âõîäíîìó ñèãíàëó òðèããåðà Ò.  ñâÿçè ñ ýòèì äàííûé ýëåìåí-
òàðíûé àâòîìàò ïîëó÷èë íàçâàíèå ñ÷åòíîãî òðèããåðà ñ ðàçäåëüíîé óñ-
òàíîâêîé èëè òðèããåðà òèïà RST.
000
000
001
010
01
001
100
100
010
Ðèñ. 7.22
q
(0)
q
(1)
q Q
1
1
1
1
Ðèñ. 7.23
87
Ëîãè÷åñêîå âûðàæåíèå äëÿ ôóíêöèè âîçáóæäåíèÿ ýòîãî òðèããåðà ìî-
æåò áûòü ïîëó÷åíî íà îñíîâàíèè òàáë. 7.14 ñ ïîìîùüþ äèàãðàììû Âåé-
÷à (ðèñ. 7.23) è áóäåò èìåòü âèä
Q(t+1) = q
ýë
(t) = q
(1)
(t) ∨
q
(0)
(t)
q
(2)
(t)Q(t) ∨ q
(2)
(t)
Q
(t). (7.12)
Èëè èíà÷å Q(t+1) = S(t) ∨ T(t)
Q
(t) ∨
R
(t)
T
(t)Q(t).
Ñòðóêòóðíàÿ ñõåìà RST-òðèããåðà ðåàëèçóåòñÿ îáû÷íî íà áàçå RS-
òðèããåðà.
88
8. ÒÅÕÍÈ×ÅÑÊÀß ÐÅÀËÈÇÀÖÈß ÝËÅÌÅÍÒÀÐÍÛÕ
ÀÂÒÎÌÀÒÎÂ
Äëÿ óñòîé÷èâîé ðàáîòû àâòîìàòà íåîáõîäèìà åãî ñèíõðîíèçàöèÿ è
ââåäåíèå äîïîëíèòåëüíûõ ñõåì (êîíúþíêòîðîâ) [5]. Îáû÷íî äîïîëíè-
òåëüíûå ñõåìû è âõîäû ñèíõðîíèçèðóþùèõ ñèãíàëîâ ïðåäóñìàòðèâà-
þòñÿ â ñàìîì ýëåìåíòå ïàìÿòè ïðè åãî òåõíè÷åñêîé ðåàëèçàöèè. Íà
îñíîâå õàðàêòåðèñòè÷åñêîãî óðàâíåíèÿ RS-òðèããåðà
Q(t+1) = S(S(S(
R
âõ
(t)), Q(t)), S(
S
âõ
(t)))
ìîæíî ïîñòðîèòü àñèíõðîííóþ ñõåìó ýòîãî òðèããåðà íà ýëåìåíòàõ Øåô-
ôåðà ñ óïðàâëåíèåì ïî âõîäàì, ïðåäñòàâëåííóþ íà ðèñ. 8.1.
Âî èçáåæàíèå ãîíîê [5] àñèíõðîííûå òðèããåðû îáû÷íî íå èñïîëüçó-
þòñÿ â êà÷åñòâå ýëåìåíòîâ ïàìÿòè â ñòðóêòóðíûõ àâòîìàòàõ. Ïîäêëþ-
÷àÿ ê âõîäàì àñèíõðîííîãî òðèããåðà ñõåìó óïðàâëåíèÿ, ñîñòîÿùóþ èç
ëîãè÷åñêèõ ýëåìåíòîâ èñïîëüçóåìîãî áàçèñà, ìîæíî ïîëó÷èòü ñèíõðîí-
íûé (òàêòèðóåìûé) òðèããåð. Íà ðèñ. 8.2, à, á ïðèâåäåíà ñõåìà ñèíõðîí-
íîãî RS-òðèããåðà è åãî ëîãè÷åñêàÿ ñòðóêòóðà, â êîòîðûõ ïóíêòèðîì îáî-
çíà÷åíû ïîáî÷íûå àñèíõðîííûå âõîäû. Íà ðèñ. 8.2, â ïðèâåäåíî óñëîâ-
íîå èçîáðàæåíèå òàêîãî òðèããåðà. Âõîäû S è R èíôîðìàöèîííûå (âõî-
äû ôóíêöèé âîçáóæäåíèÿ), à âõîä C ñèíõðîíèçèðóþùèé (òàêòîâûé).
Q
S
R
Q
Q
S
R
Q
S
T
R
Ðèñ. 8.1
Q
C
C
S
S
R
R
q
(
0
)
q
(
1
)
Q
S
a
S
a
R
a
R
a
Q
Q
S
T
R
R
C
S
S
T
R
R
C
a
a
à) á) â)
Ðèñ. 8.2
89
Èçìåíåíèå ñîñòîÿíèÿ òàêîãî òðèããåðà ìîæåò ïðîèçîéòè òîëüêî ïðè
Ñ = 1. Ïîáî÷íûå âõîäû
S
a
è
R
a
òðèããåðà ïðåäíàçíà÷åíû äëÿ àñèíõðîí-
íîé óñòàíîâêè òðèããåðà â ñîñòîÿíèå 0 è 1, ìèíóÿ èíôîðìàöèîííûå è òàê-
òèðóþùèé âõîäû. Ôóíêöèîíèðîâàíèå â ýòîì ñëó÷àå ñîîòâåòñòâóåò àñèí-
õðîííîìó RS-òðèããåðó ñ èíâåðñíûì óïðàâëåíèåì. Ïðè ñèíõðîííîé ðà-
áîòå íà ïîáî÷íûõ âõîäàõ äîëæíà ïîääåðæèâàòüñÿ íåéòðàëüíàÿ êîìáè-
íàöèÿ ñèãíàëîâ (
S
a
=
R
a
= 1).
Ïîìèìî ñèíõðîíèçàöèè äëÿ óñòðàíåíèÿ ãîíîê â àâòîìàòàõ èñïîëüçó-
åòñÿ äâîéíàÿ ïàìÿòü.  ýòîì ñëó÷àå âñå ýëåìåíòû ïàìÿòè ñòðóêòóðíî-
ãî àâòîìàòà äîëæíû áûòü îðãàíèçîâàíû â âèäå äâóõòàêòíûõ (äâóõñòó-
ïåí÷àòûõ) ñõåì. Îíè ñòðîÿòñÿ íà îñíîâå äâóõ ñèíõðîííûõ òðèããåðîâ,
ñîåäèíåííûõ ïîñëåäîâàòåëüíî. Ñèíõðîíèçèðóþùèå ñèãíàëû ïîñòóïàþò
íà ýòè òðèããåðû â ñîîòâåòñòâèè ñ óñëîâèÿìè îðãàíèçàöèè òàêèõ ñèãíà-
ëîâ â ñõåìàõ ñ äâîéíîé ïàìÿòüþ: íà âõîä C ïåðâîãî òðèããåðà ïîñòóïàåò
ïðÿìîé ñèãíàë, à íà âõîä C âòîðîãî òðèããåðà èíâåðñíûé. Äâóõòàêòíàÿ
ñõåìà RS-òðèããåðà, åå ëîãè÷åñêàÿ ñòðóêòóðà è óñëîâíîå èçîáðàæåíèå
ïðèâåäåíû ñîîòâåòñòâåííî íà ðèñ. 8.3, à, á è â.
Q
S
M
C
S
R
S
a
R
a
Q
Q
S
a
R
a
S
S
SSS
TT
RRR
RR
C
C
C
Q
S
TT
R
C
S
a
R
a
à)
á)
â)
Ðèñ. 8.3
90
Ïåðâûé òðèããåð â äâóõòàêòíîé ñõåìå íàçûâàåòñÿ âåäóùèì M, à âòî-
ðîé âåäîìûì S (Ì master (õîçÿèí), S slave (íåâîëüíèê)).
Ïîñêîëüêó RS-òðèããåð óñòîé÷èâ ïî îòíîøåíèå ê äëèòåëüíîñòè âõîä-
íîãî ñèãíàëà, íà åãî îñíîâå öåëåñîîáðàçíî ñòðîèòü ðàçëè÷íûå âàðèàíòû
ñõåì ýëåìåíòàðíûõ àâòîìàòîâ. Ðàññìîòðèì ðåàëèçàöèþ òðèããåðîâ ðàç-
ëè÷íûõ òèïîâ íà îñíîâå ñèíõðîííîãî RS-òðèããåðà.
Íà ðèñ. 8.4 ïðèâåäåíû ñõåìû S- è R-òðèããåðîâ, ôóíêöèîíèðóþùèõ â
ñîîòâåòñòâèè ñ òàáë. 7.8.
Ôóíêöèîíàëüíûå ñõåìû S-òðèããåðà è R-òðèããåðà îäèíàêîâû è êîíê-
ðåòíûé òèï òðèããåðà îïðåäåëÿåòñÿ íàèìåíîâàíèåì âõîäíûõ è âûõîä-
íûõ êàíàëîâ. Íà ðèñ. 8.4 îáîçíà÷åíèÿ âõîäîâ òðèããåðà áåç ñêîáîê ñîîò-
âåòñòâóþò òðèããåðó òèïà S, à îáîçíà÷åíèÿ â ñêîáêàõ òðèããåðó òèïà R.
Íà ðèñ. 8.5 ïðèâåäåíà ôóíêöèîíàëüíàÿ ñõåìà Å-òðèããåðà, ðàáîòàþ-
ùåãî â ñîîòâåòñòâèè ñ òàáë. 7.8.
 ýòîé ñõåìå ïðè îäíîâðåìåííîì ñî÷åòàíèè íà âõîäàõ S = R = 1
îáåñïå÷èâàåòñÿ ðåæèì õðàíåíèÿ èíôîðìàöèè è ñîñòîÿíèå òðèããåðà íå
ìåíÿåòñÿ.
Ðàññìîòðèì òåõíè÷åñêóþ ðåàëèçàöèþ òðèããåðîâ òèïà D, DV, T, JK,
ñèíòåçèðóÿ èõ êàíîíè÷åñêèì ìåòîäîì ñòðóêòóðíîãî ñèíòåçà, èñïîëüçóÿ
â êà÷åñòâå ýëåìåíòà ïàìÿòè òðèããåð òèïà RS.
Q(
)
Q
C
S(R
)
R
(S)
Q(Q
)
Ðèñ. 8.4
C
S
R
Q
Ðèñ. 8.5
91
Ñòðóêòóðíàÿ ñõåìà ëþáîãî òðèããåðà íà áàçå òðèããåðà òèïà RS èìååò
âèä, ïðåäñòàâëåííûé íà ðèñ. 8.6.
1. Ñèíòåç òðèããåðîâ òèïà D è DV. D-òðèããåð îñóùåñòâëÿåò ïåðåõîäû
èç îäíîãî ñòðóêòóðíîãî ñîñòîÿíèÿ â äðóãîå â ñîîòâåòñòâèè ñ êîäèðîâàí-
íîé òàáëèöåé ïåðåõîäîâ 8.1 Íà îñíîâå òàáë. 8.1 è ìàòðèöû ïåðåõîäîâ
RS-òðèããåðà (7.3) ìîæíî ñîñòàâèòü êîäèðîâàííóþ òàáëèöó ôóíêöèè âîç-
áóæäåíèÿ D-òðèããåðà (òàáë. 8.2).
Òàáëèöà 8.1 Òàáëèöà 8.2
Èç òàáë. 8.2 ìîæíî ñ ïîìîùüþ äèàãðàììû Âåé÷à (ðèñ. 8.7) íàéòè
ëîãè÷åñêîå âûðàæåíèå äëÿ ôóíêöèè âîçáóæäåíèÿ R è ñ ïîìîùüþ äðó-
ãîé äèàãðàììû Âåé÷à (ðèñ. 8.8) äëÿ ôóíêöèè âîçáóæäåíèÿ S.
R =
D
è S = D.
Òàêèì îáðàçîì, ôóíêöèîíàëüíàÿ ñõåìà D-òðèããåðà íà îñíîâå RS-
òðèããåðà äîëæíà ñîñòîÿòü èç RS-òðèããåðà ñ äîïîëíèòåëüíûì èíâåð-
òîðîì íà âõîäå R. Ëîãè÷åñêàÿ ñòðóêòóðà òàêîãî D-òðèããåðà è åãî
óñëîâíîå îáîçíà÷åíèå ïðèâåäåíû íà ðèñ. 8.9, à è á.
Q
x
R
KC
ïàìÿòü
(òðèããåð)
RS-
S
Ðèñ. 8.6
,
45 45
>
>
Q
D
1
0
0
b
Q
D
1
0
b
Ðèñ. 8.7
Ðèñ. 8.8
92
Ïîñêîëüêó DV-òðèããåð ïðåäñòàâëÿåò ñîáîé ìîäèôèêàöèþ D-òðèããå-
ðà, åãî ñõåìó ìîæíî ïîëó÷èòü ïðåîáðàçîâàíèåì ïîñëåäíåãî ïóòåì äî-
áàâëåíèåì âõîäà V, êîòîðûé äîëæåí áûòü ëîãè÷åñêè ñâÿçàí îïåðàöèåé
È ñ óïðàâëÿþùèì âõîäîì C (ðèñ. 8.10).
2. Ñèíòåç òðèããåðà òèïà Ò. Ôóíêöèîíèðîâàíèå T-òðèããåðà çàäàåòñÿ
êîäèðîâàííîé òàáëèöåé ïåðåõîäîâ (òàáë. 8.3).
Òàáëèöà 8.3 Òàáëèöà 8.4
Ïîëüçóÿñü ìàòðèöåé ïåðåõîäîâ RS-òðèããåðà (7.3) è òàáë. 8.3, ñîñòà-
âèì êîäèðîâàííóþ òàáëèöó ôóíêöèé âîçáóæäåíèÿ T-òðèããåðà (òàáë. 8.4).
Èç òàáë. 8.3 ìîæíî ñ ïîìîùüþ äèàãðàììû Âåé÷à (ðèñ. 8.11) íàéòè ëî-
ãè÷åñêîå âûðàæåíèå äëÿ ôóíêöèè âîçáóæäåíèÿ R è ñ ïîìîùüþ äðóãîé
äèàãðàììû Âåé÷à (ðèñ. 8.12) äëÿ ôóíêöèè âîçáóæäåíèÿ S. Ïîëó-
÷èì R = TQ è S = T
Q
, îòêóäà
TQR =
è
QTS =
. Â ñîîòâåòñòâèè ñ
ýòèìè âûðàæåíèÿìè ñõåìà àñèíõðîííîãî T-òðèããåðà áóäåò èìåòü âèä,
ïðåäñòàâëåííûé íà ðèñ. 8.13, à. Íà ðèñ. 8.13, á ïðåäñòàâëåíî óñëîâíîå
îáîçíà÷åíèå àñèíõðîííîãî T-òðèããåðà. Âìåñòî ñõåìû çàäåðæêè äëÿ
îáåñïå÷åíèÿ óñòîé÷èâîé ðàáîòû T-òðèããåðà ìîæíî èñïîëüçîâàòü äâóõ-
ñòóïåí÷àòóþ ñõåìó (ðèñ. 8.14, à).
Q
D
S
D
TT TT
R
C
C
Q
S
S
a
R
R
a
à)
á)
Ðèñ. 8.9
6
45 45
>>
Q
S
D
TT
R
C
C
V
Q
Q
T
1
b
Q
T
1
b
Ðèñ. 8.10 Ðèñ. 8.11
Ðèñ. 8.12
à
à
à
à
à
à
93
 ýòîé ñõåìå ñèíõðîíèçèðóþùèé ñèãíàë
C
, ïîäàâàåìûé íà âòîðîé
òðèããåð, îáðàçóåòñÿ êîíúþíêöèåé z
1
è z
2
(z
1
&z
2
), êîòîðàÿ ðàâíà 1, åñëè
Ñ = 0, è ïåðâûé òðèããåð íå ïåðåáðàñûâàåòñÿ. Òîãäà â ýòîò ìîìåíò âî
âòîðîé òðèããåð ïðîèñõîäèò ïåðåíîñ èíôîðìàöèè.
Óñëîâíîå îáîçíà÷åíèå äâóõòàêòíîãî T-òðèããåðà ïðèâåäåíî íà ðèñ. 8.14, á.
3. Ñèíòåç òðèããåðà òèïà JK. Ðàáîòà JK-òðèããåðà çàäàåòñÿ êîäèðî-
âàííîé òàáëèöåé ïåðåõîäîâ (òàáë. 8.5).
Ïîëüçóÿñü ìàòðèöåé ïåðåõîäîâ RS-òðèããåðà (7.3) è òàáë. 8.5, ñîñòà-
âèì êîäèðîâàííóþ òàáëèöó ôóíêöèé âîçáóæäåíèÿ JK-òðèããåðà (òàáë. 8.6).
Èç òàáë. 8.6 ñ ïîìîùüþ äèàãðàììû Âåé÷à (ðèñ. 8.15) ìîæíî íàéòè
ëîãè÷åñêîå âûðàæåíèå äëÿ ôóíêöèè âîçáóæäåíèÿ S è ñ ïîìîùüþ äðóãîé
äèàãðàììû (ðèñ. 8.16) äëÿ ôóíêöèè âîçáóæäåíèÿ R.
Q
T
Q
S
R
T
T
S
T
TT
C
R
z
2
z
1
Q
C
T
S
a
R
a
Q
à)
á)
Ðèñ. 8.13
à)
á)
Ðèñ. 8.14
à
à