Digitális technika - Sorrendi összevonás
Bevezetés a teljesen specifikált sorrendi hálózatok állapotminimalizálásába
(kis segédmagyarázat a jegyzet mellé a teljesség igénye nélkül)
Miről is van szó? Amikor a specifikáció (esetünkben a feladatkiírás) alapján felveszed az előzetes állapottáblát, akkor nem foglalkozol azzal, hogy az egyes állapotok többször is szerepelnek, azaz hogy létezhet több olyan állapot, ahol tulajdonképpen teljesen ugyanazt csinálja a hálózatod. Ezeket az állapotokat ki kell szedni a hálózatból.
Miért?
Nyilvánvaló ok a költség: logikai kapukat, áramköröket spórolsz meg a kiszedett állapotokkal (feltéve, hogy így tervezel, de ez már másik kérdés). Egy eszköznél ez 10-20-100 forintok spórolását jelenti, de mondjuk 1000 eszköznél már 100000 forintot, még többnél meg még többet. Vannak más okok is: minél több az állapot, annál nehezebb a hálózat helyes működését matematikai úton bizonyítani.
Lényeg a lényeg: a fölösleges állapotokat el kell távolítani. De melyikeket kell eltávolítani? Mi fölösleges?
Képzeld el a következőt: legyártották a hálózatodat két példányban, ott vannak előtted. Az egyik - valamilyen okból - éppen "A" állapotban van, a másik meg "B"-ben. Te annyit csinálsz, hogy mindkét hálózatot egymás után ellátod ugyanazokkal a bemeneti értékekkel, és vizsgálod a kimenetet. Tegyük fel, hogy ezt a végtelenségig csinálod és minden lehetséges bemeneti sorrendben kipróbálod. Mi van, ha azt tapasztalod, hogy mindezek után a két hálózatod (mely közül az egyik "A" állapotból indult, a másik meg "B"-ből) teljesen ugyanazt a kimenetet adja?
Nyilvánvaló, hogy a működés szempontjából ezt a két állapotot teljesen fölösleges megkülönböztetni, összevonhatók egybe.
Tehát, két állapot összevonható, ha a az adott állapotokból indítva a rendszert tetszőleges bemeneti kombinációk sorozata ugyanazt a kimeneti kombináció sorozatot adja.
Ez a definíció szépen hangzik, de elég nehéz használni. Alapvetően nem tudod azt megtenni, hogy minden állapotpárra végignézed a végtelen sok bemeneti kombináció sorozatot és a hozzá tartozó kimenetet, tehát másképp kell nekilátni.
Azt állítottuk, hogy két állapot összevonható, ha a az adott állapotokból indítva a rendszert tetszőleges bemeneti kombinációk sorozata ugyanazt a kimeneti kombináció sorozatot adja. De ez akkor azt is jelenti, hogy - és itt a lényeg - két összevonható állapotra igaz az, hogy egy adott bemenethez tartozó következő állapotoknak is összevonhatóaknak kell lenniük: hiszen azokra is igaz az, hogy tetszőleges bemeneti kombináció sorozatra ugyanazt a kimeneti kombináció sorozatot adják.
Nézzünk mást is: mi van akkor, ha a két állapot közül egy adott bemenetre az egyik X-et (valamilyen kimenet) a másik meg Y-t (valamilyen másik kimenet) ad? Nyilvánvalóan egészen más a működésük, nem vonhatóak össze. Tehát ahhoz, hogy két állapot összevonható legyen, muszáj, hogy adott bemenetre ugyanazt a kimenetet adják.
Ebből a kettő elvárásból jön ki az összevonhatóság (avagy TSH esetén ekvivalencia) két feltétele:
- Ahhoz, hogy két állapot összevonható legyen, muszáj, hogy adott bemenetre ugyanazt a kimenetet adják.
- Egy adott bemenethez tartozó következő állapotoknak is összevonhatóaknak kell lenniük.
Nagyon jó, sokkal kézzelfoghatóbb lett a dolog. Mit kell tehát tenni: minden állapotpárra megnézni, hogy összevonhatóak-e. Ehhez mire van szükség: megnézni, hogy adott bemenetre ugyanazok-e a kimenetek (ha nem, akkor nyilvánvalóan nem lehetnek összevonhatóak), és aztán megnézni, hogy adott bemenethez tartozó következő állapotok összevonhatóak-e.
Nézzük meg egy példán:
X=0 X=1 A E0 D0 B G0 H0 C B0 F0 D D0 A1 E A0 H0 F F0 C1 G B0 F0 H B0 H1
Mikor vonható össze A és H? Látjuk, hogy sosem, hiszen X=1 bemenetre helyből másképp viselkednek, más a kimenet.
Mikor vonható össze A és B? A kimenetek stimmelnek, tehát a második feltétel szerint akkor, ha E és G, illetve D és H összevonhatóak. Innentől kezdve két irányban kell nézni tovább a dolgokat: mikor vonható össze E és G? Mikor vonható össze D és H?
Nézzük például a D és H összevonhatóságát! A kimenetek itt is stimmelnek, és azt látjuk, hogy D és H összevonható, ha B és D összevonható, illetve ha A és H összevonható. De baj van: az előbb láttuk, hogy A és H nem összevonható.
Ebből dominó-szerűen dőlnek el a dolgok: A és H nem összevonható, tehát D és H sem, tehát A és B sem.
Tulajdonképpen az állapotminimalizálás arról szól, hogy ezt viszi végig az ember minden egyes állapotpárra. Ebbe nagyon könnyű belezavarodni, tehát érdemes egy olyan ábrázolásmódot kitalálni, amelyen a "vak is látja", hogy melyik állapotpár összevonhatósága mitől függ.
Erre jó a lépcsős tábla:
-+--+ B| | -+--+--+ C| | | -+--+--+--+ D| | | | -+--+--+--+--+ E| | | | | -+--+--+--+--+--+ F| | | | | | -+--+--+--+--+--+--+ G| | | | | | | -+--+--+--+--+--+--+--+ H| | | | | | | | -+--+--+--+--+--+--+--+ |A |B |C |D |E |F |G |
Ha megnézed ezt a táblát, azt látod, hogy minden állapotpárhoz tartozik egy (és csak egy) táblázatcella. A cellába az kerül, hogy összevonható-e a két állapot. Kezdetben ez három dolog lehet:
- Biztos, hogy nem vonható össze: mert eltérőek a kimenetek adott bemenetre. Ezt pl. X-szel jelöljük.
- Biztos, hogy összevonható két állapot: ugyanarra a bemenetre ugyanaz a kimenet és ugyanaz a következő állapot. Ezt pipával jelöljük
- Feltételesen összevonható két állapot: a kimenetek ugyanazok adott bemenetre, de a következő állapotok nem. Ilyenkor a cellába azt írjuk, hogy mikor összevonható a két állapot (például az előző példa alapján az AB cellába EG és DH írandó.
Kitöltötted a táblát, minden cellába került valami. Most már látjuk, hogy melyek azok az állapotok, amelyek _biztosan_ nem vonhatóak össze a kimenet miatt (1.) típusú cellák). Meg kell néznünk az összes ilyen X-szel ellátott állapotpárt, hogy van-e olyan másik állapotpárunk, amelyhez tartozó cellában ez szerepel. Előző példa szerint: AH nem összevonható. Nézzük meg, ez melyik állapotok összevonhatóságát teszi lehetetlenné. Ezek az állapotok is (dominószerűen) összevonhatatlanok lesznek.
Tulajdonképpen ennyi a feladat: végignézed az összes összevonhatatlan állapotot, hogy ezek miatt mi lesz még összevonhatatlan. Ezek után megnézed azokat is, hogy miattuk mi lesz összevonhatatlan. Aztán azokat is végignézed. Előbb-utóbb eljutsz oda, hogy végignézted az összes összevonhatatlan állapotot, már nem módosítasz a lépcsős táblán. A maradék állapotpárok (ahol pipa van vagy nincs X) összevonhatóak.
Ezek után ezek közül kell kiválasztani az egyes legnagyobb csoportokat, ha lesz egy kis időm, megpróbálom ezt is leírni.
