„Digitális technika 1 - HT partíciók” változatai közötti eltérés

# '''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><br />

#*Keressünk 2 triviálistól eltérőt:

#*#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ó.

#*#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ó.

#*#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: