Digitális technika - Sorrendi összevonás

← Vissza az előző oldalra – Digitális technika I.

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:

1. Ahhoz, hogy két állapot összevonható legyen, muszáj, hogy adott bemenetre ugyanazt a kimenetet adják.
2. 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:

1. Biztos, hogy nem vonható össze: mert eltérőek a kimenetek adott bemenetre. Ezt pl. X-szel jelöljük.
2. Biztos, hogy összevonható két állapot: ugyanarra a bemenetre ugyanaz a kimenet és ugyanaz a következő állapot. Ezt pipával jelöljük
3. 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.