Digitális technika 1 - HT partíciók

HT partíciók - egy példán keresztül

Feladatkitűzés:

Adott egy szinkron sorrendi hálózat állapottáblája

y \ X1X2	00	01	11	10
A	C 1	C 1	A 1	D 1
B	B 1	A 1	A 1	C 1
C	C 0	A 0	A 0	B 0
D	D 0	A 0	A 0	C 0

Kódolja az állapotokat önfüggő szekunder változócsoportok alapján.

1. Adja meg a triviális HT partíciókat és legalább kettő, triviálistól eltérő HT partíciót.
2. Kódolja a hálózatot a minimális számú szekunder változót igénylő triviálistól eltérő partícióval, és jelölje meg, hogy melyik változó lesz önfüggő!
3. Töltse ki a kódolt állapottáblát

Megoldás:

1. Feladat:

• A triviális HT partíciók: 2 ilyen van
  • Minden állapot külön blokkban: azaz esetünkben Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{1} (A)(B)(C)(D) }
  • Minden állapot egy blokkban: esetünkben Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{2} (ABCD) }
    
• Keressünk 2 triviálistól eltérőt:
  1. Vizsgáljuk meg például a következő partíciót: (AB)(CD)
     • AB egy csoportba tartozásának feltétele: BC, AC, DC egy csoportba tartozása. Mivel ezek nem tartoznak azonos csoportba (hiszen a mostani 2 csoportunk AB és CD), így (AB)(CD) nem HT partíció.
  2. Vizsgáljuk meg ezután a következő partíciót: (AC)(BD)
     • AC egy csoportba tartozásának feltétele BD egy csoportba tartozása, BD pedig egy csoportba tartozik. Tehát Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{3} (AC)(BD) } HT partíció.
  3. Az algoritmus tehát az, hogy minden lehetséges csoportosításra megvizsgáljuk, hogy az HT partíció-e. Most azonban csak 2-t kell keresnünk. Jelen esetben például jó lesz a következő csoportosítás: (BCD)(A)
     • BCD egy csoportba tartozik, ha a benne lévő állapotok közül bármelyik 2 egy csoportba tartozik. Vegyük sorba:
       • BC egy csoportba tartozik -> OK
       • BD is egy csoportba tartozik -> OK
       • CD egy csoportba tartozik, ha BC egy csoportba tartozik, ami igaz -> OK
     • Láthatjuk, hogy BC, BD, CD mind a BCD csoportba vannak, tehát Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{4} (BCD)(A) } is HT partíció.

2. Feladat:

• Mivel 4 állapotunk van, ezért minimum 2 szekunder változóra van szükségünk Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (2^2 = 4) } .
• Azt, hogy egy adott HT partíció szerinti kódoláshoz hány szekunder változóra van szükség, a következő összefüggés határozza meg: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p = \lceil\log_{2}B\rceil + \lceil\log_{2}A\rceil } , ahol Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \lceil \rceil} jelölés az értéknek a legközelebbi egész számra történő felkerekítésére utal. A az egy blokkban előforduló állapotok legnagyobb száma, B pedig a blokkok száma
• Nézzük meg p értékét a nem triviális partícióinkra:

HT	B	A	p
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{3}}	2	2	2
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{4}}	2	3	3

Tehát Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prod_{3}} minimális.

• Kódolás:

	y1	y2
A	0	0
B	0	1
C	1	0
D	1	1

Így Y1 lesz önfüggő, azaz Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle Y1={f}(X1,X2,y1)} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle Y2={f}(X1,X2,y1,y2)} . Ami jól látszik, ha felrajzoljuk Y1 és Y2 Karnaugh tábláját (ügyelve a peremezésre) és abból felírjuk a logikai függvényüket.

3. feladat:

• Ezek után a kódolt állapottábla kitöltése gyerekjáték, csak be kell másolni az állapotok betűi helyére a nekik megfelelő kódokat:

y \ X1X2	00	01	11	10
00	01 1	01 1	00 1	11 1
10	10 1	00 1	00 1	01 1
01	01 0	00 0	00 0	10 0
11	11 0	00 0	00 0	01 0