Digitális technika
I.
ELSŐ JAVÍTOTT KIADÁS 2004 Utolsó frissítés időpontja: 04-12-18 (terjedelem: 48 A4-es lap)
(A jegyzetben található estleges hibákért, elírásokért elnézést kérek, és a hibák jelzését köszönettel fogadom.)
©GABA
1
Logikai tervezés Logikai feladat definiálása: A logikai feladat definiálását a könnyebb megérthetőség miatt tegyük egy ellenpéldával Vegyünk egy analóg feszültségerősítő: Ube
Uki=AUbe
Ube = bemenő jel Uki = kimenő jel A = erősítés Jól látszik, hogy analóg rendszer esetén, csak az van definiálva, hogy a be és a kimeneti jel között mi a kapcsolat (jelen esetben: Uki=AUbe), míg a bemeneti érték egy bizonyos tartományon belül végtelen számú lehet, és ehhez végtelen számú kimeneti érték tartozhat. Def: (Analóg jel) Az olyan jeleket, amelyek egy tartományon belül tetszőleges értéket vehetnek fel, és a különböző értékekhez különböző információtartalmat rendelünk, analóg jelnek nevezzük. Ezzel szemben egy digitális erősítőben a bemeneti és a kimeneti jelek csak véges számú (diszkrét) értéket vehetnek fel. (bináris rendszert használ) Def: (Digitális változó) Eldöntendő kérdésre adott egyértelmű válasszal adható meg. Def: (Logikai érték) A kérdésre adott válasz igen vagy nem. (azaz 1 vagy 0)
Példa logikai hálózatra: Lift LIFT feltételek
Bementi érzékelők
bemeneti jelérték
Állapotokról ad jelet Pl.: (elmozdulást érzékel)
Logikai szerv/hálózat (LH)
Logikai algoritmusokkal logikai függvényeket old meg. (mozgassa-e ?)
kimeneti jelérték
Kimeneti szerv
következmény
A jelet illeszti Gyenge áramból erősáramot csinál (relét kapcsol, így mozog a motor )
2
Példa logikai tervezésre: Liftmotor mozgatás Ebben a feladatban azt definiáljuk (az úgynevezett igazságtábla segítségével), hogy adott bemeneti értékek mellet mikor induljon el a lift. Jelen esetben az igazságtáblánknak 24=16 sora kell, hogy legyen, mert 4 bemeneti változónk van. Bemeneti változó:
- nyomtak-e gombot - liftajtó be van-e csukva - van-e valaki a liftben - túlterhelt-e
Kimeneti változó:
Bekapcsolja-e a motort
GNY 0 0 1 1 1 1
LZ 0 0 0 1 1 1
VL 0 1 1 1 1 0
TT 0 0 0 0 1 1
(GNY) (LZ) (VL) (TT)
Liftmotor 0 0 0 1 0 -
nem indul nem indul nem indul indul nem indul NTSH
NTSH: nem teljesen specifikált hálózat, ez azt jelenti, hogy ilyen eset nem valószínű, hogy előfordulhat. (Kötött jelet használhatunk.)
Logikai hálózatok csoportosítása a megoldandó logikai feladatok szerint Mivel a logikai feladat megoldása szempontjából, nem mindig elég a mindenkori fennálló pillanatnyi bemeneti kombinációk figyelembevétele a kimeneti kombinációk előállításához, szükségünk lehet másodlagos (szekunder) feltételeknek megfelelő szekunder kombinációkra is. Magyarul, visszatérve a liftes példához: nem elég, ha a liftmotor a feltételek teljesülése után, csak úgy elindul, mert nem mindegy melyik irányba forog. Hiszen, ha az 1.-ről akarunk 3
eljutni a 3.-ra, akkor más irányba kell forognia, mintha az 5.-ről akarnánk eljutni a 3.-ra. Tehát a szekunder változó ebben az esetben a felvonó mindenkori helyzetéről ad felvilágosítást érzékelők segítségével. (A szekunder változó feladata a hálózat belső állapotának figyelése.) Ezek alapján kétféle hálózatot különböztetünk meg - Sorrendi (szekvenciális) logikai hálózatról beszélünk: Ha a mindenkori kimeneti kombinációt, nemcsak a pillanatnyi bemeneti kombináció, hanem a korábban fennállt bementi kombinációk és azok sorrendje is befolyásolja. (A szekunder kombinációk segítségével az ilyen hálózatok képessé vállnak arra, hogy az ugyanolyan bemeneti kombinációkhoz más-más kimeneti kombinációt szolgáltassanak, attól függően, hogy a bemeneti kombináció fellépésekor, milyen értékű a szekunder kombináció) - Kombinációs logikai hálózatról beszélünk: Ha a mindenkori kimeneti kombinációk létrehozásához elég a bemeneti kombinációk pillanatnyi értéke.
A logikai hálózat és a logikai rendszer kapcsolata Példa logikai rendszerre (LR) - logikai hálózatokból épül fel (természetesen be és kimenetekkel)
LR LH1
LH2
LH3
összeköttetés LH4
LH5
LH6
Egy bonyolult logikai feladat megoldásához nem célszerű egy bonyolult logikai hálózatot (LH) terveznünk, sokkal célszerűbb egyszerű LH-k összehangolt működésével megoldanunk a problémát. Az LH-k összehangolt működésű rendszerét logikai rendszernek (LR) nevezzük.
A tervezés mozzanatai -
Tervdokumentációt kell készíteni a hálózatról o Egységes, szabványos jelölésrendszer szükséges A berendezésnek könnyen vizsgálhatónak kell lennie o Tagolt legyen (könnyen átlátható, javítható) o Hiba esetén csak adott modult keljen cserélni Gyárthatónak kell lennie o Mérőpontokat, tesztelő helyeket kell kialakítani o Építőelem készletet figyelembe kell venni
4
Logikai függvény Logikai 0 Logikai 1
(alacsony feszültség, low) (magas feszültség, high)
0,0-0,7 V 2,4-5,0 V
TTL rendszereknél 0 1 0 V zaj távolság
5V
MOS rendszereknél 0
1
0 V a tartományt felezi max 18 V
- Hálózatok fajtái - Pneumatikus hálózatok (bánya, lőgyár, stb) - Elektromos rendszerek
Logikai áramkörök -
DDL: (Dióda dióda logika) Diódákból és ellenállásokból realizált függvény. Passzív áramköri elemekből áll. (Gond vele, hogy bizonyos számú elem felett elfogy a feszültség )
-
DTL: Itt tranzisztoros erősítéssel orvosolták a feszültség elfogyásának hibáját.
-
TTL: (Multi emitters tranzistoral = tranzisztor tranzisztor logika) Főleg tranzisztort tartalmaz (Napjainkban is használatos). Bipoláris tranzisztorokból épül fel.
-
MOS: TTL-ekkel hasonló, de a kapcsolók térvezérlésű tranzisztorok (FET = Field effect) benne. Nem fogyaszt elektromos teljesítményt.
5
Logikai műveletek -
És kapcsolat (AND) 0·0=0 0·1=0 1·0=0 1·1=1
kommutatív
Csak akkor ad 1-et, ha az összes változó 1. Kiterjeszthető több tagra is. -
Vagy kapcsolat (OR) 0+0=0 0+1=1 1+0=1 1+1=1
kommutatív
Ha bármely változó értéke 1, akkor a fv. 1-et ad. Kiterjeszthető több tagra is -
Tagadás (NOT) (szokták negálásnak is nevezni)
0= 1 1= 0
páratlan tagadás Î
negált állapot
0= 0
páros tagadás Î
eredeti állapot
1= 1
6
Logikai változók A·0 ≡ 0 A·1 ≡ A A· A ≡0 azonosság
A+0≡A A+1≡1 A+ A ≡1
A+B ≡ B+A A·B ≡ B·A A + B ≡ A · B De Morgan A ⋅B≡ A +B
A ≡A
(több tagra is igaz)
Ezek a függvények zárójelezhetők. Boole-algebra A+(B+C) = A+B+C A·(B·C) = A·B·C A+(B·C) = (A+B) · (A+C) A·(B+C) = (A·B)+(A·C) A „·” nagyobb prioritású, mint a „+”
Van egy logikai hálózatuk, hány függvénnyel írható le?
x1
z1
xn
zn Nb = 2n
bemeneti változó Nf = N K
NB
Nk=2m
bemeneti változó kimeneti változó kimeneti kombináció kombináció változó
= (2 m ) 2
n
-Példa: 416 logikai függvényt lehet definiálni 4 bemenet
2 kimenet
7
Logikai függvény 2 bemeneti- és 1 kimeneti változóra Függvényértékek FxR
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Bemeneti változó A 0011 B 0101 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
soha nem igaz ÉS, AND B tiltja A-t ≡ A (azonosan A) A tiltja B-t ≡ B (azonosan B) antivalencia, XOR OR, AVB (A vagy B) NOR ekvivalencia
NAND mindig igaz
A táblázat szimmetrikus, és az értékek egymás negáltjai (Pl.: az 5-ös a 10-esé)
F02 (A,B)=0 F12 (A,B)= A·B F22 (A,B)= A· B
F32 (A,B)= A· B + A·B = A·(B+ B ) = A F42 (A,B)= A ·B
F52 (A,B)= A B+AB = B(A+ A ) = B
AB-vel bővítjük
F62 (A,B)= A B+A B = A ⊕ B F72 (A,B)= A B+A B +AB = A B+A·(B+ B ) = A B+A+AB = A+B(A+ A ) = A+B F82 (A,B)= A B = A + B F92 (A,B)= A B +AB = A ⊗ B F102 (A,B)= B F112 (A,B)= A B +A B +AB = A B +A(B+ B ) = A B +A F122 (A,B)= A B + A B = A (B+ B ) = A
F132 (A,B)= A ⋅ B = A +B
8
F142 (A,B)= A ⋅ B = A + B
F152 (A,B)= 1
Logikai függvények leírása bemeneti független változók A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
fv. értékek C 0 1 0 1 0 1 0 1
F1 0 0 1 1 1 0 1 0
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F2 1 0 1 1 0 1
NTSH Kanonikus diszjunkt normálalak: (Az 1-es fv. értékkel rendelkezőket kell venni ) F1(A,B,C)= A B C + A BC+A B C +AB C F2(A,B,C)= A B C + A B C + A BC+ABC+(A B C +AB C ) NTSH Ezek a függvények egyszerűsíthetők, mert így bonyolultak. A függvények egyszerűsítésére több módszer is van.
Függvényegyszerűsítés kifejtéssel Def.: (Kifejtési tétel) Bonyolultabb fv. esetén az egyik változó értéket rögzítem ponáltnak és negáltnak, így leegyszerűsödik a feladat, majd a levezetés után visszaírjuk a bonyolultabb formulába. Példa: Tekintsük az előző példa F1 függvényét. F1(A,B,C)= A B C + A BC+ A B C + AB C F1(1,B,C)= 0B C + F1(0,B,C)= 1B C +
0BC+ 1 B C + 1B C = B C + B C = C (B+ B )= C 1BC+ 0 B C + 0B C = B C +BC= B(C+ C )=B
(A félkövérrel jelzett tagok kiesnek) Ezt a két függvényt kell összevonni, hogy megkapjuk a végeredményt:
9
F(A,B,C)= A·F1(1,B,C)+ A ·F1(0,B,C)=A C + A B
Másik alakban felírva: F(A,B,C)=[A+ F1 (0, B, C) ]+[ A + F1 (1, B, C) ]=(A+ B )( A +C) A disztjunktív kanonikus normálalak tulajdonságai: - ÉS kapcsolatok VAGY kapcsolata. - A logikai szorzatok azokból a függetlenváltozó-kombinációkból képezhetők, amelyekhez a függvény 1 értéke tartozik. - Mindegyik szorzatban az összes független változó szerepel ponált vagy negált alakban. A függvény felírható a 0 kimeneti függvényértékekre is F2(A,B,C) = (A+B+C)(A+B+ C )( A +B+ C )( A + B + C ) A konjunktív kanonikus normálalak tulajdonságai: - VAGY kapcsolatok ÉS kapcsolata. - A logikai összegek azokból a függetlenváltozó-kombinációkból képezhetők, amelyekhez a függvény 0 értéke tarozik. - Mindegyik összegben az összes független változó szerepel ponált vagy negált alakban. - Az egyes tényezőket alkotó logikai összegekben a 0 értékű logikai változók szerepelnek ponált és az 1 értékűek negált alakjukban. A diszjunktív alakot gyakrabban használják, de mindkét alak elfogadott. Speciális elemi függvények: „1”
Minterm
min
és kapcsolatok a fv.-ben
„0”
Maxterm
Min
vagy kapcsolatok a fv.-ben
B 0 0 1 1 0 0 1 1
F(A,B,C)=m23+m33+m43+m63 (A 2, 3, 4, 6-os sorban van 1-es fv. érték)
0 1 2 3 4 5 6 7
A 0 0 0 0 1 1 1 1
C 0 1 0 1 0 1 0 1
F 0 0 1 1 1 0 1 0
„term”-ek
F(A, B, C) =m03+m13+m53+m73 (A 0, 1, 5, 7-es sorban 0-ás fv. érték van, ami az 1-es negáltja) F(A, B, C) =F(A,B,C)= m 0 3 + m13 + m 5 3 + m 7 3 A mintermek negáltja maxtermeket eredményez: m 0 3 =M73 (0) 000 (7) 111
F(A,B,C)= m23+m33+m43+m63
m13 =M63 (1) 001 (6) 110 =
m 5 3 =M23 (5) 101 (2) 010
m 7 3 =M03 (7) 111 (0) 000
F(A,B,C)= M73˙M63˙ M23˙ M03
10
minterm
maxterm
Kapu áramkörök
ÉS (AND)
A B
VAGY (OR)
A
& 1
F(Q)
A˙B=F(Q)
F(Q)
A+B=F(Q)
F(Q)
A =F(Q)
B
NEGÁLT (NOT) A
1
A kör jelöli a negálást.
NEM ÉS (NAND)
A
&
A ⋅ B =F(Q)
B NEM VAGY(NOR) A B
1
F(Q)
A + B =F(Q)
Ez a kapu ≠ az előzővel: A B
ANTIVALENCIA (EXOR)
A
1 =1
F(Q)
A + B = F( Q )
F(Q)
A⊕B=F(Q)
B
11
EKVIVALENCIA ( EXOR )
A
=&
F(Q)
A⊗B=F(Q)
B Példa: (függvények realizálása)
Példa: (függvény kétszintű realizációja)
F(A,B,C) = ABC + ABC + A BC + ABC = AB(C + C) + A C( B + B) = AB + AC 1 1
Kétszintű realizációnak nevezzük (az inverter szint nem számít)
inverter szint
„és kapcsolatok” „vagy szintje kapcsolatok (a mintermeknél) ” szintje maxtermeknél „vagy kapcsolat” jönne)
12
Példa (2 bemenetű kapukból 4 bemenetű készítése)
Logikai fv. minimalizálása F(A,B,C)= m13+m33+m53+m73 F(A,B,C)= ABC + ABC + ABC +ABC= AC( B + B) + AC( B + B) = AC +AC=C(A+ A )=C 1 1 1 Magyarázat:
AB C 421 001 011 101 111
⇒ ⇒ ⇒ ⇒
ABC ABC ABC ABC
m13 m33 m53 m73
1 binér: 3 binér: 5 binér: 7 binér:
001 011 101 111
Definíció: (Szomszédos minterm) Ha van egy logikai változó amely az egyik minterben ponált a másikban negált értékével fordul elő és a többi logikai változó pedig mindkét mintermben adott bináris kombinációban megegyezik, akkor szomszédos mintermekről beszélünk. azonosak, csak az „A”-ban tér el Pl.: ABC ABC
Függvényminimalizálást a szomszédos mintermek megkeresésével tehetjük meg. A szomszédosság megállapítása után egyszerűsítünk. /mintermÆimplikáns (egyszerűsíthető)Æprimimplikáns (nem egyszerűsíthető)/
13
Mivel az algebrai minimalizálás nehéz és nem szemléletes bevezetjük a
Grafikai minimalizálást Karnough-Veitch tábla: Szomszédosság vizsgálata grafikusan így szomszédosak Ezek a számok az igazságtáblából származnak
Ami nincs jelölve az a negált érték A, B, C, B
0
1 0
A
0
1 1
1 4
0 3
1 5
2
0 7
AC +AC=C( A + A )=C (A mintermek párosával írhatók össze)
6
C
Tömbösítés szabályai - 2n (n=1, 2 , ...) minterm vonható be tömbbe (1, 2, 4, 6, 8, 16) - Egyetlen minterm több tömbben is szerepelhet. - Egymás mellett lévő sorokra, oszlopokra igaz.
Szomszédossági viszonyok
14
Feladat: (7 szegmenses dekóder kijelző tervezése)
hexadecimális megjelenítés (nemzetközi elnevezései a szegmenseknek :a, b, c, d, e, f, g )
0 1 2 3 4 5 6
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Ff 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1
D
0 1 2
1
3 4
1
5
8
1
1 A
9
0 1
4
6 7
0 0
1
1 7
6
1
13
1 8
2
0 5
0
12
0 3
1
15
14
1 9
B
1
10
11
10 11 12 13 14
C Azért az 1-eket vonjuk be tömbökbe, mert diszjunkt alakot nézünk. Ha egy tömb teljesen része egy másiknak, akkor azzal nem kell foglalkoznunk, mert számunkra a legnagyobb 2n méretű tömb kell.
15
Ez a tömb ezért nem számít, mert mind a C, mind a D egyszerre szerepel ponált és negált alakjával is.
Ff = A B + CD ( + A D + ) BD + AC + ABC (a zárójelben lévő tagot nem muszáj kiírni) -
NTSH esetén: Sokkal egyszerűbb lesz a függvény, mert ilyenkor mi választhatjuk meg (0 vagy 1), hogy mi legyen az értéke a nem teljesen specifikált helyzeteknek. Tekintsük a következő feladatot: Ismét 7 szegmenses kijelzőt tervezünk, de most csak 0-9ig tekintjük a számjegyeket a kijelzőn és a hexadecimálisokat kihagyjuk, ezért a hozzá tartozó függvényeket NTSH-nak vesszük (azaz közömbösnek).
15
0 1 2 3 4 5 6 7 8 9
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Fc 1 1 0 1 1 1 1 1 1 1 -
D
0 1 2
1
3
1 0
4
1
5
1 4
6
-
7
A
8 9
1 1
1
1 7
6
-
13
1 8
2
1 5
-
12
0 3
-
15
14
9
B
-
10
11
10
C
11 12
NTSH (don’t care) (közömbös állapot)
13 14 15
Ezeket az értékeket 0 vagy 1-ként is rögzíthetjük attól függően, hogy melyik jobb nekünk. Most az a jobb, ha 1-nek vesszük, mert így a tömbök többségét ki tudjuk ejteni.
Fc = A+B+ C +D (a zárójelben lévő tagot nem muszáj kiírni) Példa: (NTSH –ra, az igazságtáblát elhagyva) D
1
0 0
0
1 4
A
1 1
1
1 7
6
-
13
1 8
2
1 5
-
12
1 3
-
15
14
9
B
-
10
11
C
16
Példa: (5 változós fv egyszerűsítése)
Példa: (Hat változó esetén a Karnaugh-tábla, egy kocka lenne)
A példákból látható, hogy a grafikus egyszerűsítést egy közönséges ember maximum 6 változóig képes elvégezni, de már a 6. is komoly munka lenne. Számítógépen persze működhet még ennél is több változóra, de szükségünk van egy olyan módszerre, ami manuális módon nagyon sok fv.-re elvégezhető. A megoldás a:
Számjegyes minimalizálás A szomszédosság feltételei: - A decimális decimális index különbsége 2n, ahol n = 0, 1, 2, ..... Ez nem elégséges feltétel, mert: 9 6 4 -5 -5 -2 Decimális index különbsége 2n, 4 1 2 és még sem szomszédosak.
- A bináris súly különbsége legyen 1 0111 (7) 0011 (5)
0100 (4) 0010 (2)
1001 (9) 0101 (5)
0110 (6) 0101 (5)
17
Ez jó
Itt a bináris súly megegyezik
(hány 0 és 1-es van benne)
Ez sem elégséges feltétel: 9 (1001) 12 (1100) -7 (0111) -11 (1011) 2 1
Ezek sem szomszédosak
- A nagyobb bináris indexűnek kell lennie a nagyobb bináris súlyúnak. Az a, b, c szükséges és elégséges feltétele a szomszédosság megállapításának. Péda: 4
F= ∑ (0,1,3,7,11,12,14,15)
D
I. 0 1 3 12 7 11 14 15
0000 0001 0011 1100 0111 1011 1110 1111
(0 bináris súly) (1 bináris súly) (2 bináris súly)
1 bináris súly szerinti csoportosítás
0
0
1 A
12
0
0 3
2
1 5
0
0 7
6
1
13
0 8
1
15
14
1 9
B
0
10
11
C
II. 0,1 1,3 3,7 3,11 12,14 7, 15 11, 15 14, 15
1 1
4
(3 bináris súly) (4 bináris súly)
1 0
(1) (2) (4) (8) (2) (8) (4) (1)
(8) 0111 (7) 1111 (15) 24
Ez az összes létező szomszédos kettes összevonást jelenti.
(2) 0001 (1) 0011 (3) 21
III. 3, 7, 11, 15 (4, 8)
18
IV. Primimplikáns tábla
* * *
0,1 1,3 12,14 14,15 3,7,11,15
(1) (2) (2) (1) (4,8)
0 *
1 * *
3
7
11 12 14 15
* * *
*
* *
*
* *
Ahol az oszlopban csak egy csillag van, az nem elhagyható. 0 = 0000 1 = 0001
(0,1) =
12 = 1100 14 = 1110
(12,14) =
3 = 0011 7 = 0111 11 = 1011 15 = 1111
(3,7,11,15) =
Ezek a tagok kiesnek Ez a fajta minimalizálás is nagyon jól algoritmizálható. (Másképpen Quine-McCluskey minimalizálásnak hívják)
Több kimenetű hálózatok realizálása a) memória áramkörrel
19
b) PLA-val (Programable Logical Array)
Ez programozható A PLA továbbfejlesztése a PAL (Programable Array Logic), ennek továbbfejlesztése pedig a GAL (Gate Array Logic) Ezekkel az áramkörökkel programozható hardver hozható létre, ami nagyon gyors.
Egyszerűsített, optimalizált függvénynél előfordulhat, hogy nem megfelelően működik. Mi lehet az oka? Példa: B
1
F(A,B,C)=AB+ AC +(BC) A
1
0
1
4
5
3
1
2
1 7
16
C
BC
20
A (BC) a hazárdmentesítés miatt kell.
A gond a , azaz a hálózatban jelkésleltetés van (A két kapu miatt). A jelkésleltetés a vezetékhossz, kapuk, stb. miatt jön létre. A jelkésleltetést befolyásolják a környezeti behatások is, amiből következik, hogy időben változik. (A jelkésleltetés annál kisebb minél integráltabb a hálózat: kisebb felület, kisebb vezetékhossz) Ez a jelkésleltetés vezet, ahhoz, hogy a jól egyszerűsített fv.-ünk realizálás után mégis rosszul működhet. Tekintsünk egy hibás működést az előző ábra segítségével: F1(ABC) = 111 F2(ABC) = 101 (A jelkésleltetés miatt, még mindig ’0’ lesz az AC értéke, mikor az AB már „1” lesz) Láthatjuk, hogy ugyanaz az áramkör két különböző megoldást adott ugyanolyan bemeneti értékekre, ez pedig hibás működést feltételez.
111 helyett emiatt lesz 101 Def.: (Hazárd) Az olyan jelenségeket, amikor jó tervezés ellenére rossz működést kapunk hazárdoknak nevezzük. Statikus hazárd:
F(x)ÆF(x) (helyes működés) F(x)ÆF(x)*ÆF(x) (statikus hazárdnak nevezzük) Ez a fajta hazárd úgy mentesíthető jelen példánknál, hogy (BC)-t is bevonjuk a függvényünkbe. Mert a mentesítésnél, két azonos értékű szomszédos mintermet kell vennünk. Példa: (Dinamikus hazárdra) 21
D
1
1 0
1 1
1 4
2
3
1 5
1 A
F(A,B,C,D)=BD+ A BC +ACD+ BCD + [ ACD + ABC + A BD ]
0 7
6
15
14
1
12
13
8
9
1
B
(A []-ben lévő tagok a hazárdmentes működés miatt kellenek)
1
10
11
C
ABCDE = 01110 Æ ’1’ 11110 Æ ’0’
’1’-ből ’0’ lesz
Dinamikus hazárd: Többszintű hálózatokban jön létre, ahol a statikus hazárdok nem lettek kiküszöbölve. A statikus hazárdok kiküszöbölésével mentesíthető.
Az ilyen hálózatok szinkronizálással is mentesíthetők (SYNC)
22
Példa: (Funkcionális hazárdra) B
1
1 0
A
1
0 1
3
0 4
0 5
2
0 7
C
F(A,B,C) = BC + A B
0 6
100 (4) 001 (1)
ez nem szomszédos változás
Két úton realizálható a függvény:
a) 4 0 1 100 Æ 000 Æ 001 = 1Æ1Æ1 b) 4 5 1 100 Æ 101 Æ 001 = 1Æ0Æ1 !!!
(Funkcionális hazárd)
A funkcionális hazárd mentesítése: a) mesterséges késleltetések
Nem igazán jó megoldás, mert lassítja a hálózatot, és nem is mindig működik. b) A nem szomszédos bemeneti realizációkat nem engedjük meg. (Ez sem tökéletes) A megoldás erre a hazárdra, hogy szinkronizálókkal elnyeletem a hazárd jelenséget. Tökéletes megoldás, de lassítja a működést.
23
Dekompozíció (Bonyolult hálózatok hazárd mentesítése) Q1, 2, ..., n Q1, Q2 }felbontott hálózat Q1∪Q2 = Q Q1∩Q2 = ∅ F(Q)=f[f1(Q1), Q2]
F(A,B,C,D)= A BCD + ABCD + ABCD + ABCD = A C( BD + BD) + AC( BD + BD)
BD + BD = BD + BD
legyen f1(B,D)= BD + BD F(A,B,C,D)= A C ⋅ f1 ( B, D) + AC ⋅ f1 (B, D) =f(f1(B,D), A, C)
24
4
F= ∑ (4,5,6,7,8,13,14,15) F(A,B,C,D)= ABCD + ABCD + ABCD + ABCD + A BCD + ABCD + ABCD +ABCD F(A,B,C,D)=f(f1(A,D), B, C) F(A,B,C,D)= BC ⋅ p(A,D)+ BC ⋅ r(A,D)+ BC ⋅ s(A,D)+ BC ⋅ t(A,D) F(A,B,C,D)= BC ⋅ ( A D )+ BC ⋅ (0)+ BC ⋅ ( A B + AD + A D + AD )+ BC ⋅ ( A D + AD +AD) nincs BC ⋅
1
Diszjunktív dekompozíció
25
Többszörös diszjunktív dekompozíció
Sorrendi (szekvenciális) logikai hálózat: Előző bementi kombinációktól és azok sorrendjétől függ Kombinációs logikai hálózat: A bemeneti kombinációk pillanatnyi értékétől függ.
Mealy-modell fz(x, y)ÆZ fy(x, y)ÆY
Moore-modell f’z(y)ÆZ fy(x, y)ÆY
Aszinkron sorrendi hálózat: - Az instabil állapotok miatt a szükséges szekunder váltózók száma általában nagyobb, mint szinkron esetben, többek között ezért logikai tervezésük bonyolultabb. - A bemeneti változók gyakoriságát, vagyis a működés sebességét csak az építőelemek működési sebessége és a jelterjedési késleltetések korlátozzák. - Logikai tervezésük után nem kell szinkronizációs feltételeket biztosítani, megépíthetőek visszacsatolt kombinációs hálózattal is.
x változik Æ y instabil állapotok következnek x y y
Æ y instabil állapot Æ y instabil állapot Æ y instabil állapot 26
x stabil állapot Normál aszinkron sorrendi hálózatnak nevezzük a hálózatot, ha két stabil állapot között maximum 1 instabil állapot fordul elő. Ütemezett aszinkron SH:
Ha megengedjük, hogy minden órajel változáshoz új x kombináció juthasson a bemenetre, akkor sorrendi hálózatról (SH) beszélünk. Az ütemezett SH: - lassabb mint, az aszinkron SH, de vannak olyan helyzetek amikor az instabil állapotok aszinkron SH-val nem, míg ütemezett aszinkron SH-val megvalósíthatók. - Csak szigorú be- és kimeneti szinkronizációs feltételekkel működik. - Kevesebb szekunderváltozóval működtethető. Szinkronizációs feltételek: - A visszacsatoló ágak: o órajel vezérelhetők legyenek o definiált működésű tároló elemeket tartalmazzanak - A be- és kimeneti változások szinkronizálva legyenek az órajellel.
Mealy-modell szerinti működés: Kombinációs Hálózat flip-flop (tároló elem)
Moore-modell szerinti működés:
27
Szinkron esetben nincsenek értelmezve stabil vagy instabil állapotok az órajel miatt: - Kevesebb szekunder változó, mint aszinkron esetben - A logikai tervezés menete egyszerűbb - Az órajel határozza meg a sebességet, ezért általában lassabbak, mint az ütemezés nélküli aszinkron hálózatok. - Pontosabban működik, mint az aszinkron. - A bemeneti változókra és a kimeneti kombináció értelmezésére szinkronizációs feltételeknek kell teljesülniük. - A tervezésük után, megvalósításuk során biztosítani kell a szinkronizációs feltételeket.
Sorrendi Hálózatoknál állapottáblát használunk igazságtábla helyett. Példa egy állapottáblára:
x y y1 y2 y3 y4
X1
X2
X3
X4
Y1Z1 Y2Z4 Y4Z2 Y4Z4 Y1Z4 Y2Z3 Y2Z2 Y3Z1 Y4Z3 Y3Z1 Y3Z3 Y1Z2 Y4Z2 Y2Z2 Y3Z3 Y2Z3
Példa: (Állapottábla Maely-modell szerinti működésére magyarázat)
28
t Példa: (Állapottábla Moore-modell szerinti működésére magyarázat)
t Példa: (Aszinkron működés vizsgálata)
x y
X1
y1
Y1Z1
y2 y3 y4
X2
X3
X4 Y4Z4
Y2Z4
Y4Z2
Y1Z4
Y2Z3
Y2Z2
Y3Z1
Y4Z3
Y3Z1
Y3Z3
Y1Z2
Y4Z2
Y2Z2
stabil állapot
Y3Z3
Y2Z3 A hálózat X4 hatására oszcillál (össze-vissza rohangál)
Stabil állapot után megy tovább és veszi a következő Xn-t (n=1, 2, 3, 4 jelen esetben). Ha yn = Yn, akkor stabil az állapot (n=1, 2, 3, 4 jelen esetben). Aszinkron működés esetén a sorrend:
29
X1 Z1
X2 Z4, Z3
X3 Z2
X1 X3 Z , Z1 Z2, Z3
X4
4
X3
oszcillál
stabil állapot
Szinkron működés esetén a sorrend:
X1 Z1
X2 Z4 Z3
X3 Z2 Z2 .
.
x y y1 y2 y3
y4
X1 Z4 Z1
X3 Z2
X4 Z3
X1
X2
Y1Z1
Y2Z4
Y4Z2
Y1Z4
Y2Z3
Y2Z2
Y3Z1
Y4Z3
Y3Z1
Y3Z3
Y1Z2
Y4Z2
Y2Z2
Y3Z3
Y2Z3
X3
X3 Z2
X4 Y4Z4
Itt minden működés stabil Az állapottáblából állapot gráf rajzolható
Az állapot gráf is megmutatja, hogy szinkron, vagy aszinkron a hálózat.
30
Minden átvezető nyílra felírt bemeneti kombináció előbb vagy utóbb olyan körhöz vezet, amelyhez tartozó visszakanyarodó nyílon, szerepel ugyanaz a bemeneti kombináció. Ilyen esetben biztos, hogy a hálózatban nincs oszcilláció, és ekkor aszinkron módon is értelmezhető. Ha von olyan eset, hogy oszcillál a hálózat, az nem lehet aszinkron.
Elemi sorrendi hálózatok (flip-flop) (Emlékező „elemként” használjuk őket) z = y ezekben a hálózatokban f’z(y) = y, mindegyik Moore-modell szerint működik A legtöbb ilyen hálózatnak 2 bemenete és 1 (+ negált kimenet) kimenete van. Van órajel bemenet (szinkron működés), 1 db szekunderváltozó van. S-R flip-flop (Set-Reset = Beírás-Törlés) Å kimenet Å általában van negált kimenet kivezetés
nem változik törlés SR 00 y 0 0 1
01
1
0 0
írás 11
10
-
1
S
0
0 0
1 stabil állapot
y
1
1
0 4
1 3
5
2
1 7
6
R
f(SRy)=S+ R y
31
Alapvetően aszinkron módon működik. A valóságban az R-S flip-flopot nem így szokták realizálni, ahogy mi tettük, hanem így:
-
R-S0 flip-flop (NAND kapukkal)
R-S1 flip-flop (NOR kapukkal)
J -K flip-flop (S-R)
Ez a flip-flop annyiban különbözik az előzőtől, hogy itt az ’11’kombinációt is megengedjük.
nem változik törlés JK y 0
00
0 1
01
0 0
írás 11
10
1
1
0
0 0
0
1
S
1
y
stabil állapot f(J, K, y)=( J K ) + J y + Ky
1
1 1
0 4
1 3
5
2
1 7
6
R
csak a hazárd miatt kell Ezt a flip-flopot csak szinkron módon lehet megvalósítani T flip-flop
32
⇔
stabil állapot f(T,y)= T y + Ty =T⊕y
Ez a flip-flop is csak szinkron módon realizálható (Date - Gate) (adat - kapu)
D-G flip-flop
Ha Ha
G=1 Î y=D G=0 Î y=Y
DG 00 y 0 0 1
1
01
11
10
1
0 0
0
1
1
stabil állapot (Mivel minden oszlopban található egy stabil állapot aszinkron módon is megvalósítható) D
0
0 0
y
1
1 1
0 4
0 3
1 5
1 7
G
2
6
33
f(D, G, y)= Gy +DG+(Dy) A D-G flip-flop ismertebb neve Latch. D-flip-flop (D tároló)
D
0
1
0
0
1
1
0
y
1 stabil állapot
megtartja az értékét Ez a flip-flop is megvalósítható aszinkron módon, csak nincs értelem, mert úgy egy egyszerű vezeték lesz, és nem látja el a tárolási feladatot.
Szinkron módon így realizálható
f(D, y)=D A realizáció a valóságban sokszor azokból a flip-flopokból és egyéb alkatrészekből történik, amelyek kéznél vannak, olcsóbbak, stb. Nem feltétlenül azt a flip-flopot használjuk, amivel a legegyszerűbb a ralizáció.
Készítsünk D flip-flopot T flip-flopból:
34
D flip-flop D
T flip-flop
0
1
0
0
1
1
0
1
y
T
0
1
0
0
1
1
1
0
Y
f(D, y)= D y + Dy = D⊕y
antivalencia kapu
Készítsünk J-K flip-flopot T flip-flopból:
JK y 0
00
01
0
0
1
1
0
11
10
1
1
0
1
stabil állapot J
JK y 0 y
1
00
01
0
0
0
1
11
10
1
1
1
0
f(JK, y)= J y +Ky+(JK)
K
Sorrendi hálózatok tervezése
35
x1+ x2 Z c+0+0=0 c+1+0=1+c c+0+1=1+c c + 1 + 1 = 0 + carray
(carray = átvitel)
A tervezésnél mindig fel kell mérni, hogy hány belső állapotra van szükségünk. (Ez bonyolult rendszereknél nehéz) állapotok a b c d
előző átvitel 0 0 1 1
kimenet (Z) 0 1 0 1
Előzetes állapot táblát veszünk fel. (Ez még tartalmaz olyan állapotokat, ami felesleges, amiből következik, hogy ha több állapotunk van, mint amennyi kéne az nem baj, ha viszont kevesebb az már gond.) y
x1, x2
10
00
01
11
a
(Y, Z) a 0
b1
c0
b
a0
b1
c0
c
b1
c0
d1
c0
d
b1
c0
d1
c0
b1 b1
A kimenetek értéke szerint nem kell megkülönböztetni a két állapotot. (a lesz) A kimenetek értéke szerint nem kell megkülönböztetni ezt a két állapotot sem. (b lesz)
Elkészítjük az összevont állapottáblát Az „a-b”-t és a „c-d”-t összevonjuk y
x1, x2
00
01
11
10
a
a0
a1
b0
a1
b
a1
b0
b1
b0
Felvetődik a kérdés, hogy ’a’-t illetve ’b’-t vegyük ’0’-nak. Ezt önkényesen döntjük el. (Bonyolult rendszereknél nem mindegy melyik állapot 0, mert változhat a bonyolultsága) Következik a kódolt állapottábla
36
y
x1, x2
00
01
11
10
0
(Y Z) 00
01
10
01
1
01
10
11
10
a=0 b=1 x1
0 1
y
1
0
1
0
1
0
x2 Z= x 1 x 2 y + x 1 x 2 y + x 1 x 2 y + x 1 x 2 y R-S flip-floppal való realizálás:
y
x1, x2
00
01
11
10
0
(R S) 0-
0-
10
0-
1
01
-0
-0
-0
közömbös állapot A fenti táblázatot az S-R flip-flop vezérlési táblájának nevezzük.
x1 37
y
0
0
1
0
-
-
0 f(S) = x1x2
-
x2
R-S
x1
y
-
-
0
-
1
0
0
0
f(R)= x 1 x 2
x2
Az előző példa T flip-floppal való realizálása
T flip-flop vezérlési táblája: x1 y
y
x1x2
00
01
11
10
0
0
0
1
0
1
1
0
0
0
x2
f(T)= x 1 x 2 y + x 1 x 2 y Láthatjuk, hogy az előbbi példánk ezzel a flip-floppal bonyolultabb lett, még, ha a T-flip-flop egyszerűbb is, mint az R-S flip-flop. Az előzetes táblánk miatt látható, hogy a példánk a Mealy-modell szerinti tervezés (A bemenettől függőt a kimeneti- és a szekunderváltozók értéke) 38
Az előző feladat megoldása Moore-modellel
y
x1, x2
00
01
11
10
a
a0
b0
c0
b0
b
a1
b1
c1
b1
c
b0
c0
d0
c0
d
b1
c1
d1
c1
Moore-modellnél: - a kimenetek egy állapotnál ugyanazok - nincs lehetőség állapot összevonásra Kódolt állapottábla: x1 x2 a 0 0 b 0 1 c 1 0 d 1 1 A fenti állapotoknak az értékeket mi adjuk meg önkényesen. x1
y
x1, x2
00
01
y1 y2 Z 00 0
010
01
001
011
010
0
10
0 0
y1 y2 00
10
11
100
1
010
100
110
1
011 100
y1
0
011
101
111 101 ezt a két sort megcseréljük a másik táblában
2
1 7
1
13
15
0 8
11
1 5
1
12
0 3
1 4
101
0 1
0 9
10
6
1
y2
14
0 11
x2
A Moore-modell x1, x2-től nem függ, ki fog esni Z=y2
39
J-K flip-floppal való realizálása az előbbi feladatnak x1, x2
00
y1y2
01
10
10
a
J1 K1 0 -
J2 K2 0 -
0-
1-
1-
0-
0-
1-
b
0-
-1
0-
-0
1-
-1
0-
-0
c
-1
-0
-0
-1
-0
-0
d0
-1
d
-1
1-
1-
0-
-0
-0
-0
-1
Szinkron SH tervezésének lépései 1) Előzetes állapottábla felvétele: Ehhez szisztematikus módszer nem létezik, a szöveges feladat megfelelő értelmezését feltételezve intuitív jellegű. A feleslegesen megkülönböztetett állapotok a tervezés további lépéseiben összevonhatók, tehát nem jelentenek különösebb nehézségét. 2) Az (egyszerűsített) összevont állapottábla elkészítése: Ha az állapottábla teljesen specifikált, akkor erre a tervezési lépésre szisztematikus módszerek ismeretesek. Ha az állapottábla nem teljesen specifikált, akkor ugyanezek a módszerek használhatók, de a segítségükkel kapott eredményből csak intuitív lépések útján kaphatjuk meg a legegyszerűbb összevont állapottáblát. 3) Az állapotkódolás megválasztása: A hálózat egyszerűsége szempontjából kedvező kódolás megválasztására léteznek módszerek, de egyikről sem bizonyítható az optimalitás. 4) Az alkalmazandó flip-flopok megválasztása: Erre a tervezési lépésre sem létezik szisztematikus eljárás, a flip-flopok típusát többnyire a rendelkezésre álló építőelemkészlet alapján határozzuk meg. 5) A vezérlési tábla létrehozása: Ez teljesen szisztematikus. 6) A vezérlő kombinációs hálózat és a kimenetet előállító kombinációs hálózat realizációja: (A vezérlési táblához a D-G flip-flopnál próbálgatásos vizsgálat szükséges)
Példa: (Számoló tervezése, amely 0-tól 5-ig számol)
40
Szinkron SH-val valósítjuk meg. D flip-flopot választunk.
QA QB QC DA DB DC 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 . . . . . . . . . . . . . . . . . . A feladat egyszerűsége miatt most elhagyjuk az állapottáblát. DA B
0
0 0
A
1
1 1
0 4
0 3
-
5
2
7
6
C
DA=BC+ AC
Aszinkron SH tervezése
41
Aszinkron SH tervezésének lépései: - Az előzetes állapottábla felírásakor az aszinkron működési módot kell szem előtt tartanunk. Kizárólag szomszédos bemeneti kombinációváltozásokat tételezünk fel, és minden sorban csak egy stabil állapotot írunk. - Az összevont állapottábla létrehozásának módszerei ugyanazok lehetnek, mint a szinkron hálózatok esetén. - Az alkalmazandó flip-flop típus megválasztására érvényesek a szinkron hálózatok esetében tett megállapítások. Az aszinkron hálózatok ezen felül visszacsatolt kombinációs hálózattal is realizálhatók. - Az állapotkódolás kialakításakor nem a legegyszerűbb hálózat kialakítása, hanem a kritikus versenyhelyzet kiküszöbölése a cél. Erre szisztematikus eljárások léteznek. - A vezérlési tábla felírása és az elvi logikai rajz létrehozása ugyanúgy végezhető, mint a szinkron hálózatok esetén. - Lényeges hazárd szempontjából ellenőrizni kell az aszinkron hálózatot, és meg kell határoznunk, hogy melyek azok a szekunder változók, amelyek visszahatását késleltetni kell.
Kikötés:
Nem szomszédos állapotváltozások ne jöhessenek léter. Csak egyetlen stabil állapotot jelölünk ki.
Példa: (D flip-flop tervezése aszinkron módon) DC– y
x1 x2
00
01
11
10
a
YZ a0
b0
–
c0
b
a0
h0
d0
–
c
a0
–
e-
c0
d
–
b0
d0
c0
e
–
g1
e1
f1
f
h1
–
e1
f1
g
h1
g1
e1
–
h
h1
b-
–
f1
a b c d e f g h
D
C
Z
0 0 1 1 1 1 0 0
0 1 0 1 1 0 1 0
0 0 0 0 1 1 1 1
ez itt átmeneti állapot (’1’ vagy ’0’) ez itt szomszédos állapot változás
Átmeneti állapotnál mindegy hogy ’1’-et vagy ’0’-át választunk, mert nekünk csak a stabil állapotok számítanak. 0 1 0 0 stabil inst A
a, b, d
1 1 stabil A:00
42
c e, f, g h
B C D x1, x2
B:01 C:10 D:11
y1 y2 y1 y2 00
00
01
11
10
y1 y2 Z 00 0
00 0
00 0
01 0
01
00 0
–
10 -
01 0
10
11 1
10 1
10 1
10 1
11
11 1
00 -
–
10 1
stabil állapot
közömbös állapot
Ha az egyik szekunder változó gyorsabb, mint a másik kritikus helyzet alakulhat ki. Ezt a hazárdot kritikus versenyhelyzetnek nevezzük. Ebben a példában:
ha y1 gyorsabb Æ kritikus helyzet ha y2 gyorsabb Æ kritikus helyzet lehet
Új kódolással eltüntethető a versenyhelyzet, mert így a szekunderváltozók szomszédosak, nem úgy, mint az előbb. DC
y1 y2 y1 y2 00
00
01
11
10
y1 y2 Z 00 0
00 0
00 0
01 0
01
00 0
–
11 -
01 0
11
10 1
11 1
11 1
11 1
10
10 1
00 -
–
11 1
Y1= y1 y 2 + y 2 x 2 + x 2 y1 Y2= x 1 x 2 + x 1 y 2 + x 2 y 2 Z=y1 A feladat a Moore-modell szerint működik.
43
Z = 1 lesz pedig azt várnánk, hogy 1 Æ0 lesz. A bemeneti változók nem megfelelő késleltetése miatt alakul ki ez a helyzet (lényeges hazárd). Plusz késleltetések beiktatásával lehet kiküszöbölni. Előzetes állapottábla felvétel: - Szigorúan csak szomszédos állapot változásokat engedünk csak meg - Soronként 1 stabil állapot lehet - Összevont tábla létrehozása (közömbös állapotokat nem vesszük figyelembe) - Flip-floppal realizálása (azt választunk, amit akarunk, „vagy amink van”) - Kritikus versenyhelyzet kiküszöbölése. - Lényeges hazárd vizsgálata (bementi változók vizsgálata)
TSH (Teljesen Specifikált Hálózat) Def: TSH 2 állapota akkor megkülönböztethető, ha létezik olyan bemeneti kombináció sorozat amelyre a hálózat két különböző állapotából kiindulva különböző kimeneti kombinációs állapot sorozatot szolgáltat. Ha nem létezik ilyen akkor nem megkülönböztethető. Előzetes állapottábla x x2 x1 y a
aZ1
dZ2
b
bZ1
bZ2
c
dZ2
bZ2
d
dZ2
bZ2
Lehetnek-e összevonási lehetőségek? b és c állapot összehasonlítsa: A kimenetek állapota miatt b és c nem lehet azonos (b≠c) c és d teljesen egyértelmű: c≡d
44
Def.: Két állapot ekvivalens, ha bármely bemeneti kombinációt u.a. kimeneti kombináció hozza létre, és a két állapot bármelyikéből kiindulva u.a. állapotba jutunk. x y
x1
x2
a
bZ1
dZ2
b
1
fZ
2
eZ
c
aZ1
bZ2
d
dZ2
cZ1
e
eZ2
cZ1
f
aZ2
eZ2
Első ránézésre nincsenek ekvivalens állapotok a≡c? (nem mert b≠d) Igen, ha b≡a és d≡b a≡b? Igen, ha b≡f és d≡e d≡b? nem mert Z1≠Z2 Ebből viszont következik: a≠c
b≡f? ha a≡f d≡e? d≡e a≡f? ha a≡b és d≡e Ha nincs kizáró feltétel, akkor egymással azonosak, tehát a példánkban szereplő állapotok közül ezek ekvivalensek: b≡a b≡f a≡f d≡e Bonyolultabb esetekben Paul-Unger lépcsős táblázatát használjuk. n (n állapot esetén ( ) kombináció van) 2
b c
bf de ab db
af be
d e f
ab de a
af
be
b
c
d
e 45
Ha mind a két állapot azonos: Feltételesen azonos: feltételek leírása A feladat a nem ekvivalensek megkeresése !!! (Ami marad azt ekvivalensnek fogadjuk el)
Def.: (Ekvivalencia osztály) Páronként ekvivalens állapotok, halmaza az ekvivalencia osztály Def.: (Maximális ekvivalencia osztály) Ha már nem bővíthető az ekvivalencia osztály , akkor maximális. Az előbbi példánk alapján a maximális ekvivalencia osztály a következő: (a b c d e f) (b c d e f ) (a b f ) (c d e f ) (a b f) (b f) (d e f ) (a b f) (c) (e f) (a b f) (c) (d e) (e) (f) (a b f) (c) (d e)
„a” nem jó, mert nem ekvivalens mindegyikkel „b” nem jó, mert nem ekvivalens mindegyikkel „c” nem jó, mert nem ekvivalens mindegyikkel „d” nem jó, mert nem ekvivalens mindegyikkel „e” nem jó, mert nem ekvivalens mindegyikkel
A maximális ekvivalencia osztály: (a b f) (c) (d e) A: (a b f) B: (d e) C: (c)
Összevont állapottábla: x
x1
x2
A
AZ1
BZ2
B
BZ2
CZ1
C
AZ1
AZ2
y
Ekvivalenciák tulajdonságai: - a≡a (reflexivitás) (szimmetria) - a≡b Æ b≡a (tranzitivitás) - a≡b és b≡c Æ a≡c Maximális ekvivalencia osztály tulajdonságai: - „Az előzetes állapot tábla” állapotaiból alkotott halmaz részhalmazai. - „Az előzetes állapot tábla” minden egyes állapota, megtalálható a maximális ekvivalencia osztályban. - Mindegyik állapotot csak egyszer találhatjuk meg a maximális ekvivalencia osztályban.
46
NTSH (Nem Teljesen Specifikált Hálózat) NTSH esetén az állapot összevonás célja, hogy olyan állapottáblához jussunk, aminek a lehető legkevesebb sora van és az előzetes állapottábla specifikált bejegyzéseivel megegyező működést olvashatunk ki belőle. - Az összes lehetséges állapotot valahogy rögzítjük, majd a legegyszerűbbet megkeressük (ez egy halom összevont állapottáblát jelent) A legkedvezőbb állapottábla előállításának lépései: 1. Valamennyi kompatibilis és inkompatibilis állapot pár megkeresése lépcsős tábla felhasználásával Def: (inkompatibilitás, kompatibilitás) NTSH két állapota akkor, és csak akkor megkülönböztethető, ha létezik legalább egy olyan mindkét állapotra specifikációs bemeneti kombinációsorozat, amelyre a két állapotból kiindulva szolgáltatott két kimeneti kombinációsorozat legalább egy bemeneti kombináció esetén különbözik egymástól. Az NTSH nem megkülönböztethető (NMK) állapotait kompatibilis (összeegyeztethető) állapotnak nevezik. 2. A lépcsős tábla alapján (ugyanúgy, mint a TSH-nál) a maximális kompatibilitási osztályok megkeresése. Def.:(kompatibilitási osztály és a maximális kompatibilitási osztály) Egy sorrendi hálózat páronként kompatibilis állapotainak halmazát kompatibilitási osztálynak nevezzük. Egy kompatibilitási osztály maximális, ha nem bővíthető egyetlen újabb állapottal sem. 3. A kompatibilitási osztályok legkedvezőbb zárt halmazainak megkeresése. 4. A legkedvezőbb zárt halmaz osztályainak egy-egy állapotot megfeleltetve az összevont állapottábla kitöltése. Kompatibilitás – mint egy NTSH állapotai közötti reláció- tulajdonságai: - Minden állapot kompatibilis önmagával: a~a (reflexivitás) - A kompatibilitás kölcsönös két állapot között: ha a~b, akkor b~a. (szimmetria) (nem tranzitív) - a~b és b~c, ebből nem következik a~c
A kompatibilitás csak a tranzitivitás szempontjából különbözik az ekvivalenciától, ezt a különbséget a közömbös bejegyzések különböző rögzítési lehetőségei okozzák NTSH esetében. Maximális kompatibilitási osztályok tulajdonságai: - „Az előzetes állapot tábla” állapotaiból alkotott halmaz részhalmazai. - „Az előzetes állapot tábla” minden egyes állapota, megtalálható a maximális kompatibilitási osztályban. - Lehetnek közös állapotaik, azaz egy állapot több osztályban is szerepelhet. A maximális kompatibilitási osztályok tehát nem diszjunkt részhalmazai az összes állapot halmazának
47
Intuitív tervezés A klasszikus tervezés minden esetben tökéletes segítség hálózatok tervezésére, de vannak olyan esetek, amikor a hálózat tervezéséhez a klasszikus tervezés lépései elhagyhatók, mert: - nagyon egyszerű a hálózat - gyakorlott tervezőnek az adott hálózat megtervezéséhez nincs szüksége rá. Az olyan tervezést, amikor a klasszikus tervezés lépései, helyett megérzés, gyakorlat alapján tervezünk, intuitív tervezésnek hívjuk. Példa: (Intuitív tervezésre) Tervezzünk egyszerű ébresztőóra áramkört.
Function NG: Ébresztés be-, kikapcsolása A Háózatot D flip-flop-okkal valósítjuk meg
48
Karnough táblák és peremezésük B
A
0
1
3
2
4
5
7
6
C
D
A
0
1
3
2
4
5
7
6
12
13
15
14
8
9
10
11
B
C
49