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 [math] \prod_{1} (A)(B)(C)(D) [/math]
     • Minden állapot egy blokkban: esetünkben [math] \prod_{2} (ABCD) [/math]
       
   • 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 [math] \prod_{3} (AC)(BD) [/math] 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 [math] \prod_{4} (BCD)(A) [/math] is HT partíció.

2. Mivel 4 állapotunk van, ezért minimum 2 szekunder változóra van szükségünk([math] 2^2 = 4 [/math]). 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: [math] p = \lceil\log_{2}B\rceil + \lceil\log_{2}A\rceil [/math], ahol [math]\lceil \rceil[/math] 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* |} |[math]\prod_{3}[/math]||2||2||2 |} |[math]\prod_{4}[/math]||2||3||3 |} Tehát [math]\prod_{3}[/math] minimális. kódolás: |* *||*y1*||*y2* |} |*A*||0||0 |} |*C*||0||1 |} |*B*||1||0 |} |*D*||1||1 |} Így Y1 lesz önfüggő, azaz [math]Y1={f}(X1,X2,y1)[/math] és [math]Y2={f}(X1,X2,y1,y2)[/math]. 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. 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. |*y1y2 \ 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 |}