Aszinkron sorrendi hálózatok
©
Benesóczky Zoltán 2004 A jegyzetet a szerzıi jog védi. Azt a BME hallgatói használhatják, nyomtathatják tanulás céljából. Minden egyéb felhasználáshoz a szerzı belegyezése szükséges.
1
Az aszinkron hálózat struktúrája: visszacsatolt kombinációs hálózat
q Q
Q(q,x)
Z Z(q, X)
X
A mőködés egyszerősített modellje q0
Q0
qi
Qi
qn
Qn Q(q,X)
dt0 dt1 dtn
q0 qi Z0
qn Z(q, X)
Zk Zp
X0 Xj Xm
Egy állapot stabil valamely X kombináció esetén, ha Q (q, X ) = q
2
bemeneti
Egy állapot instabil valamely X bemeneti kombináció esetén, ha Q(q, X ) ≠ q Példa. Hogyan viselkedik az alábbi aszinkron sorrendi hálózat az y1y0=11 kódú állapotból indulva, az X1X0= 10, 00, 01 bemeneti sorozat hatására? 00/0,11/1
x1x0/z
01/1
01/1,10/0 00
01 00/0 10/0,11/0
10/1,01/1 11/0 10
11 00/0
00/1 q1q0/x1x0 00 01 11 10
10/0 00 00/0 00/0 10/0 10/1
01 01/1 01/1 --/00/1
11 00/1 11/0 00/0 --/-
3
10 01/0 11/0 11/0 00/1
X1X0=10 q1q0/x1x0 00 01 11 10
00 00/0 00 10/0 10/1
01 01/1 01/1 -00/1
q1
Q1
q0 X1
Q0
11 00/1 11 00/0 --
1 dt0
1
dt1
1
q0 q1
10 01/0 11/0 11/0 00/1
1 1
Z Z(q, X)
0
Q(q,X)
0 X0
X1X0=00 q1q0/x1x0 00 01 11 10
q1 q0 X1 X0
0 0
01 01/1 01/1 -00/1
00 00/0 00 10/0 10/1
Q1 Q0
11 00/1 11 00/0 --
1 0
dt0 dt1
Q(q,X)
4
q1 q0
10 01/0 11/0 11/0 00/1
1 1
Z Z(q, X)
0
X1X0=00 q1q0/x1x0 00 01 11 10
01 01/1 01/1 -00/1
00 00/0 00 10/0 10/1
11 00/1 11 00/0 --
1 q1 X1 X0
0 0
X1X0=01 q1q0/x1x0 00 01 11 10
q0
dt0 dt1
Q0
00 00/0 00 10/0 10/1
q0
X0
0
q0
1 0
Z 1
Z(q, X)
Q(q,X)
q1 X1 0
Q1
q1
10 01/0 11/0 11/0 00/1
11 00/1 11 00/0 --
01 01/1 01/1 -00/1
Q1
0 0
Q0
q1 dt0 dt1
Q(q,X)
1
5
q0
10 01/0 11/0 11/0 00/1
1 0
Z Z(q, X)
1
X1X0=01 q1q0/x1x0 00 01 11 10
00 00/0 00 10/0 10/1
q1 q0 X1 0 X0
Q1
0 1
q1 dt0 dt1
Q0
q0
10 01/0 11/0 11/0 00/1
0 0
Z 1
Z(q, X)
Q(q,X)
1
X1X0=01 q1q0/x1x0 00 01 11 10
00 00/0 00 10/0 10/1
q1 q0 X1 0 X0
11 00/1 11 00/0 --
01 01/1 01/1 -00/1
11 00/1 11 00/0 --
01 01/1 01/1 -00/1
Q1
1 Q0
q1
0 dt0 dt1
Q(q,X)
1
6
q0
10 01/0 11/0 11/0 00/1
0 1
Z Z(q, X)
1
Összefoglalva: X1X0 10 00 00 Állapot (q1q0) 11 11 10 Kimenet 0 0 1
01 10 1
01 00 1
01 01 1
Az aszinkron hálózat mőködtetésének feltételei FMA (Fundamental Method Asyncronous) feltételek: • A bemeneten csak 1 Hamming távolságú változásokat engedünk meg. • Bemeneti változás csak stabil állapotban megengedett.
7
Mi történhetne, ha az alábbi hálózatra a x1x0=11 bemenet mellett stabil 00 kódú állapotban x1x0=11 után 00-át adnánk? (Nem tartjuk be az FMA feltételt.) q1q0/x1x0 00 01 11 10
00 00/0 00/0 10/0 10/1
01 01/1 01/1 --/00/1
11 00/1 11/0 00/0 --/-
10 10/0 11/0 11/0 11/1
x1x0=11-01-00 bemenet érzékelési sorrend esetén: X1X0 11 01 01 00 00 Állapot 00 00 01 01 00 Kimenet 1 1 1 0 0 11-10-00 érzékelési sorrend esetén: X1X0 11 10 01 01 Állapot 00 00 10 11 Kimenet 1 0 1 0
00 11 0
00 10 1
Több Hamming távolságú bemeneti kombináció változás esetén a bemenet érzékelési sorrendjétıl függıen hibás választ adhat a hálózat! Itt feltételeztük, hogy egy-egy változás érzékelése között stabilizálódik a hálózat, s csak utána érzékeli a következı változást. A valóság rosszabb, a hálózat stabilizálódása elıtt érzékelhet újabb változást! 8
További problémák az aszinkron sorrendi hálózatban. q1q0/x1x0 00 01 11 10
00 00/0 00/0 10/0 10/1
01 01/1 01/1 00/1 01/1
11 00/1 00/0 00/0 10/0
10 01/0 11/0 11/0 00/1
Mi történhetne, ha az alábbi hálózatra a x1x0=10 bemenet mellett stabil 11 kódú állapotban x1x0=10 után 11-et adunk? Ez 1 Hamming távolságú változás, betartjuk az FMA feltételt. Az 11 kódú állapot után a 00 kódú következne, ehelyett a hálózat elıször 01-et vagy 10-át érzékel. q1q0=01 érzékelése esetén: X1X0 10 11 Állapot (qt) 11 11 Kimenet 0 0 q1q0=01 érzékelése esetén: X1X0 10 Állapot (qt) 11 Kimenet 0 Hibás mőködés! 9
11 11 01! 00 0 1
11 11 0
11 10! 0
Ha az egymást követı állapotok kódjának Hamming távolsága 1-nél nagyobb, akkor a szekunder változók érzékelési sorrendjétıl függıen hibásan mőködhet a hálózat. Versenyhelyzet van a szekunder változók között. A versenyhelyzet kritikus, ha hibás mőködéshez vezethet. Az alábbi állapottáblán az x1x0=00 bemenetre stabil 10 állapotból indulva, 01 bemenetre a 2 Hamming távolságú 01 állapot következne, azonban ez nem vezet hibás mőködéshez, a versenyhelyzet nem kritikus. A hálózat elıbb-utóbb a kívánt végállapotba kerül. q1q0/x1x0 00 01 11 10
00 00/0 00/0 10/0 10/1
01 01/1 01/1 00/1 01/1
11 00/1 00/0 00/0 10/0
10 01/0 11/0 11/0 00/1
Az aszinkron hálózat nem tartalmazhat kritikus versenyhelyzetet! A kritikus versenyhelyzetet megfelelı állapotkódolással lehet kivédeni. (Lásd késıbb.)
10
Az aszinkron hálózat állapotkódolásánál az elsıdleges cél, a hálózat helyes mőködése. A helyes mőködés egyik feltétele, hogy a hálózat ne tartalmazzon kritikus versenyhelyzetet. Ezt többféleképpen elérhetjük: Versenyhelyzet mentes kódolás (szomszédos kódolás) Ennél a módszernél az egymást követı állapotokat szomszédosan kódoljuk, vagyis az egymást követı állpotok kódja 1 Hamming távolságú. (Ez a kódolás nem összetévesztendı a szinkron hálózatok azonos nevő kódolási módszerével, melynek algoritmusa más!) bemenet: x1,x0
állapot:Q1Q0
10
00 A 00
00 00/0
B 01 01
10 D 10
11/0 11
01
11
B
D
C Q1 Q0
C 11
11
A
Átvezetı állapotok felvétele A szomszédos kódolás ill. a szomszédossági követelmények teljesítése vagy lehetséges közvetlenül, a minimális számú szekunder változóval, vagy sem. Ha nem teljesíthetı, akkor az állapotgáfot kiegészítjük instabil állapotokkal úgy, hogy azok egyrészt nem változtatják meg a lényegi mőködést (hogy adott bemenetre hol stabilizálódik a hálózat), másrészt a kiegészítés után már szomszédosan kódolható lesz a hálózat. bemenet: x1,x0
állapot:Q1Q0
10
00 A
00
B 01
10
10 D
C 11
11
01 10
00 00 A
B
A
D
01 E 10
10 F
D 11 11
átvezetõ állapot
E
01
C
C
Q2 F Q1 Q0
11
átvezetõ állapot
B
01
12
Instabil állapotok módosítása Az elıbbi módszer a minimálisnál több állapothoz vezethet. Ha az állapottábla tulajdonságai megengedik, akkor más lehetıség is adódhat a versenyhelyzet mentes kódolásra. Azokat az állapotátmenteket, amelyek közvetlenül vezetnek egyik állapotból egy másikba megpróbálhatjuk más állapotokon keresztül vezetni. Ha egy xi bementre mondjuk egy Q1 stabil állapotból a Q2 stabilba kellene jutni, de van olyan Qj állapot, melyre vagy nincs elıírva, hogy hová menjen az xi bementre, vagy az xi-re szintén a Q2-be vezet, akkor a közvetlen Q1-Q2 átmenet helyett a Q1-Qj-Q2 átmentet valósítjuk meg, ha az állapottáblát úgy módosítjuk, hogy a Q1-bıl xi-re Qj-be vezetjük az hálózatot, Qj-bıl pedig Q2-be. Az ilyen a módosítások nem okoznak változást a lényegi mőködésben, viszont a szomszédossági követelmények számát csökkenthetik, így kis szerencsével a minimális számú szekunder változóval szomszédosan kódolhatóvá válhat a hálózat.
13
bemenet: x1,x0
állapot:Q1Q0
10
00
10
00
00
00
A
B
A
B
01
01
10
10 D
10 C
D
C
11 11
11 ,10 01
11
01 A
B
D
C Q1 Q0
Versenyhelyzetet megengedı kódolás Az állapottábla alapján megnézzük, hogy mely szomszédossági követelményeket nem szükséges betartani. Nyilván azokat, amelyek be nem tartása versenyhelyzetet ugyan okoz, de az nem kritikus. Ha ezzel sikerül lecsökkenteni a követelmények számát annyira, ami már teljesíthetı a minimális számú szekunder változóval, akkor ez is megfelelı kódoláshoz vezet.
14
Aszinkron sorrendi hálózat analízise Analizáljuk az alábbi kapcsolási rajzzal megadott ASSH-ot! R Q S q
Az analízishez elıször megszakítjuk a visszacsatolás(okat) majd felírjuk a szekunder változó(k) függvényét. Q=/R(S+q) Ez alapján kitöltjük a kódolt állapottáblát. Majd felrajzoljuk az állapotgráfot. Q 0 0 0 1 1 0 0 1
SR=00,01,11
SR=10,00 SR=01,11
0 q S
1 SR=10
R A kapcsolás az SR flip-flopot realizálja.
15
Aszinkron flip-flopok A szinkron hálózatokhoz hasonlóan az aszinkron hálózatok is megvalósíthatók flip-flopok segítségével. Az SR flip-flop eredeti állapottáblája és szokásos megvalósításai: /S
R
Q
/R
Q
S Q 0 0 1 0 -
Q 0 0 1 0 -
1 1 R
Q S
1 1 R
Q S
Mőködése szövegesen: SR=10 1-be ír (Q=1) SR=01 0-ba ír (Q=0) SR=00 megtartja állapotát (Q=q) A szekunder változók igazság táblái alapján a szinkron hálózatokhoz hasonlóan a vezérlési tábla kitöltéséhez itt is megadható egy segéd táblázat: qQ SR /S/R 00 0101 10 01 10 01 10 11 -0 -1 16
DG flip-flop (latch) A DG flip-flop Karnaugh táblája és állapotgráfja: Q DG=00,01,10 0 0 1 0 0 1 0 1 1 q D G
DG=01
DG=00,10,11 1
DG=11
A DG flip-flop mőködése szövegesen: G=1 átlátszó (Q=D) G=0 megırzi a G=0 elıtti állapotát A segédtáblázat a vezérlési függvényekhez: qQ 00 01 10 11
DG 0-, -0 11 01 1-,-0
Egyes esetekben többféle kitöltési lehetıség is van.
17
Példa: Készítsünk DG flip-flopot! A megvalósítandó aszinkron állapottábla. Ez itt egyben az egyetlen szekunder változó Karnaugh táblája is. Q Q 0 0 1 0 0 0 1 0 1 0 1 1 q 1 0 1 1 q D D G G Ezt kell megvalósítani visszacsatolt kombinációs hálózattal. Az Karnaugh táblát hazárdmentesen kell lefedni! A hazárd hibás mőködéshez vezethet!
A hazárdmentes lefedés: Q=qD + q/G + DG A kapcsolási rajz:
D
Q G
18
Készítsünk negált bemenető SR flip-flop segítségével DG flip-flopot. /S /R Q 1 1 0 1 - - 1 0 0 1 0 - 1 - 1 0 1 1 1 0 1 1 q q D G A vezérlési táblák az segtíségével tölthetık ki.
qQ 00 01 10 11
SR 010 01 -0
G alábbi
D
SR
/S/R 101 10 -1
A hazárdmentes lefedések: /S=/D + /G /R=D + /G A homogén NAND-os megvalósítás: G
/S Q
D
/R
19
G segédtábla
q D
Az alábbi egyenletekkel adott egy aszinkron sorrendi hálózat: (X1, X2 a bemenetek, q1, q2 a két RS flip-flop kimenete.) S1 = /X2.q2./q1 R1 = /X2.q2.q1 S2 = X1.X2 R2 = /X2 Z = q1 Tartalmaz-e a hálózat kritikus versenyhelyzetet? S1
R1
1
Q1
1
1 q2
x2
1
q1 x1
S2
1
x2
q2 q1 x1
R2 1
1
1
1
1
1
1
1
1
q2
1 x2
q1 x1
1
1
1
1
q2 1 x1
q1 x2
Q2
1
1
1
1
x2
1
q2
1
1
1
1
q2
1
q1 x1
x1
q1 x2
Q1Q2 00 00 01 00 10
01 01 10
00
11 11 00
10 10 11 10 x1
20
q2 q1 x2
