Orbis pictus21. století

Tato prezentace byla vytvořenav rámci projektu

Minimalizace funkcíMinimalizace funkcí

OB21-OP-EL-CT-JANC-M-2-009 OB21-OP-EL-CT-JANC-M-2-009

Minimalizace logické funkce Minimalizace logické funkce pomocí map pomocí map

Způsob minimalizace logické funkce pomocí mapového Způsob minimalizace logické funkce pomocí mapového zobrazení je velmi často používán a vede vždy k hledanému zobrazení je velmi často používán a vede vždy k hledanému minimálnímu logickému výrazu. minimálnímu logickému výrazu.

Karnaughova mapa Karnaughova mapa se dá použít pro minimalizaci logické se dá použít pro minimalizaci logické funkce do 4 až 6 (vyjímečně do 8) vstupních proměnných.funkce do 4 až 6 (vyjímečně do 8) vstupních proměnných.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Do jednotlivých políček Karnaughovy mapy vložíme hodnoty Do jednotlivých políček Karnaughovy mapy vložíme hodnoty logické funkce z pravdivostní tabulky. logické funkce z pravdivostní tabulky.

Každému mapovému zobrazení libovolné určité nebo neurčité Každému mapovému zobrazení libovolné určité nebo neurčité funkce odpovídá vždy alespoň jeden algebraický výraz, který funkce odpovídá vždy alespoň jeden algebraický výraz, který tvoří minimální součtovou (disjunktivní) nebo součinovou tvoří minimální součtovou (disjunktivní) nebo součinovou (konjunktivní) formu dané funkce. (konjunktivní) formu dané funkce.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Minimální logickou funkci stanovíme tak, že v Karnaughově Minimální logickou funkci stanovíme tak, že v Karnaughově mapě vytváříme tzv. mapě vytváříme tzv. podmapypodmapy

Podmapou rozumíme sjednocení 2Podmapou rozumíme sjednocení 2kk sousedních stavů, ve sousedních stavů, ve kterých nabývá logická funkce hodnoty 1 ( pro NDF) nebo 0 kterých nabývá logická funkce hodnoty 1 ( pro NDF) nebo 0 ( pro NKF) pro k = 0,1,2, …, n-1. ( pro NKF) pro k = 0,1,2, …, n-1.

Každou podmapou vyloučíme Každou podmapou vyloučíme kk proměnných z dvou, čtyř až  proměnných z dvou, čtyř až 22n-1n-1 základních součinů (pro NDF) nebo součtů (pro NKF). základních součinů (pro NDF) nebo součtů (pro NKF).

Snažíme se vytvářet co největší podmapy, abychom vyloučili Snažíme se vytvářet co největší podmapy, abychom vyloučili co největší počet proměnných. Využíváme k tomu také co největší počet proměnných. Využíváme k tomu také neurčité stavy. neurčité stavy.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Výběr podmap provádíme podle následujících pravidel:Výběr podmap provádíme podle následujících pravidel:

Vybranými podmapami musí být pokryty všechny jednotkové Vybranými podmapami musí být pokryty všechny jednotkové (pro NDF) nebo nulové (pro NKF) stavy logické funkce.(pro NDF) nebo nulové (pro NKF) stavy logické funkce.

Do podmapy spojujeme stejné stavy, které spolu sousedí Do podmapy spojujeme stejné stavy, které spolu sousedí hranou, a to i přes okraje mapy. Rohy mapy jsou též hranou, a to i přes okraje mapy. Rohy mapy jsou též sousedními stavy. Členy dvou sousedních polí se od sebe liší sousedními stavy. Členy dvou sousedních polí se od sebe liší jednou proměnnou a tuto proměnnou můžeme vyloučit.jednou proměnnou a tuto proměnnou můžeme vyloučit.

Podmapu pravidelného tvaru (čtverec, obdélník) vytváříme co Podmapu pravidelného tvaru (čtverec, obdélník) vytváříme co největší, aby se ze skupiny stavů vyloučila jedna, dvě, největší, aby se ze skupiny stavů vyloučila jedna, dvě, eventuálně tři proměnné.eventuálně tři proměnné.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Podmapy se mohou prolínat.Podmapy se mohou prolínat.

Nevytváříme zbytečné podmapy, tzn. že nespojujeme ty stavy, Nevytváříme zbytečné podmapy, tzn. že nespojujeme ty stavy, které už byly předtím pokryty jinou podmapou.které už byly předtím pokryty jinou podmapou.

Čím větší bude podmapa, tím jednodušší bude výsledný výraz.Čím větší bude podmapa, tím jednodušší bude výsledný výraz.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Na následujícím obr.1 jsou ukázány dvě logické funkce Na následujícím obr.1 jsou ukázány dvě logické funkce zapsané pomocí mapového zobrazení: zapsané pomocí mapového zobrazení:

obr.1 a) funkce určitá, obr.1 a) funkce určitá, obr.1 b) funkce neurčitá, tj. funkce, která není pro některé obr.1 b) funkce neurčitá, tj. funkce, která není pro některé

kombinace vstupních definována. kombinace vstupních definována.

Může proto nabývat libovolné hodnoty 0 nebo 1 – zapisujeme Může proto nabývat libovolné hodnoty 0 nebo 1 – zapisujeme ji symbolem X. ji symbolem X.

Pro minimalizaci funkce se této skutečnosti využívá tak, že Pro minimalizaci funkce se této skutečnosti využívá tak, že vytváříme podmapy s využitím neurčitých stavů, které vytváříme podmapy s využitím neurčitých stavů, které považujeme buď za jednotkové, nebo za nulové, jak je to považujeme buď za jednotkové, nebo za nulové, jak je to z hlediska minimalizace nejvhodnější. z hlediska minimalizace nejvhodnější.

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Příklad:Příklad: Minimalizujte logické funkce dvou vstupních proměnných, Minimalizujte logické funkce dvou vstupních proměnných,

zadané mapami na obr. 1 a) a b) zadané mapami na obr. 1 a) a b)

Obr. 1 Mapové zobrazení logických funkcía) f1 – určité, b) f2 – neurčité

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Určitá logická funkce na obr. 1 a) je tvořena v úplné součtové Určitá logická funkce na obr. 1 a) je tvořena v úplné součtové formě (UNDF) třemi jedničkovými stavyformě (UNDF) třemi jedničkovými stavy

Při minimalizaci pokryjeme tyto tři stavy dvěma podmapami Při minimalizaci pokryjeme tyto tři stavy dvěma podmapami označenými P1 a P2. Každá podmapa obsahuje 2 políčka. označenými P1 a P2. Každá podmapa obsahuje 2 políčka. Podmapa P1 zahrnuje dva mintermy a . Pomocí Podmapa P1 zahrnuje dva mintermy a . Pomocí podmapy P1 provádíme minimalizaci vyloučením proměnné podmapy P1 provádíme minimalizaci vyloučením proměnné b:b:

babababaf ),(1

abbababaP )(1

ba ba

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Podmapa označená v obrázku P2 umožní vyloučit proměnnou Podmapa označená v obrázku P2 umožní vyloučit proměnnou a:a:

Výsledná minimalizovaná funkce je dána součtem Výsledná minimalizovaná funkce je dána součtem minimálního počtu podmap, které pokrývají všechny minimálního počtu podmap, které pokrývají všechny jedničkové stavy jedničkové stavy

baabbabaP )(2

baPPbaf 21),(1

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Na obr. 1 b) je znázorněna neurčitá logická funkce f2, která Na obr. 1 b) je znázorněna neurčitá logická funkce f2, která obsahuje jeden jednotkový stav a dva neurčité stavy na obsahuje jeden jednotkový stav a dva neurčité stavy na pozicích a . Výsledná logická funkce musí pokrývat pozicích a . Výsledná logická funkce musí pokrývat jednotkový logický stav a k minimalizaci použijeme buď jednotkový logický stav a k minimalizaci použijeme buď neurčený stav , pak funkce neurčený stav , pak funkce

v případě že k minimalizaci využijeme neurčený stav , bude v případě že k minimalizaci využijeme neurčený stav , bude výstupní funkcevýstupní funkce

Obě funkce jsou v tomto případě stejně složité.Obě funkce jsou v tomto případě stejně složité.

af 2

bf 2

ba ba ba

ba ba

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Příklad:Příklad: Minimalizujte logické funkce tří vstupních proměnných f1 a Minimalizujte logické funkce tří vstupních proměnných f1 a

f2, zadané pravdivostní tabulkou znázorněnou na obr. 2. f2, zadané pravdivostní tabulkou znázorněnou na obr. 2.

Obr. 2 Pravdivostní tabulka určité funkce f1 a neurčité funkce f2

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Minimalizace logické funkce Minimalizace logické funkce pomocí mappomocí map

Děkuji za pozornostDěkuji za pozornost

Ing. Ladislav JančaříkIng. Ladislav Jančařík

LiteraturaLiteratura

Antošová M, Davídek V.: Číslicová technika, KOPP České Antošová M, Davídek V.: Číslicová technika, KOPP České Budějovice 2008Budějovice 2008

Bernard J., Hugon J., Le Covec R.: Od logických obvodů k Bernard J., Hugon J., Le Covec R.: Od logických obvodů k mikroprocesorům I, SNTL Praha 1982mikroprocesorům I, SNTL Praha 1982