Ïðèêëàäíàÿ òåîðèÿ öèôðîâûõ àâòîìàòîâ
1. ÏÎÁÓÄÎÂÀ ÎÁ'ªÄÍÀÍί
ÃÑÀ
1.1. Ïîáóäîâà
ÃÑÀ
Ïî
îïèñàõ ãðàô-ñõåì, ïðèâåäåíèõ â çàâäàíí³
äî êóðñîâî¿ ðîáîòè, ïîáóäóºìî ÃÑÀ Ã1-Ã5
(ìàë. 1.1-1.5), äîäàâøè ïî÷àòêîâ³ ³ ê³íöåâ³ âåðøèíè ³ çàì³íèâøè êîæíèé îïåðàòîð
Yi îïåðàòîðíîþ âåðøèíîþ, à êîæíó óìîâó Xi - óìîâíîþ.
1.2. Ìåòîäèêà
îá'ºäíàííÿ ÃÑÀ
Ó
ÃÑÀ Ã1-Ã5 º
îäíàêîâ³ ä³ëÿíêè, òîìó ïîáóäîâà àâòîìàò³â çà ÃÑÀ Ã1-Ã5 ïðèâåäå äî
íåâèïðàâäàíèõ àïàðàòóðíèõ âèòðàò. Äëÿ äîñÿãíåííÿ
îïòèìàëüíîãî ðåçóëüòàòó ñêîðèñòàºìîñÿ ìåòîäèêîþ Ñ.².Áàðàíîâà, ÿêà äîçâîëÿº
ì³í³ì³çóâàòè ÷èñëî îïåðàòîðíèõ
óìîâíèõ âåðøèí. Çàçäàëåã³äü ïîì³òèìî
îïåðàòîðí³ âåðøèíè â ïî÷àòêîâèõ ÃÑÀ, êåðóþ÷èñü ñë³äóþ÷èìè
ïðàâèëàìè:
1)
îäíàêîâ³ âåðøèíè Yi â ð³çíèõ ÃÑÀ â³äì³÷àºìî îäíàêîâèìè ì³òêàìè Aj;
2) îäíàêîâ³
âåðøèíè Yi â ìåæàõ îäí³º¿
ÃÑÀ â³äì³÷àºìî ð³çíèìè ì³òêàìè
Aj;
3) ó âñ³õ ÃÑÀ ïî÷àòêîâó âåðøèíó ïîì³òèìî ÿê
À0, à ê³íöåâó - ÿê Ak.
Íà
íàñòóïíîìó åòàï³
êîæí³é ÃÑÀ ïîñòàâèìî
ó â³äïîâ³äí³ñòü íàá³ð çì³ííèõ PnÎ {P1...Pq}, äå q=]log2N[,
N -ê³ëüê³ñòü ÃÑÀ. Îçíà÷óâàëüíîþ äëÿ ÃÑÀ Ãn ìè áóäåìî íàçèâàòè êîí`þíêöèþ Pn=p1eÙ...Ùpqn åÎ{0,1}, ïðè÷îìó p0=ùð, p1=ð. Îá'ºäíàíà ÃÑÀ ïîâèííà çàäîâîëüíÿòè ñë³äóþ÷èì
âèìîãàì:
1)
ÿêùî ÌÊ Ai âõîäèòü õî÷à á â îäíó ÷àñòêîâó ÃÑÀ, òî âîíà âõîäèòü ³ â îá'ºäíàíó ÃÑÀ Ã0,
ïðè÷îìó ò³ëüêè îäèí ðàç;
2)
ïðè ï³äñòàíîâö³ íàáîðó
çíà÷åíü (å1...en), íà ÿêîìó Pq=1 ÃÑÀ Ã0
ïåðåòâîðþºòüñÿ â ÃÑÀ, ð³âíîñèëüíó ÷àñòêîâ³é ÃÑÀ Ãq.
Ïðè îá'ºäíàíí³ ÃÑÀ âèêîíàºìî ñë³äóþ÷³ åòàïè:
-ñôîðìóºìî
÷àñòêîâ³ ÌÑÀ Ì1
- Ì5, ùî â³äïîâ³äí³ ÃÑÀ Ã1 - Ã5;
-
ñôîðìóºìî îá'ºäíàíó ÌÑÀ Ì0;
-
ñôîðìóºìî ñèñòåìè äóæêîâèõ
ôîðìóë ïåðåõîäó ÃÑÀ Ã0;
-
ñôîðìóºìî îá'ºäíàíó ÃÑÀ Ã0.
1.3. Îá'ºäíàííÿ
÷àñòêîâèõ ÃÑÀ
×àñòêîâ³
ÌÑÀ Ì1-Ì5
ïîáóäóºìî ïî ÃÑÀ Ã1-Ã5
(ìàë.1.1)
â³äïîâ³äíî. Ðÿäêè ÌÑÀ â³äì³òèìî âñ³ìà ì³òêàìè Ai, ùî
âõîäÿòü äî ÃÑÀ, êð³ì ê³íöåâî¿ Ak.
ÏÎ×ÀÒÎÊ A0
1
0 X1 1
2
A1
3
0
4 X2
A2 1
5
A3
6
A4
7
A5
8
A6
9
A7
10
A8
ʳÍÅÖü Ak
Ìàë.1.1. ×àñòêîâà
ãðàô-ñõåìà àëãîðèòìó Ã1
ÏÎ×ÀÒÎÊ A0
1
A1
2
A7
0
3 1
X3
4 5
A9 A6
6 7
A10 A12
8 9
A3 A22
10
A11
ʳÍÅÖÜ Ak
Ìàë.1.2. ×àñòêîâà ãðàô-ñõåìà
àëãîðèòìó Ã2
ÏÎ×ÀÒÎÊ A0
1
A11
0 2 1
X1
3 4
A15 A16
6
5 1
X3 A12
0
7 8
A6 A13
ʳÍÅÖÜ Àk
Ìàë.1.3. ×àñòêîâà ãðàô-ñõåìà àëãîðèòìó Ã3
ÏÎ×ÀÒÎÊ A0
1
0
1
X1
2
A13
3
A9
4
A8
5
1
X2
6 0
A17
7
A6
8
A2
9
A18
ʳÍÅÖÜ
Ak
Ìàë.1.4.
×àñòêîâà ãðàô-ñõåìà àëãîðèòìó Ã4
ÏÎ×ÀÒÎÊ A0
1
A1
2
A6
3
A19
4
0 1
X1
5
0 X2
1
6
A20
7
A17
8
A2
9
A21
ʳÍÅÖÜ Ak
Ìàë.1.5. ×àñòêîâà ãðàô-ñõåìà
àëãîðòèìó Ã5
Ñòîâïö³
ÌÑÀ â³äì³òèìî âñ³ìà ì³òêàìè Ai, ùî âõîäÿòü äî ÃÑÀ, êð³ì ïî÷àòêîâî¿ A0. Íà ïåðåòèí³ ðÿäêà Ai
ñòîâïöÿ Aj çàïèøåìî
ôîðìóëó ïåðåõîäó fij â³ä îïåðàòîðà Ai äî îïåðàòîðà Aj.
Öÿ ôóíêö³ÿ äîð³âíþº 1 äëÿ
áåçóìîâíîãî ïåðåõîäó àáî êîí`þíêö³¿
ëîã³÷íèõ óìîâ, â³äïîâ³äíèõ âèõîäàì óìîâíèõ âåðøèí, ÷åðåç ÿê³ ïðîõîäèòü øëÿõ ç âåðøèíè ç ì³òêîþ
Ai ó âåðøèíó ç ì³òêîþ
Aj.
Çà
ìåòîäèêîþ îá'ºäíàííÿ çàêîäóºìî ÌÑÀ
òàêèì ÷èíîì:
Òàáëèöÿ 1.1
Êîäóâàííÿ ÌÑÀ
ÌÑÀ P1P2P3 Ì1 0 0 0 (ùp1ùp2ùp3) Ì2 0 0 1 (ùp1ùp2p3) Ì3 0 1 0 (ùp1p2ùp3) Ì4 0 1 1 (ùp1p2p3) Ì5 1 0 0 (p1ùp2ùp3)
×àñòêîâ³ ÌÑÀ Ì1-Ì5
íàâåäåí³
â òàáë.1.2-1.6
Òàáëèöÿ 1.2
×àñòêîâà ÌÑÀ Ì1 A1 A2 A3 A4 A5 A6 A7 A8 Ak A0 ùx1 ùx1ùx2 x1x2 A1 1 A2 1 A3 1 A4 1 A5 1 A6 1 A7 1 A8 1
Òàáëèöÿ 1.3
×àñòêîâà ÌÑÀ Ì2 A1 A3 A6 A7 A9 A10 A11 A12 A22 Ak A0 1 A1 1 A3 1 A6 1 A7 x3 ùx3 A9 1 A10 1 A11 1 A12 1 A22 1
Òàáëèöÿ 1.4
×àñòêîâà ÌÑÀ Ì3 A6 A12 A13 A14 A15 A16 Ak A0 1 A6 1 A12 1 A13 1 A14 ùx1 x1 A15 x3 ùx3 A16 1
Òàáëèöÿ 1.5
×àñòêîâà ÌÑÀ Ì4 A2 A6 A8 A9 A13 A17 A18 Ak A0 ùx1 x1 A2 1 A6 1 A8 x2 ùx2 A9 1 A13 1 A17 1 A18 1
Òàáëèöÿ 1.6
×àñòêîâà ÌÑÀ Ì5 A1 A2 A6 A17 A19 A20 A21 Ak A0 1 A1 1 A2 1 A6 1 A17 1 A19 x1ùx2 x1x2 ùx1 A20 1 A21 1
Íà íàñòóïíîìó åòàï³ ïîáóäóºìî îá'ºäíàíó ÌÑÀ
Ì0, â ÿê³é
ðÿäêè â³äì³÷åí³ âñ³ìà
ì³òêàìè Ài,
êð³ì Àk, à
ñòîâïö³ - âñ³ìà, êð³ì À0.
Íà
ïåðåòèí³ ðÿäêà Ài ³ ñòîâïöÿ Àj çàïèøåìî ôîðìóëó ïåðåõîäó, ÿêà ôîðìóºòüñÿ òàêèì
÷èíîì: Fij=P1fij1+...+Pnfijn (n=1...N). Äå fijn-ôîðìóëà
ïåðåõîäó ç âåðøèíè Ài
ó âåðøèíó Àj äëÿ n-î¿
ÃÑÀ. Íàïðèêëàä, ôîðìóëà ïåðåõîäó
À0®À1 áóäå ìàòè âèãëÿä F0,1=ùx1ùp1ùp2ùp3+
ùp1ùp2p3+
+p1ùp2ùp3.
Ó ðåçóëüòàò³ ìè îòðèìàºìî îá'ºäíàíó ÌÑÀ Ì0 (òàáë.1.7). Ìè
ìàºìî ìîæëèâ³ñòü ì³í³ì³çóâàòè ôîðìóëè ïåðåõîäó òàêèì ÷èíîì: ðîçãëÿäàþ÷è ÃÑÀ Ã0 ÿê ÃÑÀ Ãn, ìè ï³äñòàâëÿºìî ïåâíèé íàá³ð Pn=1,
ïðè öüîìó çì³íí³
p1..pq íå çì³íþþòü ñâî¿õ çíà÷åíü ï³ä ÷àñ ïðîõîäó ïî ÃÑÀ. Òàêèì ÷èíîì, ÿêùî ó âåðøèíó Ài
ïåðåõ³ä çàâæäè çä³éñíþºòüñÿ
ïðè íåçì³ííîìó çíà÷åíí³ pq,
òî öå çíà÷åííÿ pq â ðÿäêó Ài çàì³íèìî íà “1", à éîãî ³íâåðñ³þ íà “0". Íàïðèêëàä, ó
âåðøèíó À3 ïåðåõ³ä çä³éñíþºòüñÿ
ïðè íåçì³ííîìó çíà÷åíí³ ùp1
ùp2,
îòæå â ðÿäêó À3 ùp1
ùp2
çàì³íèìî íà “1", à p1 ³ p2 íà “0". Ó ðåçóëüòàò³
îòðèìàºìî ôîðìóëè F3,4=ùp3, F3,11=p3. Êåðóþ÷èñü
âèùåíàâåäåíèì ìåòîäîì, îòðèìàºìî
ì³í³ì³çîâàíó ÌÑÀ Ì0 (òàáë.1.8).
Ïî òàáëèö³ ñêëàäåìî ôîðìóëè ïåðåõîäó äëÿ îá'ºäíàíî¿ ÃÑÀ Ã0. Ôîðìóëîþ
ïåðåõîäó áóäåìî íàçèâàòè ñë³äóþ÷å âèðàæåííÿ: Ai®Fi,1À1+..+Fi,kÀk,
äå Fi,j- â³äïîâ³äíà
ôîðìóëà ïåðåõîäó ç
ì³í³ì³çîâàíî¿ ÌÑÀ. Ó íàøîìó
âèïàäêó îòðèìàºìî ñë³äóþ÷ó ñèñòåìó ôîðìóë:
A0®ùx1ùp1ùp2ùp3A1+ùp1ùp2p3A1+p1ùp2ùp3A1+x1ùx2ùp1ùp2ùp3A2+x1x2ùp1ùp2ùp3A3+
+ùx1ùp1p2p3A8+x1ùp1p2p3A13+ùp1p2ùp3A14
A1®ùp1ùp3A2+p1ùp3A6+ùp1p3A7
A2®ùp1ùp2ùp3A6+ùp1p2p3A18+p1ùp2p3A21
A3®ùp3A4+p3A11
A4®A5
A5®À6
Òàáëèöÿ
1.7
Îá`ºäíàíà ÌÑÀ Ìo A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 A22 Ak A0 _ _ _ _ x1p1p2p3+ _ _ +p1p2p3+ _ _ +p1p2p3 _ _ _ _ x1x2p1p2p3 _ _ _ x1x2p1p2p3 _ _ x1p1p2p3 _ x1p1p2p3 _ _ p1p2p3 A1 _ _ _ p1p2p3 _ _ p1p2p3 _ _ p1p2p3 A2 _ _ _ p1p2p3 _ p1p2p3 _ _ p1p2p3 A3 _ _ _ p1p2p3 _ _ p1p2p3 A4 _ _ _ p1p2p3 A5 _ _ _ p1p2p3 A6 _ p1p2p3 _ _ _ p1p2p3 _ _ p1p2p3 _ _ p1p2p3 _ _ p1p2p3 A7 _ _ x3p1p2p3 _ _ _ p1p2p3 _ _ _ x3p1p2p3 A8 _ x2p1p2p3 _ _ _ p1p2p3+ _ _ +x2p1p2p3 A9 _ p1p2p3 _ _ p1p2p3 A10 _ _ p1p2p3 A11 _ _ p1p2p3 A12 _ _ p1p2p3 _ _ p1p2p3 A13 _ p1p2p3 _ _ p1p2p3 A14 _ _ _ x1p1p2p3 _ _ x1p1p2p3 A15 _ _ x3p1p2p3 _ _ _ x3p1p2p3 A16 _ _ p1p2p3 A17 _ _ p1p2p3 _ p1p2p3 A18 _ p1p2p3 A19 _ _ _ x1x2p1p2p3 _ _ x1x2p1p2p3 _ _ _ x1p1p2p3 A20 _ _ p1p2p3 A21 _ _ p1p2p3 A22 _ _ p1p2p3
Òàáëèöÿ
1.8
Îá`ºäíàíà
ì³í³ì³çîâàíà
ÌÑÀ Ìo A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 A22 Ak A0 _ _ _ _ x1p1p2p3+ _ _ +p1p2p3+ _ _ +p1p2p3 _ _ _ _ x1x2p1p2p3 _ _ _ x1x2p1p2p3 _ _ x1p1p2p3 _ x1p1p2p3 _ _ p1p2p3 A1 _ _ p1p3 _ p1p3 _ p1p3 A2 _ _ _ p1p2p3 _ p1p2p3 _ _ p1p2p3 A3 _ p3 p3 A4 1 A5 1 A6 _ p1p2p3 _ _ _ p1p2p3 _ _ p1p2p3 _ _ p1p2p3 _ _ p1p2p3 A7 x3p3 _ p3 _ x3p3 A8 x2p2p3 _ _ p2p3+ _ +x2p2p3 A9 p2 _ p2 A10 1 A11 1 A12 _ p2p3 _ p2p3 A13 p3 _ p3 A14 _ x1 x1 A15 x3 _ x3 A16 1 A17 _ _ p1p2p3 _ p1p2p3 A18 1 A19 _ x1x2 x1x2 _ x1 A20 1 A21 1 A22 1
A6®ùp1p2p3A2+ùp1ùp2ùp3A7+ùp1ùp2p3A12+p1ùp2ùp3A19+ùp1p2ùp3Ak
A7®x3p3A6+ùp3A8+ùx3p3A9
A8®x2p2p3A17+ùp2ùp3Ak+ùx2p2p3Ak
A9®p2A8+ùp2A10
A10®A3
A11®Ak
A12®ùp2p3A22+p2ùp3A13
A13®p3A9+ùp3Ak
A14®ùx1A15+x1A16
A15®x3A6+ùx3Ak
A16®A12
A17®p1ùp2ùp3A2+ùp1p2p3A6
A18®Ak
A19®x1ùx2A2+x1x2A20+ùx1A21
A20®A17
A21®Ak
A22®Ak
Ïðè ïîáóäîâ³ ñèñòåìè äóæêîâèõ ôîðìóë ïåðåõîäó íåîáõ³äíî êîæíó ôîðìóëó ïðèâåñòè äî âèãëÿäó Àx1+Âùx1, äå À
 -äåÿê³ âèðàçè, à x1 ³ ùx1-ëîã³÷í³ óìîâè ïåðåõîäó. Ôîðìóëè ïåðåõîäó äëÿ âåðøèí À3,
À4, À5, À9, À10, À11, À13,
À14, À15, À16, À18, À20,
À21, À22 âæå º åëåìåíòàðíèìè (ðîçêëàäåíèìè), à â ³íøèõ º
âèðàçè âèäó Àn®xj(À)
+ùxjpi(Â).
Òóò pi â³äïîâ³äຠ÷åêàþ÷³é âåðøèí³ (ìàë.1.6). Ïîä³áíèõ âåðøèí â îá'ºäíàí³é ÃÑÀ áóòè íå ïîâèííî. Äëÿ ¿õ óñóíåííÿ ñêîðèñòàºìîñÿ ñë³äóþ÷èì
ïðàâèëîì: äîäàâàííÿ âèðàçó [PqÀn]
íå çì³íèòü ôîðìóëó, ÿêùî íàá³ð Pq íå
âèêîðèñòîâóºòüñÿ äëÿ êîäóâàííÿ ÃÑÀ
àáî âåðøèíà Àn â³äñóòíÿ â ÃÑÀ ç êîäîì Pq. Òàêèì
÷èíîì, äîäàþ÷è äîïîì³æí³ íàáîðè, ìè îòðèìàºìî ìîæëèâ³ñòü çà äîïîìîãîþ åëåìåíòàðíèõ ïåðåòâîðåíü çâåñòè
ôîðìóëè äî íåîáõ³äíîãî âèãëÿäó.
Íàïðèêëàä, ôîðìóëà A8®x2p2p3A17+ùp2ùp3Ak+ùx2p2p3A
ñïðîùóºòüñÿ òàêèì ÷èíîì A8=p3(x2p2A17+ùx2p2Ak)+ùp3ùp2Ak=p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak=
1 Xj 0
Pi 0
1
Ìàë.1.6 Ïðèêëàä ÷åêàþ÷î¿
âåðøèíè Pi
=[ùp3p2(x2A17+ùx2Ak)]+p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak+[p3ùp2Ak]=ùp2Ak+p2(x2A17+ùx2Ak).
Òóò âåðøèíà À8 íå çóñòð³÷àºòüñÿ
ó ÃÑÀ ,â êîäàõ ÿêèõ ïðèñóòí³ êîìá³íàö³¿ ùp3p2 ³ p3ùp2.
Íèæ÷å íàâåäåíî ðîçêëàä óñ³õ
íååëåìåíòàðíèõ ôîðìóë ïåðåõîäó.
A0=p1(ùp2ùp3A1)+ùp1(ùx1ùp2ùp3A1+ùp2p3A1+x1ùx2ùp2ùp3A2+x1x2ùp2ùp3A3+
+ùx1p2p3A8+x1p2p3A13+p2ùp3A14)=p1(ùp2ùp3A1)+[p1ùp2ùp3A1]+
+ùp1(p2(ùx1p3A8+x1p3A13+ùp3A14)+ùp2(ùx1ùp3A1+p3A1+x1ùx2ùp3A2+
+x1x2ùp3A3))=p1(ùp2A1)+[p1p2A1]+ùp1(p2(p3(ùx1A8+x1A13)+ùp3A14)+
+ùp2(ùp3(ùx1A1+x1x2A3+x1ùx2A2)+p3A1))=
p1A1+ùp1(p2(p3(
ùx1A8+
+x1A13)+ùp3A14)+ùp2(ùp3(ùx1A1+x1(x2A3+ùx2A2))+p3A1))
A1=ùp1(p3A7+ùp3A2)+p1ùp3A6+[p1p3A6]=
ùp1(p3A7+ùp3A2)+p1A6
A2=p1(ùp2p3A21)+ùp1(ùp2ùp3A6+p2p3A18)=
p1(ùp2p3A21)+[p1ùp2p3A21]+
+ùp1(ùp2ùp3A6+[p2ùp3A6]+p2p3A18+[p3ùp2A18])=p1(ùp2A21)+ùp1(ùp3A6+
+p3A18)=p1(ùp2A21)+[p1p2A21]+ùp1(ùp3A6+p3A18)=p1A21+ùp1(ùp3A6+
+p3A18)
A6=p1(ùp2ùp3A19)+[p1ùp2p3A19]+ùp1(p2p3A2+ùp2ùp3A7+ùp2p3A12+p2ùp3Ak)=
=p1ùp2A19+[p1p2A19]+ùp1(p2(p3A2+ùp3Ak)+ùp2(ùp3A7+p3A12))=p1A19+
+ùp1(p2(p3A2+ùp3Ak)+ùp2(ùp3A7+p3A12))
A7=p3(x3A6+ùx3A9)+ùp3A8
A8=p3(x2p2A17+ùx2p2Ak)+ùp3ùp2Ak=p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak=
=[ùp3p2(x2A17+ùx2Ak)]+p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak+[p3ùp2Ak]=ùp2Ak+
+p2(x2A17+ùx2Ak)
A12=ùp2p3A22+p2ùp3A13+[p2p3A22]+[ùp2ùp3A13]=p3A22+ùp3A13
A17=p1ùp2ùp3A2+[p1ùp2p3A2]+ùp1p2p3A6+[ùp1ùp2p3A6]=p1ùp2A2+[p1p2A2]+
+ùp1p3A6+[ùp1ùp3A6]=p1A2+ùp1A6
A19=x1(ùx2A2+x2A20)+ùx1A21
Îá'ºäíàíó ÃÑÀ Ã0 (ìàë.1.7) ïîáóäóºìî â³äïîâ³äíî äî ôîðìóë ïåðåõîäó, çàì³íþþ÷è êîæíó ì³òêó Ài â³äïîâ³äíîþ îïåðàòîðíîþ âåðøèíîþ Yt,
à êîæíèé âèðàç Xi ³ Pj â³äïîâ³äíèìè
óìîâíèìè âåðøèíàìè.
2.ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÀ Ç ÏÐÈÌÓÑÎÂÎÞ ÀÄÐÅÑÀÖ²ªÞ ̲ÊÐÎÊÎÌÀÍÄ.
2.1. Ïðèíöèï ðîáîòè
àâòîìàòà.
Ïðè ïðèìóñîâ³é àäðåñàö³¿ àäðåñà íàñòóïíî¿ ì³êðîêîìàíäè
çàäàºòüñÿ â ïîë³ ïîòî÷íî¿ ì³êðîêîìàíäè. Ôîðìàò ÌÊ â òàêîìó âèïàäêó ñë³äóþ÷èé
(ìàë. 2.1.).
1 Y m 1 X l 1 A0 k 1 A1 k
Ìàë.
2.1 Ôîðìàò êîìàíäè àâòîìàòà ç ÏÀ.
Òóò ó ïîë³ Y ì³ñòèòüñÿ
êîä, ùî çàäຠíàá³ð
ì³êðîîïåðàö³é, ó
ïîë³ X-êîä
ëîã³÷íî¿ óìîâè, ùî ïåðåâ³ðÿºòüñÿ, ó
ïîëÿõ A0 ³ A1- àäðåñè ïåðåõîäó ïðè íåâèêîíàíí³
ëîã³÷íî¿ óìîâè, ùî ïåðåâ³ðÿºòüñÿ àáî áåçóìîâíîìó ïåðåõîä³ ³ ïðè ³ñòèííîñò³
ëîã³÷íî¿ óìîâè â³äïîâ³äíî. Ðîçðÿäí³ñòü
ïîë³â âèçíà÷àºòüñÿ òàêèì ÷èíîì:
m=]log2T[ Ò- ÷èñëî
íàáîð³â ì³êðîîïåðàö³é, ùî
âèêîðèñòîâóþòüñÿ â ÃÑÀ, â íàøîìó âèïàäêó
Ò=17, m=5
l=]log2 (L+1)[
L-÷èñëî ëîã³÷íèõ óìîâ ó ÃÑÀ, â íàøîìó âèïàäêó L=6, l=3
k=]log2 Q[ Q
-ê³ëüê³ñòü ì³êðîêîìàíä.
Ñòðóêòóðíà
ñõåìà àâòîìàòà ïðèâåäåíà íà ìàë. 2.2. Àâòîìàò ôóíêö³îíóº òàêèì ÷èíîì. Ñõåìà çàïóñêó ñêëàäàºòüñÿ ç RS -òðèãåðà ³
ñõåìè “&", ÿêà áëîêóº
íàäõîäæåííÿ ñèíõðî³ìïóëüñ³â íà
ÐÀÌÊ ³ ÐÌÊ. Çà ñèãíàëîì “Ïóñê"
òðèãåð âñòàíîâëþºòüñÿ â îäèíèöþ ³ â³äáóâàºòüñÿ çàïèñ ì³êðîêîìàíä äî ðåã³ñòðó. Ïîëå Y
íàäõîäèòü íà ñõåìó ôîðìóâàííÿ ÌÎ ³ ïåðåòâîðþºòüñÿ â äåÿêèé íàá³ð ì³êðîîïåðàö³é.
Ïîëå X íàäõîäèòü äî ñõåìè ôîðìóâàííÿ àäðåñè, ÿêà ôîðìóº ñèãíàë Z2, ÿêùî ïåðåõ³ä áåçóìîâíèé (X=0) àáî ËÓ
, ùî ïåðåâ³ðÿºòüñÿ, äîð³âíþº 0,
àáî ñèãíàë Z1 ó âèïàäêó ³ñòèííîñò³ ËÓ. Çà ñèãíàëîì Z1(Z2)
äî àäðåñíîãî âõîäó ÏÇÏ íàäõîäèòü çíà÷åííÿ ïîëÿ A1(A0). Çà
ñèãíàëó y0 òðèãåð âñòàíîâëþºòüñÿ â íóëü ³ àâòîìàò çóïèíÿº ñâîþ
ðîáîòó. Çà ñèãíàëîì "Ïóñê" äî ÐÀÌÊ çàíîñèòüñÿ àäðåñà ïî÷àòêîâî¿ ÌÊ
(À=0).
2.2. Ïåðåòâîðåííÿ ïî÷àòêîâî¿ ÃÑÀ.
Ïåðåòâîðåííÿ
áóäå ïîëÿãàòè â òîìó, ùî ó âñ³ îïåðàòîðí³ âåðøèíè, ïîâ'ÿçàí³ ç ê³íöåâîþ, ââîäèòüñÿ ñèãíàë y0,
à ì³æ âñ³ìà óìîâíèìè âåðøèíàìè, ÿê³ ïîâ'ÿçàí³ ç ê³íöåâîþ, ââîäèòüñÿ îïåðàòîðíà
âåðøèíà, ùî ì³ñòèòü ñèãíàë y0. Ïðè÷îìó, öÿ âåðøèíà áóäå çàãàëüíîþ äëÿ âñ³õ óìîâíèõ. Ç óðàõóâàííÿì âèùåñêàçàíîãî îòðèìàºìî
ïåðåòâîðåíó ÃÑÀ (ìàë. 2.3). Ó ïåðåòâîðåí³é ÃÑÀ ìè çáåð³ãàºìî ïîçíà÷åííÿ Yi, àëå ïðè
öüîìó ïàì'ÿòàºìî, ùî êîæíà ì³êðîêîìàíäà
Yi
ÐÀÌÊ
Z1 Z2
S T
& ÏÇÏ
“Ïóñê”
Ѳ
R ÐÌÊ Y
X A0
A1 ÑÔÌÎ Z1 y0 .... yi ÑÔÀ äî ÎÀ Z2
Ìàë.2.2. Ñòðóêòóðíà ñõåìà àâòîìàòà ç ÏÀ
ðîçáèâàºòüñÿ
íà ì³êðîîïåðàö³¿ yi..yj
çã³äíî ç
òàáë. 2.1.
Òàáëèöÿ
2.1.
Ðîçïîä³ë
ÌÎ ïî ì³êðîêîìàíäàì. ÌÊ Ì³êðîîïåðàö³¿ ÌÊ Ì³êðîîïåðàö³¿ Y1 y1y2y9y10 Y12 y5y6y12y17y19 Y2 y1y5y12y19 Y13 y4y6y20y21 Y3 y1y6y11y20 Y14 y3y11y17y18y22 Y5 y3y4y13y30 Y15 y4y5y6y18y19y23 Y7 y2y6y7y16 Y16 y12y14y16y24 Y8 y5y13y15y29 Y17 y2y13y25 Y9 y6y17 Y18 y5 Y10 y3y4y5y18y19 Y20 y3y27y28 Y11 y7y8y17y20
2.3.Ôîðìóâàííÿ âì³ñòó êåðóþ÷î¿ ïàì'ÿò³.
Ïåðøèé åòàï - âèä³ëåííÿ ì³êðîêîìàíä çàäàíîãî ôîðìàòó.  àâòîìàò³ ç ÏÀ â îäíîìó
òàêò³ ìîæóòü âèêîíóâàòèñÿ ÌÎ ³ ïåðåâ³ðÿòèñÿ ëîã³÷íà óìîâà. Òîìó ì³êðîêîìàíäà
â³äïîâ³äຠïàð³ ÎÏÅÐÀÒÎÐÍÀ ÂÅÐØÈÍÀ - ÓÌÎÂÍÀ ÂÅÐØÈÍÀ. Âèõîäÿ÷è ç öüîãî,
îòðèìàºìî, ùî ìîæëèâèìè º ïàðè:
ÎÏÅÐÀÒÎÐÍÀ ÂÅÐØÈÍÀ - ÓÌÎÂÍÀ
ÂÅÐØÈÍÀ, ÎÏÅÐÀÒÎÐÍÀ ÂÅÐØÈÍÀ - ÁÅÇÓÌÎÂÍÈÉ ÏÅÐÅÕ²Ä, ÏÎÐÎÆÍß ÎÏÅÐÀÒÎÐÍÀ - ÓÌÎÂÍÀ
ÂÅÐØÈÍÀ. Ïðè öüîìó ïîòð³áíî âðàõîâóâàòè, ùî ïðè âèáîð³ ïàðè ÎÏÅÐÀÒÎÐÍÀ ÂÅÐØÈÍÀ - ÓÌÎÂÍÀ ÂÅÐØÈÍÀ íåäîïóñòèì ïåðåõ³ä ççîâí³ â òî÷êó ì³æ
îïåðàòîðíîþ ³ óìîâíîþ âåðøèíàìè, êð³ì ñèòóàö³¿, êîëè óìîâíà âåðøèíà âõîäèòü äî
ñêëàäó ³íøî¿ ì³êðîêîìàíäè.
Ó ðåçóëüòàò³ ìè îòðèìàºìî ñë³äóþ÷å
ðàçáèòòÿ íà ì³êðîêîìàíäè
(ìàë. 2.3.). Ìè îòðèìàëè 38 äîïóñòèìèõ ÌÊ. Çàêîäóºìî ¿õ â ïðèðîäíîìó ïîðÿäêó,
ïðèâëàñíèâøè ïî÷àòêîâ³é
ÌÊ íóëüîâó àäðåñó (òàáë.2.2). Äëÿ öüîãî
íåîáõ³äíî q=]log2N[
ðîçðÿä³â, äå N- ê³ëüê³ñòü ÌÊ çàäàíîãî ôîðìàòó. Ó íàøîìó âèïàäêó N=38,
q=6.
Òàáëèöÿ
2.2
Êîäóâàííÿ ÌÊ
ÌÊ À1À2À3À4 À5À6 Î1 0 0 0 0 0 0 Î2 0 0 0 0 0 1 ...... ........................ Î38 1 0 0 1 0 1
Àíàëîã³÷íèì ÷èíîì çàêîäóºìî îïåðàòîðè Yi, íàäàâøè íóëüîâèé êîä ïîðîæíüîìó îïåðàòîðíîìó ïîëþ (òàáë. 2.3).
Òàáëèöÿ 2.3
Êîäóâàííÿ Y
Yi T2T3T4T5T6 Æ 00000 Y1 00001 Y2 00010 Y3 00011 Y5 00100 Y7 00101 Y8 00110 Y9 00111 Y10 01000 Y11 01001 Y12 01010 Y13 01011 Y14 01100 Y15 01101 Y16 01110 Y17 01111 Y18 10000 Y20 10001
Òàáëèöÿ 2.5
Âì³ñò
êåðóþ÷î¿
ïàì`ÿò³. ¹ A FY FX FA0 FA1 Îï. A1A2A3A4A5A6 T1T2T3T4T5T6 T7T8T9 T10T11T12T13T14T15 T16T17T18T19T20T21 1 000000 000000 100 000001 001100 2 000001 000000 101 000010 011001 3 000010 000000 110 000011 001100 4 000011 000000 001 001100 000100 5 000100 000000 010 001001 000101 6 000101 000110 110 000111 000110 7 000110 101100 000 000000 000000 8 000111 000111 000 001000 000000 9 001000 001001 000 001110 000000 10 001001 001000 100 001010 011000 11 001010 000000 110 001110 001011 12 001011 100111 000 000000 000000 13 001100 000001 100 001101 001110 14 001101 000000 110 001001 010010 15 001110 000100 100 001111 010111 16 001111 000000 101 010001 010000 17 010000 000000 110 010100 010101 18 010001 000000 110 010010 011110 19 010010 000110 110 011111 010011 20 010011 000000 011 100011 001110 21 010100 100000 000 000000 000000 22 010101 000000 010 001001 010110 23 010110 000001 000 100101 000000 24 010111 001010 001 011000 010101 25 011000 101010 000 000000 000000 26 011001 000000 110 011011 011010 27 011010 000000 001 011111 100001 28 011011 001101 001 011100 011101 29 011100 001110 011 010100 001110 30 011101 000101 000 011110 000000 31 011110 001111 010 100001 100000 32 011111 000111 101 010100 100010 33 100000 100011 000 000000 000000 34 100001 010000 110 010100 100011 35 100010 000000 010 010100 100101 36 100011 000001 101 100100 011111 37 100100 001011 000 000101 000000 38 100101 010001 100 001110 001001
2.4. Ñèíòåç ñõåìè
àâòîìàòà.
Ñõåìà ÑÔÀ
ÿâëÿº ñîáîþ ìóëüòèïëåêñîð,
ÿêèé â çàëåæíîñò³ â³ä êîäó ëîã³÷íî¿ óìîâè, ùî ïåðåâ³ðÿºòüñÿ, ïåðåäຠíà âèõ³ä Z1
çíà÷åííÿ â³äïîâ³äíî¿
ËÓ. Ïðè öüîìó ñèãíàë Z2 çàâæäè º ³íâåðñ³ºþ ñèãíàëó Z1. Òàêèì ÷èíîì, îòðèìàºìî ñë³äóþ÷³
âèðàçè äëÿ Z1 ³ Z2:
Z1=X1ùT7ùT8T9+X2ùT7T8ùT9+X3ùT7T8T9+P1T7ùT8ùT9+P2T7ùT8T9+P3T7T8ùT9
Z2=ùZ1
àáî, çâ³âøè äî çàäàíîãî áàçèñó (4 ÀÁÎ-Ͳ), îòðèìàºìî
Z1=ù ù(ù ù(A+B+C+D)+E+F), äå
A=ù ù( X1ùT7ùT8T9)=ù(ùX1+T7+T8+ùT9)
B=ù ù( X2ùT7T8ùT9)=ù(ùX2+T7+ùT8+T9)
C=ù ù( X3ùT7T8T9)=ù(ùX3+T7+ùT8+ùT9)
D=ù ù( P1T7ùT8ùT9)=ù(ùP1+ùT7+T8+T9)
E=ù ù( P2T7ùT8T9)=ù(ùP2+ùT7+T8+ùT9)
F=ù ù( P3T7T8ùT9)=ù(ùP3+ùT7+ùT8+T9)
²íôîðìàö³ÿ, ùî
íàäõîäèòü íà àäðåñí³ âõîäè ÏÇÏ
ôîðìóºòüñÿ òàêèì ÷èíîì: Ai=A0iZ1+A1iZ2
àáî, ïðèâîäÿ÷è äî çàäàíîãî áàçèñó, îòðèìóºìî Ai=ùù(ù(ùA0i+ùZ1)+ù(ùA1i+ùZ2)).
Ñèíòåçóºìî òåïåð ñõåìó äåøèôðàòîðà, ùî ôîðìóº ñèãíàëè ì³êðîîïåðàö³é
yi. Ïîÿâà îäèíèö³, â³äïîâ³äíî¿ êîæíîìó Y, â³äáóâàºòüñÿ ïðè ïîÿâ³ íà âõîä³ äåøèôðàòîðà êîäó äàíîãî Y, òîáòî Yi=T2eÙT3eÙT4åÙT5åÙT6å,
äå åÎ{0,1} T0=ùT, T1=T.
Àáî ïðèâîäÿ÷è äî çàäàíîãî áàçèñó, îòðèìàºìî: Yi=ù(ù ù(T2ùe+T3ùe+T4ùå+T5ùå)+T6ùå). Òàêèì
÷èíîì, ñõåìà, ùî ôîðìóº ñèãíàë Y ç ï`ÿòèðîçðÿäíîãî êîäó âèãëÿäຠòàêèì
÷èíîì(ìàë. 2.4)
T6ùe
1
1 1 Yi
T2ùe
Ìàë. 2.4. Ñõåìà
ôîðìóâàííÿ ñèãíàëó Yi.
Âðàõîâóþ÷è, ùî
ðîçðÿä T2 ð³âíèé “1" ïðè ôîðìóâàíí³ ò³ëüêè äâîõ
ñèãíàë³â Y18 ³ Y20, òî ñõåìó(ìàë. 2.4) áóäåìî âèêîðèñòîâóâàòè äëÿ ôîðìóâàííÿ Y1,
Y20, äëÿ ÿêèõ ñï³âïàäàþòü
ìîëîäø³ ÷îòèðè ðîçðÿäè òà äëÿ Y18, äëÿ ÿêîãî ìîëîäø³
÷îòèðè ðîçðÿäè ñï³âïàäàþòü
ç êîäîì ïîðîæíüî¿
îïåðàòîðíî¿
âåðøèíè. À
äëÿ âñ³õ ³íøèõ Y ñõåìó ìîæíà ñïðîñòèòè (ìàë.2.5.).
T6ùe
1 Yi
T3ùe
Ìàë.2.5. Ñïðîùåíà ñõåìà ôîðìóâàííÿ ñèãíàëó
Yi.
Çã³äíî ç
íàâåäåíèìè ñõåìàìè çàïèøåìî ôîðìóëè äëÿ âñ³õ Yi. Y11=ù(ùT3+T4+T5+ùT6) Y12=ù(ùT3+T4+ùT5+T6) Y13= ù(ùT3+T4+ùT5+ùT6) Y14= ù(ùT3+ùT4+T5+T6) Y15= ù(ùT3+ùT4+T5+ùT6) Y16= ù(ùT3+ùT4+ùT5+T6) Y17= ù(ùT3+ùT4+ùT5+ùT6) Y18=ù (ù ù(ùT2+T3+T4+T5)+T6) Y20=ù (ù ù(ùT2+T3+T4+T5)+ùT6)
Y1=ù (ù ù(T2+T3+T4+T5)+ùT6)
Y2=
ù(T3+T4+ùT5+T6)
Y3=
ù(T3+T4+ùT5+ùT6)
Y5=
ù(T3+ùT4+T5+T6)
Y7=
ù(T3+ùT4+T5+ùT6)
Y8=
ù(T3+ùT4+ùT5+T6)
Y9=
ù(T3+ùT4+ùT5+ùT6)
Y10=ù(ùT3+T4+T5+T6)
Ñèãíàëè ì³êðîîïåðàö³é
yj îòðèìàºìî,
îá'ºäíóþ÷è ïî “àáî" âèõîäè
â³äïîâ³äí³ îïåðàòîðàì Yi, â ÿêèõ çóñòð³÷àºòüñÿ ÌÎ yj. Ïðè öüîìó áóäåìî êîðèñòóâàòèñÿ òàáëèöåþ
Òàáëèöÿ 2.5.
Ðîçïîä³ë ÌÎ çà ì³êðî-
êîìàíäàìè ÌÎ íîìåðè ÌÊ y1 1,2,3 y2 1,7,17 y3 5,10,14,20 y4 5,10,13,15 y5 2,8,10,12,15,18 y6 3,7,9,12,13,15 y7 7,11 y8 11 y9 1 y10 1 y11 3,14 y12 2,12,16 y13 5,8,17 y14 16 y15 8 y16 7,16 y17 9,11,12,14 y18 10,14,15 y19 2,10,12,15 y20 3,11,13 y21 13 y22 14 y23 15 y24 16 y25 17 y27 20 y28 20 y29 8 y30 5
Íà íàñòóïíîìó åòàï³
ñèíòåçóºìî ñõåìè ÐÀÌÊ ³ ÐÌÊ, âèêîðèñòîâóþ÷è ùRùS òðèãåðè. Ñêîðèñòàºìîñÿ êëàñè÷íèì
ìåòîäîì ñèíòåçó ðåã³ñòð³â
çàïîâíèìî ñë³äóþ÷ó
òàáëèöþ (òàáë. 2.6.).
Òàáëèöÿ
2.6.
Ñèíòåç ÐÀÌÊ òà ÐÌÊ Çàïîâíèìî êàðòè Êàðíî: Qt\Ai 0 1 0 * 1 ùR=Ai 1 0 1 Qt\Ai 0 1 0 1 0 ùS=ùAi 1 1 * Ñ Ai Qt Qt+1 Ct ùR ùS 0 0 0 0 0 * * 0 0 1 1 0 * * 0 1 0 0 0 * * 0 1 1 1 0 * * 1 0 0 0 1 * 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 *
Ó ðåçóëüòàò³ îòðèìàºìî
ñë³äóþ÷ó
ñõåìó äëÿ áàçîâîãî åëåìåíòó ÐÀÌÊ òà ÐÌÊ (ìàë.2.6).
Ai
1 S TT Q
Ѳ C
R
“Reset” R ùQ
Ìàë. 2.6. Áàçîâèé åëåìåíò ðåã³ñòðà.
Ñõåìà ÐÀÌÊ ì³ñòèòü
6 òàêèõ åëåìåíò³â,
à ñõåìà ÐÌÊ - 21. Ïðè ïîáóäîâ³
ñõåìè ñèãíàëè ùT1..ùT21
áóäåìî çí³ìàòè ç ³íâåðñíèõ
âèõîä³â åëåìåíò³â
ðåã³ñòð³â. ʳëüê³ñòü ì³êðîñõåì
ÏÇÏ âèçíà÷èìî çà ôîðìóëîþ: NÏÇÏ=]R/3[, äå R - ðîçðÿäí³ñòü
ì³êðîêîìàíäè R=21, NÏÇÏ=7. Äëÿ çáåð³ãàííÿ
ì³êðîïðîãðàìè äîñèòü îäí³º¿ ë³í³éêè ÏÇÏ, îñê³ëüêè QÏÇÏ=8, òîáòî îäíà ì³êðîñõåìà ðîçðàõîâàíà íà çáåð³ãàííÿ 256 òðüîõá³òîâèõ
êîìá³íàö³é, à â íàøîìó âèïàäêó ïîòð³áíî ò³ëüêè 38. Ïðè ïîáóäîâ³
ñõåìè áóäåìî çàïèñóâàòè â ÐÀÌÊ ³íâåðñ³þ àäðåñè, à äî ÏÇÏ áóäåìî ïîäàâàòè àäðåñó ç ³íâåðñíèõ âèõîä³â åëåìåíò³â ðåã³ñòðà,
òàêèì ÷èíîì, ìè çàîùàäèìî
6 åëåìåíò³â-³íâåðòîð³â
ó ÑÔÀ. Ç âðàõóâàííÿì âèùåñêàçàíîãî ïîáóäóºìî ñõåìó àâòîìàòà ç
ïðèìóñîâîþ àäðåñàö³ºþ ì³êðîêîìàíä(ìàë.
2.7).
3.ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÀ Ç ÏÐÈÐÎÄÍÎÞ
ÀÄÐÅÑÀÖ²ªÞ ̲ÊÐÎÊÎÌÀÍÄ
3.1.
Ïðèíöèï ðîáîòè àâòîìàòà.
Ïðè ïðèðîäí³é àäðåñàö³¿ ìèêðîêîìàíä ³ñíóº òðè ôîðìàòà ÌÊ (ìàë. 3.1.).
Ï 1 FY m ÎÌÊ
Ï 1 FX l 1 FA r ÓÌÊ1 Ï 1 Æ l 1
FA r
ÓÌÊ2
Ìàë.3.1.
Ôîðìàòè ì³êðîêîìàíä
àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ..
Òóò ôîðìàò ÎÌÊ â³äïîâ³äຠîïåðàòîðí³é âåðøèí³, ÓÌÊ1-óìîâí³é, à ÓÌÊ2-âåðøèí³ áåçóìîâíîãî
ïåðåõîäó. Ïðè ïîäà÷³ ñèãíàëó “ïóñê" ë³÷èëüíèê ËÀÌÊ îáíóëÿºòüñÿ, ³ çà
ñèãíàëîì Ѳ â³äáóâàºòüñÿ çàïèñ ÌÊ äî ðåã³ñòðà. ÑÔÌÎ ôîðìóº â³äïîâ³äí³ ÌÎ ïðè Ï=1 àáî âèäຠíà âñ³õ âèõîäàõ íóë³ ïðè
Ï=0. ÑÔÀ â çàëåæíîñò³ â³ä Ï ³ âì³ñòó
ïîëÿ FX, ôîðìóº ñèãíàëè Z1 ³
Z2. Ñèãíàë Z1 äîçâîëÿº
ïðîõîäæåííÿ ñèíõðî³ìïóëüñ³â íà ë³÷èëüíèé
âõ³ä ËÀÌÊ, à Z2 äîçâîëÿº çàïèñ äî ë³÷èëüíèêà àäðåñè íàñòóïíî¿ ÌÊ ç
ïðèõîäîì ñèíõðî³ìïóëüñó.
Âèçíà÷èìî ðîçðÿäí³ñòü
ïîë³â. l=]log2(L+1)[, äå L-÷èñëî óìîâíèõ âåðøèí. L=6, l=3
m=]log2T[ Ò- ÷èñëî
íàáîð³â ì³êðîîïåðàö³é, ùî
âèêîðèñòîâóþòüñÿ â ÃÑÀ, â íàøîìó âèïàäêó
Ò=17, m=5
r=]log2 Q[, Q -
ê³ëüê³ñòü ì³êðîêîìàíä.
3.2.Ïåðåòâîðåííÿ ïî÷àòêîâî¿ ÃÑÀ.
Ïåðåòâîðåííÿ áóäå ïîëÿãàòè â òîìó, ùî äî âñ³õ îïåðàòîðíèõ âåðøèí,
ïîâ'ÿçàíèõ ç ê³íöåâîþ, ââîäèòüñÿ ñèãíàë y0, à ì³æ âñ³ìà óìîâíèìè
âåðøèíàìè, ÿê³ ïîâ'ÿçàí³ ç ê³íöåâîþ, ââîäèòüñÿ îïåðàòîðíà âåðøèíà, ùî ì³ñòèòü
ñèãíàë y0. Êð³ì öüîãî, â ÃÑÀ ââîäÿòüñÿ ñïåö³àëüí³ âåðøèíè
áåçóìîâíîãî ïåðåõîäó X0, â³äïîâ³äí³ ôîðìàòó ÓÌÊ2. Ââåäåííÿ òàêèõ
âåðøèí íåîáõ³äíå äëÿ âèêëþ÷åííÿ êîíôë³êò³â àäðåñàö³¿ ì³êðîêîìàíä. Ó àâòîìàò³ ç ïðèðîäíîþ àäðåñàö³ºþ (ðèñ3.2.) ïðè ³ñòèííîñò³(ïîìèëêîâ³ñòü) ëîã³÷íî¿ óìîâè
ïåðåõ³ä çä³éñíþºòüñÿ äî âåðøèíè ç àäðåñîþ íà îäèíèöþ âåëèêèì, à ïðè
(ïîìèëêîâ³ñòü)³ñòèííîñò³ ËÓ ïåðåõ³ä â³äáóâàºòüñÿ çà àäðåñîþ, çàïèñàíîþ â ïîë³
FA. Ó íàøîìó âèïàäêó áóäåìî äîäàâàòè îäèíèöþ
ïðè ³ñòèííîñò³ ËÓ àáî ïðè ïåðåõîä³ ç îïåðàòîðíîé âåðøèíè. ßêùî â îäí³é
òî÷ö³ ñõîäèòüñÿ äåê³ëüêà ïåðåõîä³â ïî
1" àáî ç îïåðàòîðíî¿
âåðøèíè, òî âñ³ âåðøèíè ç ÿêèõ çä³éñíþâàâñÿ ïåðåõ³ä, ïîâèíí³ áóëè á ìàòè
îäíàêîâó (íà îäèíèöþ ìåíøó ) àäðåñó, í³æ íàñòóïíà êîìàíäà. Àëå öå íåìîæëèâî.
Z1 +1
ñ³ Z2 À ËÀÌÊ
“Ïóñê”
1 ÏÇÏ
ÐÌÊ
FY Ï FX FA
ÑÔÌÎ
ÑÔÀ Z1
y0.....yi ê
ÎÀ
Z2
Ìàë.3.2.
Ñòðóêòóðíà ñõåìà àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ.
Äëÿ âèêëþ÷åííÿ ïîä³áíèõ ñèòóàö³é
ââîäÿòü ñïåö³àëüíó âåðøèíó áåçóìîâíîãî ïåðõîäó (ìàë. 3.3). Äàí³ âåðøèíè äîäàºìî
òàêèì ÷èíîì, ùîá â îäí³é òî÷ö³ ñõîäèëàñÿ áóäü-ÿêà ê³ëüê³ñòü ïåðåõîä³â ïî
0" ³ ò³ëüêè îäèí ïî “1" àáî ç îïåðàòîðíî¿ âåðøèíè. Ç âðàõóâàííÿì âêàçàíèõ
ïåðåòâîðåíü îòðèìàºìî ïåðåòâîðåíó ÃÑÀ (ìàë. 3.4).
X0 0
1
Ìàë.
3.3. Âåðøèíà áåçóìîâíîãî ïåðåõîäó.
3.3.Ôîðìóâàííÿ âì³ñòó êåðóþ÷î¿ ïàì'ÿò³.
Íà ïåðåòâîðåí³é
ÃÑÀ âèä³ëèìî ì³êðîêîìàíäè
ôîðìàò³â ÎÌÊ, ÓÌÊ1, ÓÌÊ2. Ó ðåçóëüòàò³ îòðèìàºìî 63 ÌÊ. Âèêîíàºìî ¿õ àäðåñàö³þ.
Äëÿ öüîãî çàïèøåìî âñ³ ïðèðîäí³ ïîñë³äîâíîñò³ êîìàíä (ëàíöþæêè âåðøèí, ïåðåõ³ä
ì³æ ÿêèìè çä³éñíþºòüñÿ ïî “1" àáî ÷åðåç îïåðàòîðíó âåðøèíó). Ó ðåçóëüòàò³
îòðèìàºìî:
a1=[O1,O5]
a2=[ O2
,O6 ,O7 ,O36 ,O48 ,O51
,O55 ,O34 ,O47 ,O49 ,O56
,O59 ,O12 ,O16 ,O45]
a3=[ O3
,O9 ,O13 ,O18]
a4=[ O4
,O10 ,O11]
a5=[ O8
,O14 ,O20 ,O30 ,O32 ,O35]
a6=[ O60
,O15 ,O21 ,O22]
a7=[ O17
,O52 ,O57 ,O61 ,O62]
a8=[ O19
,O28 ,O29]
a9=[ O23
,O25 ,O27 ,O31 ,O37 ,O44
,O43 ,O53 ,O54]
a10=[ O24
,O26]
a11=[ O33]
a12=[ O38
,O41 ,O42]
a13=[ O39
,O40]
a14=[ O46]
a15=[ O50]
a16=[ O58]
a17=[ O63]
Ïåðåðàõóºìî â òàáëèö³ àäðåñàö³¿ (òàáë.
3.1) ï³äðÿä âñ³ ïîñë³äîâíîñò³ a1-a17 ³ çàêîäóºìî ¿õ
R-ðîçðÿäíèì êîäîì. R=]log2N[, N-ê³ëüê³ñòü ì³êðîêîìàíä (N=63, R=6). Çàêîäóºìî òàêîæ îïåðàòîðè Yi,
ïîñòàâèâøè ¿ì ó â³äïîâ³äí³ñòü ï`ÿòèðîçðÿäíèé êîä. Áóäåìî âèêîðèñòîâóâàòè òå æ
êîäóâàííÿ, ùî ³ â àâòîìàò³ ç ÏÀ.(òàáë. 2.3., 2.4). Ó òàáëèö³ 3.2 â³äîáðàçèìî
âì³ñò êåðóþ÷î¿ ïàì'ÿò³, çàïîâíèâøè ïîëÿ FX, FY, FA.
Òàáëèöÿ
3.1. Òàáëèöÿ 3.1.
(ïðîäîâæåííÿ)
Àäðåñàö³ÿ ÌÊ. ìê À1À2À3À4À5À6 O1 000000 O5 000001 O2 000010 O6 000011 O7 000100 O36 000101 O48 000110 O51 000111 O55 001000 O34 001001 O47 001010 O49 001011 O56 001100 O59 001101 O12 001110 O16 001111 O45 010000 O3 010001 O9 010010 O13 010011 O18 010100 O4 010101 O10 010110 O11 010111 O8 011000 O14 011001 O20 011010 O30 011011 O32 011100 O35 011101 O60 011110 O15 011111 O21 100000 O22 100001 O17 100010 O52 100011 O57 100100 O61 100101 O62 100110
Òàáëèöÿ 3.2.
Âì³ñò êåðóþ÷î¿
ïàì`ÿò³
àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ. ÌÊ Àäðåñà Ï FY Ôîðìóëà ïåðåõîäó FX FA À1À2À3À4À5À6 T1 T2T3T4 T5T6T7T8T9T10 O1 000000 1 100 000010 O1®ùP1O2+P1O5 O5 000001 1 000 010010 O5®O9 O2 000010 1 101 010001 O2®ùP2O3+P2O6 O6 000011 1 110 011000 O6®ùP3O8+P3O7 O7 000100 1 001 001001 O7®ùX1O34+X1O36 O36 000101 0 010 000000 O36®O48 O48 000110 1 110 111110 O48®ùP3O63+P3O51 O51 000111 0 000 010000 O51®O55 O55 001000 1 101 011110 O55®ùP2O60+P2O34 O34 001001 0 000 111000 O34®O47 O47 001010 1 101 111011 O47®ùP2O46+P2O49 O49 001011 1 010 111100 O49®ùX2O50+X2O56 O56 001100 0 010 001000 O56®O59 O59 001101 1 100 101100 O59®ùP1O27+P1O12 O12 001110 0 001 000000 O12®O16 O16 001111 1 100 110011 O16®ùP1O24+P1O45 O45 010000 0 101 010000 O45®K O3 010001 1 110 010101 O3®ùP3O4+P3O9 O9 010010 0 000 001000 O9®O13 O13 010011 1 100 100010 O13®ùP1O17+P1O18 O18 010100 1 000 101100 O18®ùO27 O4 010101 1 001 010010 O4®ùX1O9+X1O10 O10 010110 1 010 001110 O10®ùX2O12+X2O11 O11 010111 1 000 011111 O11®O15 O8 011000 0 001 101000 O8®O14 O14 011001 1 001 100111 O14®ùX1O19+X1O20 O20 011010 0 000 101000 O20®O30 O30 011011 0 001 111000 O30®O32 O32 011100 1 110 000101 O32®ùP3O36+P3O35 O35 011101 0 100 011000 O35®K O60 011110 0 001 011000 O60®ùO15 O15 011111 0 000 110000 O15®O21 O21 100000 1 110 101010 O21®ùP3O23+P3O22 O22 100001 0 101 100000 O22®K O17 100010 1 110 001110 O17®ùP3O12+P3O52 O52 100011 0 000 110000 O52®O57 O57 100100 1 110 001001 O57®ùP3O34+P3O61 O61 100101 1 011 000111 O61®ùX3O51+X3O62 O62 100110 1 000 101100 O62®O27 O19 100111 0 001 110000 O19®O28
Òàáëèöà 3.2.
(ïðîäîâæåííÿ) O28 101000 1 011 110101 O28®ùX3O33+X3O29 O29 101001 1 000 101100 O29®O27 O23 101010 0 000 111000 O23®O25 O25 101011 0 001 001000 O25®O27 O27 101100 0 000 100000 O27®O31 O31 101101 1 100 110110 O31®ùP1O38+P1O37 O37 101110 0 001 010000 O37®O44 O44 101111 1 001 010000 O44®ùX1O45+X1O43 O43 110000 1 010 001110 O43®ùX2O12+X2O53 O53 110001 0 000 001000 O53®O54 O54 110010 1 000 001100 O54®O56 O24 110011 1 110 101100 O24®ùP3O27+P3O26 O26 110100 0 100 111000 O26®K O33 110101 0 100 000000 O33®K O38 110110 1 101 111001 O38®ùP2O39+P2O41 O41 110111 1 110 111101 O41®ùP3O58+P3O42 O42 111000 1 000 001110 O42®ùO12 O39 111001 1 110 100011 O39®ùP3O52+P3O40 O40 111010 1 000 011011 O40®O30 O46 111011 0 100 000000 O46®K O50 111100 0 100 000000 O50®K O58 111101 0 100 000000 O58®K O63 111110 0 100 000000 O63®K
3.4.
Ñèíòåç ñõåìè àâòîìàòà.
Ñèíòåçóºìî ñõåìó, ùî ôîðìóº ñèãíàë Z1. Ñèãíàë Z1
ð³âíèé 1, ÿêùî îçíàêà Ï=0 àáî Ï=1 ³ ïðè öüîìó ëîã³÷íà óìîâà, ùî ïåðåâ³ðÿºòüñÿ,
ñòèííà. Ñêîðèñòàºìîñÿ ôîðìóëîþ Z1 äëÿ àâòîìàòà ç ÏÀ, ÿêà â
çàëåæíîñò³ â³ä êîäó óìîâè ïåðåäຠíà
âèõ³ä Z1 çíà÷åííÿ â³äïîâ³äíîãî ËÓ.
Z1=X1ùT2ùT3T4+X2ùT2T3ùT4+X3ùT2T3T4+P1T2ùT3ùT4+P2T2ùT3T4+P3T2T3ùT4
Ç âðàõóâàííÿì âèùåíàâåäåíèõ âèìîã
çàïèøåìî ôîðìóëè äëÿ ñèãíàë³â Z1 ³ Z2 â
àâòîìàò³ ç ïðèðîäíîþ àäðåñàö³ºþ.
Z1=ùT1+T1(X1ùT2ùT3T4+X2ùT2T3ùT4+X3ùT2T3T4+P1T2ùT3ùT4+P2T2ùT3T4+P3T2T3ùT4)
Z2=ùZ1
Àáî , çâ³âøè äî
çàäàíîãî áàçèñó îòðèìàºìî:
Z1=ù ù(ù(ù(ù ù(A+B+C+D)+E+F)+ùT1)+ùT1),
ãäå
A=ù ù( X1ùT7ùT8T9)=ù(ùX1+T2+T3+ùT4)
B=ù ù( X2ùT7T8ùT9)=ù(ùX2+T2+ùT3+T4)
C=ù ù( X3ùT7T8T9)=ù(ùX3+T2+ùT3+ùT4)
D=ù ù( P1T7ùT8ùT9)=ù(ùP1+ùT2+T3+T4)
E=ù ù( P2T7ùT8T9)=ù(ùP2+ùT2+T3+ùT4)
F=ù ù( P3T7T8ùT9)=ù(ùP3+ùT2+ùT3+T4)
Ñõåìà ôîðìóâàííÿ ÌÎ ïîä³áíà ÑÔÌÎ
àâòîìàòà ç ÏÀ, àëå ïîÿâà ñèãíàë³â íà âèõîäàõ yi ìîæëèâà ò³ëüêè ïðè
Ï=0, òîáòî êîëè ïîòî÷íà ì³êðîêîìàíäà
â³äïîâ³äຠîïåðàòîðí³é
âåðøèí³. Òîìó ñõåìó ôîðìóâàííÿ Yi çì³íèìî òàêèì ÷èíîì: ñèãíàë ùT1(ùÏ)
êîí`þíêòèâíî îá'ºäíàºìî ç êîæíèì ñèãíàëîì T3...T7,ùT3...ùT7
(ìàë. 3.5). Ïðè öüîìó â³äñóòí³ñòü öèõ ñèãíàë³â
ïðèâåäå äî â³äñóòíîñò³ ñèãíàë³â yi, áî êîìá³íàö³ÿ ç óñ³õ íóë³â íà
âõîä³
äíøèôðàòîðà â³äïîâ³äàº
ïîðîæí³é
îïåðàòîðí³é
âåðøèí³.
Âèíÿòîê ñêëàäຠñèãíàë y0, äëÿ ÿêîãî ïåðåäáà÷åíèé îêðåìèé ðîçðÿä,
òîìó éîãî ìè êîí`þíêòèâíî îá'ºäíàºìî ç ñèãíàëîì ùT1(ùÏ) (ìàë. 3.6.)
ùT3...ùT7 T3..T7
1
T3...T7 1 ùT3...ùT7
T1 T1
Ìàë.3.5. Ñõåìè
ï³äêëþ÷åííÿ
ùÏ.
ùT2
1 y0
T1
Ðèñ.3.6.Ñõåìà
ôîðìóâàííÿ y0.
Ñõåìà áàçîâîãî åëåìåíòó ÐÌÊ àíàëîã³÷íà
â³äïîâ³äí³é ñõåì³ â àâòîìàò³ ç ÏÀ(ìàë2.6). Ó ÿêîñò³ ËÀÌÊ áóäåìî âèêîðèñòîâóâàòè
ë³÷èëüíèê, ùî ìຠñë³äóþ÷ó
ôóíêö³îíàëüíó ñõåìó(ìàë. 3.7.). Âõ³ä V
â³äïîâ³äຠñèãíàëó Z1, ÿêùî â³í ð³âíèé 1, òî ËÀÌÊ çá³ëüøóº ñâ³é
âì³ñò íà 1, â ïðîòèëåæíîìó âèïàäêó, íà âèõ³ä ïåðåäàºòüñÿ ³íôîðìàö³ÿ ç âõîä³â A1...Ai.
Ñèíòåçóºìî ë³÷èëüíèê ç êð³çíèì
ïåðåíåñåííÿì. Äëÿ öüîãî ñêëàäåìî ñë³äóþ÷ó òàáëèöþ(òàáë.3.3).Òàáëèöÿ ñêëàäåíà äëÿ îäíîãî
ðîçðÿäó. Áóäåìî ââàæàòè, ùî Ñë=Ñ. ³äïîâ³äíî ôóíêö³ÿì çáóäæåííÿ ùRùS òðèãåðà ñêëàäåìî êàðòè Êàðíî, ³ çà ðåçóëüòàòàìè ñèíòåçó ïîáóäóºìî ñë³äóþ÷ó ñõåìó ë³÷èëüíèêà(ìàë.3.8.).Òóò T-ñèãíàë ïåðåíåñåííÿ. Ai,Qt\V,T 00 01 11 10 00 * * 1 * 01 0 0 0 1 11 1 1 0 1 10 1 1 1 * ùR=ù ù(ùQt+ù(ùV+T)+ù(V+ùAi)) Ai,Qt\V,T 00 01 11 10 00 1 1 0 1 01 1 1 1 * 11 * * 1 * 10 0 0 0 1 ùS=ù ù(Qt+ù(ùV+T)+ù(V+Ai)) Ïðè ïîáóäîâ³ ñõåìè âðàõóºìî, ùî ñèãíàë ïðåíåñåííÿ T ôîðìóºòüñÿ çã³äíî ç ñë³äóþ÷îþ ôîðìóëîþ Ti=Qi-1*Ti-1, i-íîìåð ðîçðÿäó(T0=1).
A1 CT
A2 A1
A3 A2
A4 A3
A5 A4
A6 A5
A6
V
C
R
Ìàë.3.7.
Ôóíêö³îíàëüíå
çîáðàæåííÿ
ë³÷èëüíèêà.
Òàáëèöÿ.3.3
Ñèíòåç ñõåìè ËÀÌÊ. V T Ai Qt Qt+1 ùR ùS 0 0 0 0 0 * 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 * 0 1 0 0 0 * 1 0 1 0 1 1 1 * 0 1 1 0 1 1 0 0 1 1 1 1 1 * 1 0 0 0 0 * 1 1 0 0 1 1 1 * 1 0 1 0 0 * 1 1 0 1 1 1 1 * 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1
Ñõåìà ÐÌÊ ì³ñòèòü 10 áàçîâèõ åëåìåíò³â. Ïðè ïîáóäîâ³ ñõåìè ñèãíàëè ùT1...ùT10
áóäåìî çí³ìàòè ç ³íâåðñíèõ
âèõîä³â åëåìåíò³â
ðåã³ñòðà. ʳëüê³ñòü ì³êðîñõåì ÏÇÏ âèçíà÷èìî çà ôîðìóëîþ: NÏÇÏ=]R/3[, äå R - ðîçðÿäí³ñòü ì³êðîêîìàíäè R=10, NÏÇÏ=4
Äëÿ çáåð³ãàííÿ ì³êðîïðîãðàìè
äîñèòü îäí³º¿ ë³í³éêè ÏÇÏ, îñê³ëüêè QÏÇÏ=8, òîáòî îäíà ì³êðîñõåìà
ðîçðàõîâàíà íà çáåð³ãàííÿ 256 òðüîõá³òîâèõ
êîìá³íàö³é, à â íàøîìó âèïàäêó ïîòð³áíî ò³ëüêè 63. Ç óðàõóâàííÿì âèùåñêàçàíîãî
ïîáóäóºìî ñõåìó àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ ì³êðîêîìàíä(ìàë. 3.8).
V
1 1
T0
1 1 1 Q0 S TT C
Ai 1 1 R 1 1 R
C
Reset”
T1
Q1
ùT1 T2
1 Q2
ùQ1
ùT2 T3
1 Q3
ùQ2
........................................................................
Ìàë.3.8.Ñõåìà ËÀÌÊ (óñüîãî 6
åëåìåíò³â,
ñèãíàëè V,C,”Reset”,Ai äëÿ âñ³õ, îêð³ì
ïåðøîãî, íå ïîêàçàí³).
4.ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÀ Ç
ÊÎÌÁ²ÍÎÂÀÍÎÞ ÀÄÐÅÑÀÖ²ªÞ ̲ÊÐÎÊÎÌÀÍÄ.
4.1.Ïðèíöèï ðîáîòè àâòîìàòà.
Àâòîìàò ç êîìá³íîâàíîþ àäðåñàö³ºþ º
êîìá³íàö³ºþ ç àâòîìàò³â ç ïðèìóñîâîþ ³ ïðèðîäíîþ àäðåñàö³ºþ . Ó äàíîìó
àâòîìàò³ àäðåñà íàñòóïíî¿ ÌÊ çàäàºòüñÿ â ïîë³ ïîòî÷íî¿ ì³êðîêîìàíäè, ïðè öüîìó ïðè
íåâèêîíàíí³ ËÓ, ùî ïåðåâ³ðÿºòüñÿ, àáî ïðè áåçóìîâíîìó ïåðåõîä³ ïåðåõ³ä
çä³éñíþºòüñÿ çà çàäàíîþ
àäðåñîþ, à ïðè ³ñòèííîñò³
- çà àäðåñîþ íà îäèíèöþ á³ëüøó, í³æ ïîòî÷íà. Ôîðìàò êîìàíäè àâòîìàòà ç ÊÀ íàñòóïíèé(ìàë. 4.1).
1
Y m 1 Õ k 1 A l
Ìàë.
4.1.Ôîðìàò êîìàíäè àâòîìàòà ç ÊÀ.
Òóò ó ïîë³
Y ì³ñòèòüñÿ êîä, ùî çàäຠíàá³ð ì³êðîîïåðàö³é,
ó ïîë³ X-êîä
ëîã³÷íî¿ óìîâè, ùî ïåðåâ³ðÿºòüñÿ, â
ïîë³ À - àäðåñà ïåðåõîäó ïðè
íåâèêîíàíí³
ëîã³÷íî¿ óìîâè àáî ïðè áåçóìîâíîìó ïåðåõîä³. Ðîçðÿäí³ñòü ïîë³â âèçíà÷àºòüñÿ òàêèì ÷èíîì:
m=]log2T[ Ò- ÷èñëî íàáîð³â ì³êðîîïåðàö³é,
ùî âèêîðèñòîâóþòüñÿ â ÃÑÀ, â
íàøîìó âèïàäêó Ò=17, m=5
k=]log2(L+1)[ L-÷èñëî ëîã³÷íèõ óìîâ â ÃÑÀ, â íàøîìó âèïàäêó L=6, l=3
l=]log2Q[ Q -ê³ëüê³ñòü ì³êðîêîìàíä.
Ñòðóêòóðíà
ñõåìà àâòîìàòà ïðèâåäåíà íà ìàë. 4.2. Àâòîìàò ôóíêö³îíóº òàêèì ÷èíîì. Ñõåìà çàïóñêó ñêëàäàºòüñÿ ç RS -òðèãåðà ³
ñõåìè “&", ÿêà áëîêóº íàäõîäæåííÿ ñèíõðî³ìïóëüñ³â
íà ÐÌÊ. Çà ñèãíàëîì “Ïóñê" òðèãåð âñòàíîâëþºòüñÿ â îäèíèöþ ³ â³äáóâàºòüñÿ çàïèñ ì³êðîêîìàíäè äî ðåã³ñòðó. Ïîëå Y ïîñòóïàº
íà ñõåìó ôîðìóâàííÿ ÌÎ ³
ïåðåòâîðþºòüñÿ â
äåÿêèé íàá³ð ì³êðîîïåðàö³é.
Ïîëå X ïîñòóïຠíà ñõåìó
ôîðìóâàííÿ àäðåñè, ÿêà ôîðìóº ñèãíàë Z2,
ÿêùî ïåðåõ³ä áåçóìîâíèé
(X=0) àáî ËÓ, ùî
ïåðåâ³ðÿºòüñÿ,äîð³âíþº
íóëþ àáî ñèãíàë Z1 ó âèïàäêó ³ñòèííîñò³ ËÓ.
Çà ñèãíàëîì Z2 âì³ñò
ïîëÿ À íàäõîäèòü äî ë³÷èëüíèêà,à
ç íüîãî - íà àäðåñíèé âõ³ä ÏÇÏ.
À çà ñèãíàëîì Z1 íà àäðåñíèé âõ³ä òàêîæ íàäõîäèòü âì³ñò ë³÷èëüíèêà
àëå òåïåð öå àäðåñà ïîòî÷íî¿ ì³êðîêîìàíäè,
çá³ëüøåíà íà îäèíèöþ. Çà ñèãíàëîì y0 òðèãåð ñêèäàºòüñÿ â íóëü ³ àâòîìàò çóïèíÿº ñâîþ ðîáîòó.
4.2.
Ïåðåòâîðåííÿ ïî÷àòêîâî¿ ÃÑÀ.
Ïåðåòâîðåííÿ áóäåìî âèêîíóâàòè äâîìà
åòàïàìè. Íà
ïåðøîìó - ââåäåìî ñèãíàë y0 äî âåðøèí, ïîâ'ÿçàíèõ ç ê³íöåâîþ, ÿêùî âåðøèíà óìîâíà, òî ââåäåìî
+1
Z1
ÑT
Z2
S T
& ÏÇÏ
“Ïóñê”
Ѳ
R ÐÌÊ Y
X A ÑÔÌÎ y0
.... yi Z1 ÑÔÀ
äî ÎÀ Z2
Ìàë.4.2. Ñòðóêòóðíà
ñõåìà àâòîìàòà ç ÊÀ.
äîäàòêîâó îïåðàòîðíó âåðøèíó ç ñèãíàëîì y0. Êð³ì òîãî, ââåäåìî äîäàòêîâ³
âåðøèíè áåçóìîâíîãî ïåðåõîäó, âèõîäÿ÷è ç òèõ æå ì³ðêóâàíü, ùî ³ äëÿ àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ. Áóäåìî, îäíàê, ìàòè íà óâàç³, ùî äëÿ àâòîìàòà ç ÊÀ ïåðåõ³ä ç îïåðàòîðíî¿
âåðøèíè ïðèð³âíþºòüñÿ äî áåçóìîâíîãî, òîìó â îäí³é òî÷ö³ ìîæå ñõîäèòèñÿ áóäü-ÿêà ê³ëüê³ñòü
áåçóìîâíèõ ïåðåõîä³â àáî ïåðåõîä³â ç îïåðàòîðíèõ
âåðøèí ³ ò³ëüêè îäèí ïî
ñòèííîñò³ ËÓ, ùî
ïåðåâ³ðÿºòüñÿ. Íà äðóãîìó åòàï³
âèä³ëèìî ì³êðîêîìàíäè çàäàíîãî
ôîðìàòó, êîðèñòóþ÷èñü òèìè æ ïðàâèëàìè, ùî ³ äëÿ àâòîìàòà ç ÏÀ. Ç âðàõóâàííÿì
âèùåñêàçàíîãî îòðèìàºìî
ïåðåòâîðåíó ÃÑÀ (ìàë. 4.3).
4.3.Ôîðìóâàííÿ âì³ñòó êåðóþ÷î¿ ïàì'ÿò³.
Ïðè ôîðìóâàíí³ âì³ñòó êåðóþ÷î¿ ïàì'ÿò³ ñêîðèñòàºìîñÿ òèì æå
êîäóâàííÿì íàáîð³â ì³êðîîïåðàö³é
ËÓ, ùî ³ äëÿ àâòîìàò³â ç
ÏÀ ³ ïðèðîäíîþ àäðåñàö³ºþ (òàáë.
2.3, 2.4). Äëÿ àäðåñàö³¿ ì³êðîêîìàíä
âèïèøåìî ¿õ ïðèðîäí³ ïîñë³äîâíîñò³ òàê ñàìî, ÿê ³ äëÿ àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ, âðàõîâóþ÷è,
ùî ïðèðîäíèì ââàæàºòüñÿ ò³ëüêè ïåðåõ³ä ïî ³ñòèííîñò³ ËÓ.
a1=[O1,O14]
a2=[ O2
,O19 ,O18 ,O46 ,O6 ,O42
,O43 ,O44 ,O9 ,O38 ]
a3=[ O3
,O15 ,O17 ]
a4=[ O4
,O5 ,O7,O8]
a5=[ O10
]
a6=[ O11
,O13]
a7=[ O12]
a8=[ O16,O29,O30,O25,O37,O35,O36]
a9=[ O20
,O22 ]
a10=[ O21,O23]
a11=[ O26,O32,O33]
a12=[ O27
,O24 ,O45]
a13=[ O34]
a14=[ O39]
a15=[ O40]
a16=[ O41]
a17=[ O28]
a18=[O31]
Ïåðåðàõóºìî â òàáëèö³ àäðåñàö³¿ (òàáë. 4.1) ï³äðÿä âñ³
ïîñë³äîâíîñò³ a1-a18 ³ çàêîäóºìî ¿õ
R-ðîçðÿäíèì êîäîì. R=]log2N[, N-ê³ëüê³ñòü ì³êðîêîìàíä(N=46,
R=6). Çàêîäóºìî òàêîæ îïåðàòîðè Yi,
ïîñòàâèâøè ¿ì ó â³äïîâ³äí³ñòü ï`ÿòèðîçðÿäíèé
êîä. Ó òàáëèö³ 4.2 â³äîáðàçèìî âì³ñò êåðóþ÷î¿ ïàì'ÿò³, çàïîâíèâøè ïîëÿ FX, FY,
FA.
Òàáëèöÿ 4.1.
Àäðåñàö³ÿ ÌÊ. ìê À1À2À3À4À5À6 O1 000000 O14 000001 O2 000010 O19 000011 O18 000100 O46 000101 O6 000110 O42 000111 O43 001000 O44 001001 O9 001010 O38 001011 O3 001100 O15 001101 O17 001110 O4 001111 O5 010000 O7 010001 O8 010010 O10 010011 O11 010100 O13 010101 O12 010110 O16 010111 O29 011000 O30 011001 O25 011010 O37 011011 O35 011100 O36 011101 O20 011110 O22 011111 O21 100000 O23 100001 O26 100010 O32 100011 O33 100100 O27 100101 O24 100110 O45 100111 O34 101000 O39 101001 O40 101010 O41 101011 O28 101100 O31 101101
Òàáëèöÿ 4.2
Âì³ñò
êåðóþ÷î¿
ïàì`ÿò³. ¹ A FY FX FA Îï. A1A2A3A4A5À6 T1T2T3T4T5T6 T7T8T9 T10T11T12T13T14T15 O1 000000 000000 100 000010 O14 000001 000000 000 001101 O2 000010 000000 101 001100 O19 000011 000000 110 011110 O18 000100 000000 001 000111 O46 000101 010000 110 101101 O6 000110 000010 101 101100 O42 000111 000111 101 101010 O43 001000 000000 010 101011 O44 001001 010001 100 011010 O9 001010 001000 100 010100 O38 001011 101010 000 000000 O3 001100 000000 110 001111 O15 001101 000001 100 010111 O17 001110 000000 000 011010 O4 001111 000000 001 001101 O5 010000 000000 010 001010 O7 010001 000110 110 010011 O8 010010 101100 000 000000 O10 010011 000111 000 010110 O11 010100 000000 110 011010 O13 010101 100111 000 000000 O12 010110 001001 000 011010 O16 010111 000000 110 001010 O29 011000 000110 110 000111 O30 011001 000000 011 000110 O25 011010 000100 100 100010 O37 011011 001010 001 001011 O35 011100 000000 010 001010 O36 011101 000001 000 001001 O20 011110 001101 001 100000 O22 011111 000101 000 100110 O21 100000 001110 011 101001 O23 100001 000000 000 011010 O26 100010 000000 101 100101 O32 100011 000000 110 101000 O33 100100 000000 000 001010 O27 100101 000000 110 011000 O24 100110 001111 110 000101 O45 100111 100011 000 000000 O34 101000 100000 000 000000
Òàáëèöÿ 4.2.
(ïðîäîâæåííÿ) O39 101001 100000 000 000000 O40 101010 100000 000 000000 O41 101011 100000 000 000000 O28 101100 001011 000 010001 O31 101101 100000 000 000000
4.4.Ñèíòåç
ñõåìè àâòîìàòà.
Ïðè ñèíòåç³ ñõåìè ñêîðèñòàºìîñÿ âæå ðîçðîáëåíèìè âóçëàìè äëÿ
àâòîìàò³â ç ÏÀ ³ ïðèðîäíîþ àäðåñàö³ºþ.
ÑÔÀ àâòîìàòà ç ÊÀ àíàëîã³÷íà ÑÔÀ àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ.
Ñõåìè ÑÔÌÎ, ÐÌÊ àíàëîã³÷í³ â³äïîâ³äíèì âóçëàì àâòîìàòà ç ÏÀ (ðîçä.2.4), à ñõåìà ËÀÌÊ çàïîçè÷åíà ç àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ (ðîçä.3.4). ³äì³íí³ñòü ïîëÿãຠëèøå â òîìó, ùî
äëÿ ÐÌÊ áóäå ïîòð³áíî 15
áàçîâèõ åëåìåíò³â.
Âðàõîâóþ÷è âèùåñêàçàíå, ïîáóäóºìî
ñõåìó àâòîìàòà ç êîìá³íîâàíîþ àäðåñàö³ºþ ì³êðîêîìàíä(ìàë.
4.4).
5. ÏÎвÂÍßËÜÍÀ
ÕÀÐÀÊÒÅÐÈÑÒÈÊÀ ÀÂÒÎÌÀÒ²Â.
5.1.
ϳäðàõóíîê àïàðàòóðíèõ âèòðàò.
Âèçíà÷èìî àïàðàòóðí³
âèòðàòè íà êîæíèé ç àâòîìàò³â. Îñê³ëüêè
ñèíòåç ë³÷èëüíèêà íå áóâ îáîâ'ÿçêîâèì, òî ïðè âèçíà÷åíí³ àïàðàòóðíèõ
âèòðàò áóäåìî ââàæàòè éîãî
äèíèì âóçëîì.
1.
Ó
àâòîìàò³ ç ïðèìóñîâîþ àäðåñàö³ºþ ñõåìà ÑÔÀ ì³ñòèòü 28 ëîã³÷íèõ åëåìåíò³â, ÑÔÌÎ
- 57 ËÅ, âóçîë çàïóñêó ³ ñõåìà
&" - 4 ËÅ ³, êð³ì òîãî, íåîáõ³äíî 6 åëåìåíò³â-³íâåðòîð³â äëÿ îòðèìàííÿ ñèãíàë³â ùX1...ùX3,ùP1...ùP3 Òàêîæ
ïîòð³áíî 27 åëåìåíò³â äëÿ ÐÀÌÊ ³ ÐÌÊ.
Òàêèì ÷èíîì, ñóìàðíå ÷èñëî ËÅ
äîð³âíþº 122. Äëÿ ïîáóäîâè
ÐÀÌÊ ³ ÐÌÊ òàêîæ áóäå ïîòð³áíî 27 òðèãåð³â. ʳëüê³ñòü ÏÇÏ- 7.
2.
Ó
àâòîìàò³ ç ïðèðîäíîþ àäðåñàö³ºþ ñõåìà ÑÔÀ ì³ñòèòü 12
ëîã³÷íèõ åëåìåíò³â, ÑÔÌÎ - 68 ËÅ, âóçîë ñêèäàííÿ - 2 ËÅ
, êð³ì òîãî, íåîáõ³äíî 6 åëåìåíò³â-³íâåðòîð³â äëÿ îòðèìàííÿ ñèãíàë³âùX1...ùX3,ùP1...ùP3
10 åëåìåíò³â äëÿ ÐÌÊ. Òàêèì ÷èíîì, ñóìàðíå ÷èñëî ËÅ äîð³âíþº 98. Äëÿ ïîáóäîâè ÐÌÊ
òàêîæ áóäå ïîòð³áíî 10 òðèãåð³â.
ʳëüê³ñòü ÏÇÏ- 4. Ñõåìà
òàêîæ ì³ñòèòü îäèí ë³÷èëüíèê.
3. Ó àâòîìàò³ ç êîìá³íîâàíîþ àäðåñàö³ºþ ñõåìà ÑÔÀ ì³ñòèòü
10 ëîã³÷íèõ åëåìåíò³â, ÑÔÌÎ - 57 ËÅ, âóçîë çàïóñêó ³ ñõåìà “&" - 4 ËÅ ³, êð³ì
òîãî, íåîáõ³äíî 6 åëåìåíò³â-³íâåðòîð³â äëÿ îòðèìàííÿ ñèãíàë³â ùX1...ùX3,ùP1...ùP3
15 åëåìåíò³â äëÿ ÐÌÊ. Òàêèì ÷èíîì, ñóìàðíå ÷èñëî ËÅ äîð³âíþº 92. Äëÿ ïîáóäîâè ÐÌÊ
òàêîæ áóäå ïîòð³áíî 15 òðèãåð³â.
ʳëüê³ñòü ÏÇÓ- 5. Ñõåìà òàêîæ ì³ñòèòü îäèí ë³÷èëüíèê.
Ñêëàäåìî çâåäåíó
òàáëèöþ âèòðàò íà ñèíòåçîâàí³ àâòîìàòè.(òàáë. 5.1.)
Òàáëèöÿ
5.1.
Àïàðàòóðí³
âèòðàòè äëÿ ñèíòåçîâàíèõ
àâòîìàò³â. Òèï àâòîìàòà Ëîã³÷í³ åëåìåíòè Òðèãåðè ÏÇÏ Ë³÷èëüíèêè ÏÀ 122 27 7 0 ÏðÀ 98 10 4 1 ÊÀ 92 15 5 1
5.2. Âèçíà÷åííÿ
àâòîìàòà ç ì³í³ìàëüíèìè àïàðàòóðíèìè
âèòðàòàìè.
Çàïîâíèìî òàáëèöþ, äå äëÿ êîæíîãî àâòîìàòà
çíàêîì “+" â³äì³òèìî
ì³í³ìàëüí³ âèòðàòè íà
äàíèé òèï åëåìåíò³â, à çíàêîì “-" -íåì³í³ìàëüí³
(òàáë. 5.2.).
Òàáëèöÿ
5.2. Òèï àâòîìàòà Ëîã³÷í³ åëåìåíòè Òðèãåðè ÏÇÏ Ë³÷èëüíèêè ÏÀ - - - + ÏðÀ - + + - ÊÀ + - - -
ßê âèäíî ç òàáëèö³ 5.2., àâòîìàò ç ïðèðîäíîþ àäðåñàö³ºþ
âèãðຠïî äâîì ïàðàìåòðàì:
ïî ê³ëüêîñò³ òðèãåð³â
ÏÇÏ.
Äëÿ ï³äòâåðäæåííÿ ïðàâèëüíîñò³ âèáîðó àâòîìàòà çàñòîñóºìî òàêîæ îö³íêó
çà Êâàéíîì (çà ñóìàðíîþ ê³ëüê³ñòþ
âõîä³â åëåìåíò³â).
Áóäåìî ââàæàòè ê³ëüê³ñòü
âõîä³â ó ËÅ - 4, ó òðèãåðà
- 4, ó ÏÇÏ -9 ³ ó ë³÷èëüíèêà - 9. Ç âðàõóâàííÿì âèùåíàâåäåíèõ
çíà÷åíü, äëÿ àâòîìàòà ç ÏÀ ïîêàçíèê îö³íêè ñêëàäå - 659, äëÿ àâòîìàòà ç ÏðÀ -
477, äëÿ àâòîìàòà ç ÊÀ- 482.
ßê âèäíî ç ïðèâåäåíèõ îö³íîê, àâòîìàò ç ïðèìóñîâîþ
àäðåñàö³ºþ äàëåêî íå îïòèìàëüíèé, à àâòîìàòè ç ïðèðîäíîþ ³ êîìá³íîâàíîþ
àäðåñàö³ºþ ïî âèòðàòàõ
ïðàêòè÷íî îäíàêîâ³, àëå âñå æ àâòîìàò ç ÏðÀ ìຠäåÿêó ïåðåâàãó ïåðåä àâòîìàòîì
ç ÊÀ. Òàêèì ÷èíîì,
ðåçóëüòàòîì ïðîåêòóâàííÿ áóäå ñõåìà àâòîìàòà ç ïðèðîäíîþ àäðåñàö³ºþ ì³êðîêîìàíä.
|
