Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

temata:08-minimalizace_logickych_vyrazu:main [2011/02/12 18:22]
jasho [Hazardy]
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 88: Řá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á
- 
-  * 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:09_hazardy.png|}} {{: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)
  
 {{:temata:08-minimalizace_logickych_vyrazu:10_eliminacia_01.png|}} {{:temata:08-minimalizace_logickych_vyrazu:10_eliminacia_01.png|}}
Řádek 100: Řá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 119: Řá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>
temata/08-minimalizace_logickych_vyrazu/main.1297531339.txt.gz · Poslední úprava: 2011/02/12 18:22 autor: jasho
Recent changes RSS feed Debian Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki