OBSAH WEBU
ČTĚTE!
Rozdíly
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:19] jasho [Logická mapa] |
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 53: | Řádek 56: | ||
| * Skrátený zápis - ∨(0,2,4,6) = 1(0,2,4,6) = Σm(0,2,4,6) | * Skrátený zápis - ∨(0,2,4,6) = 1(0,2,4,6) = Σm(0,2,4,6) | ||
| + | {{:temata:08-minimalizace_logickych_vyrazu:06_undf.png|}} | ||
| ===== ÚNKF (úplna normálna konjunktná forma) ===== | ===== ÚNKF (úplna normálna konjunktná forma) ===== | ||
| Řádek 61: | Řá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 66: | Řá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 85: | Řá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 93: | Řá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 112: | Řá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> | ||
