Logické obvody 3 - Normální formy a Karnaughovy mapy

Minule jsme pravdivostní tabulkou kompletně definovali co daný kombinační obvod bude dělat tak, jak bylo v zadání požadováno. Nyní už ho stačí „pouze“ realizovat.

Realizace pomocí logických členů, co je potřeba

1. zjednodušení (minimalizace) logické funkce

1. buď: výpis výstupní funkce v algebraickém tvaru + minimalizace pomocí pravidel Booleovy algebry
2. nebo: zápis výstupní funkce přímo do Karnaughovy mapy, která slouží k minimalizaci výstupní funkce grafickou metodou

2. nakreslení schéma logického obvodu

1. buď: přímo pomocí základních logických členů – AND, OR, NOT nebo i dalších (EXOR, …)
2. nebo: pouze pomocí členů NAND nebo pouze pomocí členů NOR, napřed je ale potřeba převést logickou funkci podle De Morganových zákonů

Výpis výstupní logické funkce v algebraickém tvaru

1. Jako úplná normální disjunktní forma (ÚNDF)

• tu získáme z pravdivostní tabulky tak, že vytvoříme součiny vstupních proměnných v řádcích, kde má výstupní funkce hodnotu f = 1 tzv. mintermy. Všechny tyto mintermy pak sečteme. Každá proměnná v součinu je zapsána tak, že pokud nabývá hodnoty log 0, pak ji píšeme s negací, pokud log 1, pak píšeme bez negace.

2. jako úplná normální konjunktní forma (ÚNKF)

• která se skládá ze součtů vstupních proměnných v řádcích, kde má výstupní funkce hodnotu f = 0 tzv. maxtermů, a všechny tyto maxtermy pak vynásobíme. Každá proměnná v součtu je zapsána tak, že pokud nabývá hodnoty log 0, pak ji píšeme bez negace, pokud log 1, pak píšeme s negací.

Příklad vytvoření ÚNDF a ÚNKF z pravdivostní tabulky:

Samozřejmě teď bychom mohli nakreslit schéma obvodu, ale vždy je dobré výstupní funkci zkusit zjednodušit. Již dříve jsme využívali pravidla Booleovy algebry, takže jen zopakujeme

Minimalizace ÚNDF podle Booleovy algebry

Jak je vidět, dospěli jsme ke stejnému výsledku jako je ÚNKF. Oba tvary jsou samozřejmě tatáž funkce, takže to zas tak velké překvapení není. Zajímavé je na tom jen to, že ÚNKF byl tvar, který byl již minimální (byl to jediný řádek, resp. jediná nulová hodnota funkce, takže proto). Princip minimalizace spočívá v určitém vhodném slučování jedniček pro ÚNDF a nul pro ÚNKF, nicméně minimalizace se dělá především pro ÚNDF a pro ÚNKF se volí pouze, pokud je výrazněji méně nul než jedniček, což byl náš případ.

Schéma výstupní funkce ze základních logických členů

Tak a teď schéma ze základních logických členů. Příklad je příliš jednoduchý, takže je hned zřejmé, že postačuje použít jeden OR.

Raději uvedu ještě jeden příklad, který je zadán pravdivostní tabulkou a opět máme vypsat ÚNDF a ÚNKF:

Minimalizace ÚNDF podle Booleovy algebry

Tak tady už byla úprava mnohem zajímavější, ale realizovatelná.

Pokud bychom chtěli zjednodušovat ÚNKF, bylo by nutné závorky mezi sebou roznásobit a .... to už samo o sobě je hrozná představa, takže to dělat nebudeme

Schéma výstupní funkce ze základních logických členů

Ještě schéma naší funkce. Ze základních členů budeme potřebovat 3x dvouvstupový AND a 2x dvouvstupový OR.

Schéma vypadá dobře a není ani moc složité, ale každý typ logického členu je obsažen v jiném integrovaném obvodu. Konkrétně dvouvstupový AND v TTL 7408, kde jsou čtyři tyto členy a dvouvstupový OR zase v TTL 7432, kde jsou také čtyři členy. Což tedy znamená celkem dva integrované obvody.

Realizace výstupní funkce pouze pomocí členů NAND

V rámci úspor (místa i financí) se minimalizace týká i omezení typů použitých členů. Takže se pak provádí převedení již minimalizované funkce na jen NAND nebo jen NOR a to pomocí De Morganových pravidel.

Já to trošku zjednoduším. Chceme-li použít jen NAND, musíme se zbavit všech součtů ve funkci a naopak chceme-li funkci realizovat jen NOR, pak je potřeba odstranit součiny. To provedeme "dvojitou negací" nad součtem (nebo součinem). Otázka je proč dvojitá negace, když podle De Morgana stačí jen jedna negace pro změnu součtu na součin (nebo součinu na součet). Tak pokud bychom naší funkci znegovali pouze jednou, tak vlastně realizujeme funkci právě opačnou než jsme chtěli. Takže ta druhá negace je tam proto, abychom nezměnili původní funkci. Pro vlastní demorganování ji nepoužijeme, jen tam zůstane.

Schéma výstupní funkce jen z logických členů NAND

Když na to teď koukám, tak jsme si moc nepomohli, protože zase budeme potřebovat dva integrované obvody (TTL 7400 a TTL 7411). Sice je dvou i třívstupové NAND stejný typ, ale bohužel se rozlišuje i počet vstupů, ale doufám, že princip je jasný .

Minimalizace výstupní funkce pomocí Karnaugovy mapy

Cílem minimalizace je nalézt co nejjednodušší vyjádření zadané logické funkce. Tato metoda je vhodná maximálně pro 4 až 5 proměnných, ale je rychlá a výsledná funkce je vždy v minimálním tvaru.

Hledáme:

MNDF, minimální normální disjunktní formu - logický součet minimálního počtu minimálních součinů (mintermů)

nebo

MNKF, minimální normální konjunktní formu - logický součin minimálního počtu minimálních součtů (maxtermů)

Postup minimalizace pomocí Karnaughovy mapy

1. Zapíšeme výstupní funkci do mapy.
2. Vytvoříme smyčky. Pro hledání MNDF vytváříme smyčky přibližně ve tvaru čtverce nebo obdélníku, které obsahují, co největší počet „sousedních jedničkových stavů“. Počet těchto stavů musí být vždy mocninou čísla 2 (tj. 1, 2, 4, 8, 16, … atd.). Sousední jedničkové stavy jsou „jedničky“, které spolu sousedí hranou, a to i přes okraje mapy. Smyčky se mohou navzájem překrývat, neděláme však smyčky nadbytečné. Všechny jedničky musí být popsány buď v rámci některé smyčky, nebo samostatně.
3. Jednotlivé smyčky se popisují mintermy, složenými pouze z těch proměnných, které se během celé smyčky nemění (proměnná a bude v mintermu obsažena, pokud pro všechny „1“ ve smyčce nabývá stejné hodnoty, např. a = 1). Termy dvou sousedních polí se od sebe liší jen ve stavu jedné proměnné a o tuto proměnnou lze funkci, při sloučení těchto polí do smyčky, zjednodušit. Čím více sousedních „1“ je ve smyčce, tím méně proměnných bude v příslušném mintermu.
4. Výsledná MNDF je součtem takto vytvořených minimálních mintermů.

Pro MNKF platí totéž, s tím, že smyčky vytváříme kolem „sousedních nulových stavů“ a smyčky se popisují pomocí maxtermů. Výsledná MNKF je pak součinem těchto minimálních maxtermů.

Př.: Napište pravdivostní tabulku, Karnaughovu mapu, MNDF a MNKF funkce, zadané pomocí stavových indexů.

Př.: Vytvořte pravdivostní tabulku, Karnaughovu mapu, MNDF a MNKF logického členu OR. Uvažujte dvě vstupní proměnné.

Minimalizace neúplně zadaných funkcí

Při minimalizaci neúplně zadaných funkcí postupujeme shodně jako při minimalizaci funkcí úplně zadaných s tím, že neurčené stavy x zahrnujeme buď do smyček s „jedničkami“ nebo do smyček s „nulami“ nebo je nemusíme zahrnout do žádné smyčky. Vždy hledíme na výhodnost jejich polohy pro tu kterou minimalizaci. Stručně řečeno, pokud je výhodné zahrnout neurčitý stav a získat tak větší smyčku (tedy menší počet proměnných) učiníme tak, jinak ne.

Př.: pravdivostní tabulka a Karnaughova mapa funkce neúplně zadané

Pro MNDF není výhodné neurčený stav zahrnovat, vedlo by to pouze k vytvoření další smyčky a tím dalších proměnných.

Pro MNKF je však smyčka s x výhodnější neboť je popsána jen proměnnou b, oproti popisu samotné „0“, jež by vedlo k popisu (a + b).

Př.: Minimalizujte neúplně zadanou funkci pomocí Karnaughovy mapy a zapište ve tvaru MNDF. Funkce je zadána stavovým indexem.

Tak myslím, že v tomto díle toho už bylo poměrně dost , tak abychom se úplně mentálně nevyčerpali je nutné říci, že většina lepších simulačních programů umí provést minimalizaci ze zadané pravdivostní tabulky nebo funkce v algebraickém tvaru jedním kliknutím.