Szikszayl: vissza link

2013-12-09T22:07:03Z

vissza link

← Régebbi változat		A lap 2013. december 10., 00:07-kori változata
1. sor:		1. sor:
			{{Vissza\|Digitális technika I.}}

	=Bevezetés a teljesen specifikált sorrendi hálózatok állapotminimalizálásába=		=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)===		===(kis segédmagyarázat a jegyzet mellé a teljesség igénye nélkül)===

Szikszayl: kategória hozzáadva

2013-12-09T22:06:05Z

kategória hozzáadva

← Régebbi változat		A lap 2013. december 10., 00:06-kori változata
89. sor:		89. sor:

	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.		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.

			[[Category:Infoalap]]

Szikszayl: Szikszayl átnevezte a(z) SorrendiOsszevonas lapot a következő névre: Digitális technika - Sorrendi összevonás

2013-12-09T22:04:04Z

Szikszayl átnevezte a(z) SorrendiOsszevonas lapot a következő névre: Digitális technika - Sorrendi összevonás

← Régebbi változat	A lap 2013. december 10., 00:04-kori változata
(Nincs különbség)

Wachag: Új oldal, tartalma: „=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…”

2013-12-09T21:20:00Z

Új oldal, tartalma: „=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…”

Új lap

=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:
<nowiki>
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
</nowiki>
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:
<nowiki>
-+--+
B| |
-+--+--+
C| | |
-+--+--+--+
D| | | |
-+--+--+--+--+
E| | | | |
-+--+--+--+--+--+
F| | | | | |
-+--+--+--+--+--+--+
G| | | | | | |
-+--+--+--+--+--+--+--+
H| | | | | | | |
-+--+--+--+--+--+--+--+
|A |B |C |D |E |F |G |
</nowiki>
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.

Digitális technika - Sorrendi összevonás - Laptörténet

Szikszayl: vissza link

Szikszayl: kategória hozzáadva

Szikszayl: Szikszayl átnevezte a(z) SorrendiOsszevonas lapot a következő névre: Digitális technika - Sorrendi összevonás

Wachag: Új oldal, tartalma: „=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…”