08 - Minimalizácia logických výrazov

Kritériá minimalizácie:

Zoradíme si vstupné premenné a keď sme schopný priradiť im váhy tak môžme priradiť tomu vstupu nejakú binárnu hodnotu (aby sa nám s tým lepšie pracovalo).
X - neurčený stav - je nám jedno, čo bude dávať výstup (môžme si dosadiť 0 alebo 1)

Vrcholy musia byť booleovsky susedné.
Kde je pruh, tam má premenná hodnotu logická 1.
Svobodova mapa a Karnaughova mapa - sú ekvivalentné (vo svete je známejšia Karnaughova).

Grafický zápis v ktorom sa ľahko hľadá.
Ak sú v susedných políčkach logické 1, našli sme booleovsky susedné kombinácie vstupných premenných a teda môžme tieto políčka združiť. - Eliminujeme premennú, ktorá sa mení. Môžme združovať aj štvorice, osmice…
Pre viac ako 4 premenné je to nepraktický zápis.

Term - usporiadaná skupina premenných a operátorov. (termom hovoríme implikanty)
ÚNDF = suma súčinov, kompletný výpis, zápis pre jednotky
ZNDF = skrátená normálna disjunktná forma - niečo eliminujeme (môže existovať viacero)
MNDF = minimálna normálna disjunktná forma - eliminujeme všetko čo sa dá (môže existovať viacero)
Skrátený zápis - ∨(0,2,4,6) = 1(0,2,4,6) = Σm(0,2,4,6)

Termom hovoríme implicenty
ÚNKF = súčin súm, zapisujeme výraz pre nuly (kedy je funkcia nulová), zápis s negovanými premennými
ZNKF = skrátená normálna konjunktná forma - niečo eliminujeme (môže existovať viacero)
MNKF = minimálna normálna konjunktná forma - eliminujeme všetko čo sa dá (môže existovať viacero)
Skrátený zápis - ∧(1,3,5,7) = &(1,3,5,7) = πM(1,3,5,7)

P - počet log. členov
S - počet spojov medzi členmi vrátane vstupov a výstupov (spočítať počet vstupov všetkých log. členov a pripočítať počet výstupov obvodu)
T - oneskorenie obvodu (súčet oneskorenia jednotlivých log. členov, počítame najdlhšiu cestu v obvode (ale v praxi musíme ešte uvažovať oneskorenie na vodičoch))

Log. vetva - cesta signálov od vstupov k výstupom, pre jednotlivé vstupy môže mať rôznu dĺžku
prechodný dej, chvíľu sa obvod chová inak ako by sme čakali a až potom sa ustáli
Dôvody:
- nerovnaka dlžka log. vetiev
- oneskorenie vodičov
- nerovnaké oneskorenie log. členov
Druhy:
- statické:
  - na výstupe krátky pulz
  - 1 hazard - pulz z log. 1 do log. 0 a naspäť
  - 0 hazard - pulz z log. 0 do log. 1 a naspäť
  - dvojica vstupných kombinácií, ktoré sa líšia v jednej premennej a zároveň produkujú rovnaké hodnoty výstupu log. funkcie
  - príklad - prepli sme x (1 ⇒ 0)

dynamické:
- na výstupe viac ako jeden pulz
- v prípade viacerých ciest s rôznymi dĺžkami zo vstupu na výstup
- eliminácia môže byť náročná

Eliminácia statických hazardov - z Karnaughovej mapy - treba pokryť všetky dvojice vrcholov, ktoré ležia vedľa seba (za cenu zložitejšieho obvodu)

pre každý výstup samostatná rovnica - obvody budú mať rovnaké vstupy, ale každý bude mať vlastný výstup
alebo - budeme sa to snažiť navrhovať ako 1 obvod - využijeme časti iných obvodov (ktoré sa nám hodia)
podstata je, že nemusí byť najlepšie riešenie také, že zoberiem minimálne formy pre každý výstup a spravým podľa toho obvody, ale môžu horšie formy spraviť lepšie výsledné riešenie keď majú veľa spoločných prvkov

princíp - prechádza všetky dvojice booleovsky susedných vrcholov a zisťuje, či sú v log. 1, ak sú, tak ich zlúči
terminológia:
- úplny implikant - vyskytujú sa v ňom všetky premenné
- čiastočne skrátený implikant - má niektoré booleovsky susedné premenné eliminované
- skrátený implikant - má všetky booleovsky susedné premenné eliminované
- množina minimálnych implikantov - všetky minimálne implikanty
- minimálne riešenie funkcie - jedna alebo viac podmnožín z množiny minimálnych implikantov
- nesporný implikant - skrátený implikant, ktorý bude vždy súčasťou výsledného riešenia
- voliteľný implikant - skrátený implikant, ktorý môže ale nemusí byť súčasťou výsledného riešenia (ak sa dá namiesto neho použiť iný skrátený implikant)
postup:
- krok 1 - zoradíme riadky tabuľky jednotlivých implikantov v poradí podľa ich váhy, čím dostaneme skupiny booleovsky susedných implikantov (poprekladáme riadky tabuľky tak, aby boli tie vedľa seba booleovsky susedné)
- krok 2 - eliminujeme jednotky

príklad:
- najrpv to spíšeme po skupinách - máme skupinu kde je len 1 jednotka, kde sú 2 jednotky…
- potom hľadáme booleovsky susedné riadky medzi skupinami (medzi skupinou 1 a skupinou 2, atď)
- zase hľadáme booleovskú susednosť, až kým sa dá niečo zlučovať

grafické znázornenie pokrytia vrcholov funkcie
hľadáme najmenší počet skrátených implikantov pokrývajúcich všetky vrcholy
môže existovať viacero riešení
postup:
- najprv musíme zahrnúť všetky nesporné implikanty
- ďalej hľadáme najmenšie pokrytie ostatných vrcholov

výsledok: F(w, x, y, z) = PI1 + PI3 + PI4 + PI7 = (1-0-) + (-010) + (01-0) + (11-1)