OBSAH WEBU
ČTĚTE!
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
temata:08-minimalizace_logickych_vyrazu:main [2011/02/12 18:20] jasho [ÚNDF (úplna normálna disjunktná forma)] |
temata:08-minimalizace_logickych_vyrazu:main [2011/05/06 17:30] (aktuální) vagabund [08 - Minimalizácia logických výrazov] |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
- | ====== Minimalizácia logických výrazov ====== | + | ~~ODT~~ |
+ | ====== 08 - Minimalizácia logických výrazov ====== | ||
+ | |||
+ | * proces, který má za úkol snížit počet logických členů v obvodech | ||
===== Kritériá minimalizácie: ===== | ===== Kritériá minimalizácie: ===== | ||
* Plocha (počet hradiel) | * Plocha (počet hradiel) | ||
Řádek 30: | Řádek 33: | ||
===== N-rozmerná jednotková kocka ===== | ===== N-rozmerná jednotková kocka ===== | ||
* N-rozmerov = N premenných | * N-rozmerov = N premenných | ||
- | * boolovská susednosť - susedné vrcholy sa líšia len v hodnote jednej premennej | + | * booleovská susednosť - susedné vrcholy sa líšia len v hodnote jednej premennej |
* eliminácia premennej - y*z + y*z' = y | * eliminácia premennej - y*z + y*z' = y | ||
Řádek 62: | Řádek 65: | ||
* Skrátený zápis - ∧(1,3,5,7) = &(1,3,5,7) = πM(1,3,5,7) | * Skrátený zápis - ∧(1,3,5,7) = &(1,3,5,7) = πM(1,3,5,7) | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:07_unkf.png|}} | ||
===== Metriky používané v INC ===== | ===== Metriky používané v INC ===== | ||
* P - počet log. členov | * P - počet log. členov | ||
Řádek 67: | Řádek 71: | ||
* 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)) | * 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)) | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:08_metriky.png|}} | ||
===== Hazardy ===== | ===== Hazardy ===== | ||
* Log. vetva - cesta signálov od vstupov k výstupom, pre jednotlivé vstupy môže mať rôznu dĺžku | * Log. vetva - cesta signálov od vstupov k výstupom, pre jednotlivé vstupy môže mať rôznu dĺžku | ||
Řádek 86: | Řádek 91: | ||
* v prípade viacerých ciest s rôznymi dĺžkami zo vstupu na výstup | * 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 môže byť náročná | ||
+ | |||
+ | {{:temata:08-minimalizace_logickych_vyrazu:09_hazardy.png|}} | ||
* 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) | * 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) | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:10_eliminacia_01.png|}} | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:11_eliminacia_02.png|}} | ||
===== Minimalizácia obvodov s viacerými výstupmi ===== | ===== Minimalizácia obvodov s viacerými výstupmi ===== | ||
* pre každý výstup samostatná rovnica - obvody budú mať rovnaké vstupy, ale každý bude mať vlastný výstup | * pre každý výstup samostatná rovnica - obvody budú mať rovnaké vstupy, ale každý bude mať vlastný výstup | ||
Řádek 94: | Řádek 103: | ||
* 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 | * 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 | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:12_viac_vstupov.png|}} | ||
===== Quine-McCluskey ===== | ===== Quine-McCluskey ===== | ||
* 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 | * 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 | ||
Řádek 113: | Řádek 123: | ||
* zase hľadáme booleovskú susednosť, až kým sa dá niečo zlučovať | * zase hľadáme booleovskú susednosť, až kým sa dá niečo zlučovať | ||
+ | {{:temata:08-minimalizace_logickych_vyrazu:13_quine_mccluskey.png|}} | ||
+ | |||
+ | ===== Mriežka implikantov: ===== | ||
+ | * 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 | ||
+ | |||
+ | {{:temata:08-minimalizace_logickych_vyrazu:14_mriezka_implikantov.png|}} | ||
+ | * výsledok: F(w, x, y, z) = PI1 + PI3 + PI4 + PI7 = (1-0-) + (-010) + (01-0) + (11-1) | ||
+ | |||
+ | ===== Petrickova funkce: ===== | ||
+ | * algoritmus nájdenia minimálneho pokrytia funkcie | ||
+ | * postup: | ||
+ | * nájdeme všetky skrátené implikanty (pomocou Karnaughových máp, alebo Quine-McCluskey) | ||
+ | * nájdeme všetky nesporné implikanty (napr. pomocou mriežky implikantov) | ||
+ | * pre zostávajúce skrátené implikanty zapíšeme ZNKF výraz reprezentujúci všetky možné pokrytia - pre každý nepokrytý implikant zapíšeme sumu skrátených implikantov, ktoré ho pokrývajú | ||
+ | * roznásobením prepíšeme na disjunktnú formu, zjednodušíme pomocou booleovho teorému => každý term, ktorý vznikne predstavuje jedno možné pokrytie | ||
+ | * nájdeme pokrytie s najnižšou cenou (najnižším počtom premenných v impikante) | ||
+ | * umožňuje nájdenie optimálneho riešenia | ||
+ | |||
+ | {{:temata:08-minimalizace_logickych_vyrazu:15_petrickova_funkce_02.png|}} | ||
+ | |||
+ | |||
+ | ===== Zdroj ===== | ||
+ | <note> | ||
+ | Čerpal som zo slidov k INC: | ||
+ | https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INC-IT/lectures/inc4_minim.pdf | ||
+ | https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INC-IT/lectures/inc5_minim2.pdf | ||
+ | </note> | ||
===== Potvrzení ===== | ===== Potvrzení ===== | ||
<doodle single login|08> | <doodle single login|08> |