VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH TECHNOLOGIÍ
Ústav mikroelektroniky
LABORATORNÍ CVIČENÍ Z PŘEDMĚTU Digitální integrované obvody
Minimalizace logické funkce
Michal Krajíček Martin Klíma
Obsah 1. 2.
Úvod .................................................................................................................... 3 Binární číselná soustava, logické funkce a operátory.......................................... 3 2.1. Binární číselná soustava .............................................................................. 3 2.2. Logické funkce ............................................................................................. 4 2.2.1. Zápis Pravdivostní tabulkou .................................................................. 5 2.2.2. Zápis funkce algebraickými výrazy normálními formami ....................... 5 2.3. Logické operátory......................................................................................... 6 2.3.1. Negace – NOT ...................................................................................... 6 2.3.2. Logický součet – OR (nebo).................................................................. 7 2.3.3. Negovaný logický součet (NOR) ........................................................... 7 2.3.4. Logický součin (AND)............................................................................ 8 2.3.5. Negovaný logický součin (NAND) ......................................................... 8 2.3.6. Nonekvivalence (XOR).......................................................................... 9 3. Realizace logické sítě.......................................................................................... 9 4. Minimalizace logické funkce .............................................................................. 10 4.1. Booleova algebra ....................................................................................... 10 4.2. De Morganovy zákony................................................................................ 11 4.3. Karnaughova mapa .................................................................................... 12 4.3.1. Sestavení Karnaughovy mapy ............................................................ 13 4.3.2. Zapsání funkce do Karnaughovy mapy............................................... 14 4.3.3. Vyhodnocení Karnaughovy mapy ....................................................... 15 5. Závěr ................................................................................................................. 16 6. Zdroje ................................................................................................................ 16 7. Zadání cvičení ................................................................................................... 17
2
1. Úvod S rozvojem elektroniky a jejímu stále častějšímu využívání pro plnění výpočetních úkolů se po čase elektronika rozdělila na analogovou elektroniku, která zpracovává spojité signály, a elektroniku digitální - číselnou. Jedním z důvodů byl fakt, že velká část matematických operací pracuje s konkrétními hodnotami, což je těžko realizovatelné pomocí prvků se spojitými charakteristikami. Protože nestačí možné stavy od sebe pouze separovat, ale je nutné i rozlišit je při vyhodnocení od sebe, nastal problém s definováním rozhodovacích úrovní signálu. Pro lidi přirozená dekadická číselné soustava se nejevila vhodná z důvodu nutnosti rozlišit relativně velké množství úrovní. Kvůli jasnému určení stavu se tedy elektronika vydala cestou, které skýtá nejmenší možný počet pro rozhodnutí, a to dva. Pro efektivní zpracovaní matematických operací, které má především vliv na rychlost zpracování informace, menší spotřebu materiálu i energie, začal být kladen důraz na snížení počtu operací na nutné minimum a jejich zjednodušení. Protože všechny zmíněné výhody, včetně času, lze vyčíslit penězi, je patrné, že minimalizace a zjednodušování operací vede ke značným úsporám.
2. Binární číselná a operátory
soustava,
logické
funkce
V souvislosti s digitální elektronikou je často užíván termín logický - logické hodnoty, logické funkce, logické operace aj. Logickou hodnotou, nebo také bool hodnotou, je hodnota reprezentována stavy pravda/nepravda (true/false), nebo také ano/ne, zapnuto/vypnuto nebo ‘1’/’0’. Veškeré matematické souvislosti pro tyto hodnoty zastřešuje Booleova algebra.
2.1. Binární číselná soustava Za nadskupinu logických hodnot může být považována binární, česky dvojková, číselné soustava, která je rovněž reprezentována dvěma stavy - 0 a 1. Jde o poziční číselnou soustavu mocnin se základem 2 a je nutné podotknout, že logické hodnoty korespondují pouze s jednomístnými binárními čísly - bity. Poziční soustava vychází ze zvyklostí zapisování čísla, tj. z leva doprava, přičemž nalevo jsou hodnoty s nejvyšší váhou a napravo s nejnižší, stejně, jako tomu je u desítkové soustavy. To je patrné z následující ukázky převodu binárního čísla na dekadické. Číslo 10110010101 rozepíšeme jakou součet součinů hodnot příslušných pozic s mocninou čísla 2. Nultou pozicí je hodnota s nejnižší váhou, směrem doleva se tato mocnina zvyšuje s krokem 1. 10110010101 → 1 ⋅ 210 + 0 ⋅ 2 9 + 1 ⋅ 2 8 + 1 ⋅ 2 7 + 0 ⋅ 2 6 + 0 ⋅ 2 5 + 1 ⋅ 2 4 + 0 ⋅ 2 3 + 1 ⋅ 2 2 + 0 ⋅ 21 + 1 ⋅ 2 0 = = 1024 + 0 + 256 + 128 + 0 + 0 + 16 + 0 + 4 + 0 + 1 = 1429 3
Převod dekadického čísla na binární má opačný postup. Je třeba určit kolik a jakých mocnin se základem 2 dává v součtu převáděné dekadické číslo. Standardní způsob převodu využívá celočíselné dělení dekadického čísla číslem 2. Podstatné jsou právě zbytky po celočíselném dělení, které nabývají hodnot 1, nebo 0. Ty se postupně zapisují, výsledek převodu tvoří tyto zbytky zapsané v opačném pořadí. Více napoví následující příklad - převod čísla 142910. 1429 ÷ 2 = 714 zb. 1 714 ÷ 2 = 357
zb. 0
357 ÷ 2 = 178
zb. 1
178 ÷ 2 = 89
zb. 0
89 ÷ 2 = 44
zb. 1
44 ÷ 2 = 22
zb. 0
22 ÷ 2 = 11
zb. 0
11 ÷ 2 = 5
zb. 1
5÷2 = 2
zb. 1
2÷2 =1
zb. 0
1÷ 2 = 0
zb. 1
⇒ 10110010101
Protože se tato práce zaměřuje především na zjednodušení bitových operací a funkcí, binárními čísly se dále zabývat nebudeme.
2.2. Logické funkce Logická funkce je funkce, která pro konečný počet vstupních parametrů vrací logické hodnoty. Jedná se o soubor logických operací, konkrétně operací s výroky, jejichž výsledkem je opět výrok, jež nabývá logických hodnot závisejících na pravdivosti výroků a druhu operace. Druh logické operace určuje operátor. V elektronice se logickými operátory rozumí prvky realizující operace s logickými funkcemi. Obecně se nazývají hradla. Pro praktickou realizaci jakékoliv funkce bylo vytvořeno šest základních operací a jim odpovídajících hradel. Více v kapitole 2.3 Logické operátory. Co se týče zápisu logické funkce, každou logickou funkci lze vyjádřit různými způsoby (grafickými nebo algebraickými). Je-li každému stavu x1, x2 …..xN nezávislých proměnných logické funkce f(x1 ,x2 …..xN) přiřazena funkční hodnota y, mluvíme o úplně určené funkci f. Chybí-li byť jedna funkční hodnota, jedná se o neúplně určenou funkci. Takovému stavu říkáme neurčitý stav.
4
2.2.1. Zápis Pravdivostní tabulkou Do pravdivostní tabulky, viz Tabulka 2-1, se zapisují hodnoty vstupních stavů a výstupního stavu (kombinační obvody – pouze jeden výstupní stav), resp. výstupních stavů (sekvenční obvody – může být více výstupních stavů). - stavový index, dekadické číslo, které nabývá hodnot 0 až 2n-1 - vstupní stavy - výstupní stav - logická jednička - logická nula - neurčitý stav
S X1 – X4 Y 1 0 !
2-1 Zápis logické funkce pravdivostní tabulkou
S 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2.2.2.
X1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
X2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
X3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
X4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 1 1 1 0 ! 0 1 1 0 ! 1 ! 0 1 ! 1
Zápis funkce algebraickými výrazy normálními formami
Úplná součtová normální forma 2 n −1
y=
∑y
S
⋅ KS
S =0
y = 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 0 ⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 + 1⋅ X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4
5
Úplná součinová normální forma 2n −1
y = ∏ ( yS + K S ) S =0
(
)(
)(
y = 1+ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ⋅ 1+ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ⋅ 1+ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4
(
)( )⋅ (1 + X )⋅ (1 + X )⋅ (1 + X
)( )⋅ (0 + X ⋅ X )⋅ (1 + X ⋅ X )⋅ (0 + X ⋅ X
)
)
⋅ 0 + X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ⋅ 1+ X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ⋅ 0 + X1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ⋅
(0 + X (0 + X (0 + X
1
⋅ X2 ⋅ X3 ⋅ X4
1
⋅ X2 ⋅ X3 ⋅ X4
1
⋅ X2 ⋅ X3 ⋅ X4
1
⋅ X2 ⋅ X3 ⋅ X4
1
⋅ X2 ⋅ X3 ⋅ X4
1
⋅ X2 ⋅ X3 ⋅ X4
1
2
1
2
1
2
) ⋅ X ⋅ X )⋅ ⋅ X ⋅ X )⋅ ⋅ X3 ⋅ X4 ⋅ 3
3
4
4
(1 + X 1 ⋅ X 2 ⋅ X 3 ⋅ X 4 ) yS KS
- funkční hodnota odpovídající stavovému indexu - základní logický součin
2.3. Logické operátory 2.3.1. Negace – NOT Výstupem funkce negace je hodnota opačná - negovaná - k hodnotě vstupní proměnné. Jestliže na vstupu X bude hodnota log. 1 na výstupu Y bude hodnota log. 0 (viz tabulka 2-2). 1-bitové hradlo pro realizaci funkce negace má jeden vstup a jeden výstup. Značky dle různých pro toto hradlo jsou na obr. 2-1 Matematický zápis negace: Y=X
. Tab. 2-2 Pravdivostní tabulka Negace
X 1 0
Y 0 1
Obr. 2-1 NOT: a) EU, b) US, c) ČSN, d) IEC [1]
6
2.3.2. Logický součet – OR (nebo) Logický, nebo také binární, součet sčítá dvě a více proměnných. Výstupem funkce bude log. 1, jestliže je alespoň na jednom z n vstupů logická 1. Tato funkce se také nazývá disjunkce (sjednocení). V praxi má uplatnění i jako hradlo pro kontrolu výskytu. Matematický zápis logického součtu: Y = A+ B Tab. 2-3 Pravdivostní tabulka logického součtu
A 0 0 1 1
B 0 1 0 1
Y 0 1 1 1
Obr. 2-2 Používané značení hradel OR: a) EU, b) US, c) ČSN, d) IEC [1]
2.3.3. Negovaný logický součet (NOR) Negovaný logický součet je spojením funkcí log. součtu a negace, tudíž na výstupu bude log. 1 pouze v případě, že na vstupu jsou samé log. 0. Matematický zápis negovaného logického součtu: Y = A+ B Tab. 2-4 Pravdivostní tabulka NOR
A 0 0 1 1
B 0 1 0 1
Y 1 0 0 0
Obr. 2-3 Používané značení hradel NOR: a) EU, b) US, c) ČSN, d) IEC [1]
7
2.3.4. Logický součin (AND) Logický součin je bitovou operací dvou a více proměnných. Její výstupní hodnota nabývá hodnoty log. 1 jen tehdy, jsou-li všechny vstupní hodnoty log. 1. Tato funkce se také nazývá konjunkce (průnik) a jedno z jeho praktických využití je kontrola shody. Matematický zápis logického součinu: Y = A⋅ B Tab. 2-5 Pravdivostní tabulka logického součinu
A 0 0 1 1
B 0 1 0 1
Y 0 0 0 1
Obr. 2-4 Používané značení hradel AND: a) EU, b) US, c) ČSN, d) IEC [1]
2.3.5. Negovaný logický součin (NAND) Obdobně jako pro log. funkci OR existuje funkce NOR, tak i log. funkce AND má negovaný protějšek NAND, což je zřetězením funkcí AND a NOT. Po provedení logického součinu se výstupní hodnota zneguje, tudíž na výstupu může být log. 0 jen tehdy, pokud na všech vstupech bude log. 1. Matematický zápis logického negovaného součinu: Y = A⋅ B Tab. 2-6 Pravdivostní tabulka negovaného logického součinu
A 0 0 1 1
B 0 1 0 1
Y 1 1 1 0
Obr. 2-5 Používané značení hradel NAND: a) EU, b) US, c) ČSN, d) IEC [1]
8
2.3.6. Nonekvivalence (XOR) Funkce bývá někdy označována jako exkluzivní logický součet. Její výstup nabývá hodnoty log. 1 tehdy, kdy jsou vstupní hodnoty rozdílné. Matematický zápis nonekvivalence:
Y = A⋅ B + A⋅ B = A ⊕ B Tab. 2-7 Pravdivostní tabulka nonekvivalence
A 0 0 1 1
B 0 1 0 1
Y 0 1 1 0
Obr. 2-6 Používané značení hradel XOR: a) EU, b) US, c) ČSN, d) IEC [1]
3. Realizace logické sítě Každá logická funkce lze realizovat pomocí základních logických členů - hradel. Při realizaci funkce je nutné respektovat pořadí matematických operací. Logickou síť sestavujeme zpravidla z leva doprava. V tomto případě pořadí hradel ukazuje na prioritu operace – z leva hradla vykonávají operace s vyšší prioritou. To je vidět na příkladu sestavení funkce pomocí hradel (obr. 3-1). Nejprve jsou vyčísleny závorky, dále součiny a jako operace s nejnižší prioritou je poslední operací součet.
Y = A ⋅ B ⋅ C + A ⋅ ( B + C ) + ( A + B) ⋅ ( A + C )
Obr. 3-1 Funkce Y realizovaná pomocí základních logických členů
9
4. Minimalizace logické funkce Jak již bylo v úvodu řečeno, minimalizování logické funkce, resp. úkonů, které musí digitální obvod řešit dle stanovených požadavků, vede k úspoře času potřebnému k výpočtu, materiálu a energie. Nutnost zvýšení výpočetního výkonu a snížení nákladů na provoz a výrobu se zvyšuje také s počtem použitých prvků v rámci systému a jejich řetězení. Veškeré minimalizační metody vycházejí z Booleovy algebry.
4.1.
Booleova algebra
V roce 1847 anglický matematik Georgie Bool vytvořil algebru logiky pro zjednodušování složených výroků, později byla tato algebra nazvána Booleova algebra. V té době ovšem nebyla tolik doceněna a opravdové využití pro ni přišlo až v souvislosti s reléovými obvody a s rozvojem číslicové techniky. Díky ní lze systematicky navrhovat číslicová zařízení s minimálním počtem prvků. Boolova algebra se dělí do několika skupin, přičemž každému pravidlu pro logický součet odpovídá obdobné pravidlo pro logický součin – funkce logického součtu a součinu jsou navzájem duální. Zákony pro logické operace dle Booleovy algebry se dají rozdělit do několika skupin: Komutativní A+ B = B+ A A⋅ B = B ⋅ A Asociativní A ⋅ (B + C) = A ⋅ B + A ⋅ C A + ( B ⋅ C ) = ( A + B) ⋅ ( A + C ) Distributivní A + B + C = A + ( B + C ) = ( A + B) + C A ⋅ B ⋅ C = A ⋅ ( B ⋅ C ) = ( A ⋅ B) ⋅ C Dvojité negace
O neutrálnosti A+0 = A A ⋅1 = 1 Absorpce A+ A = A A⋅ A = A A + A⋅ B = A A ⋅ ( A + B) = A
( A + B) ⋅ ( A + B) = A A⋅ B + A⋅ B = A A(1 + B) = A ⋅ 1 = A A ⋅ A + A ⋅ B = A + A ⋅ B = A ⋅ (1 + B) A ⋅ 1 = A Absorpce negace A + AB = A + B
A= A Vyloučení třetího A+ A =1 A⋅ A = 0 O agresivnosti A +1 = 1 A⋅0 = 0
A ⋅ ( A + B) = A ⋅ B
10
4.2. De Morganovy zákony Využívají principů duality Booleovy algebry. Umožňují určení duální funkce k negovanému součtu nebo součinu s libovolným počtem členů definovaných v přímém tvaru. Výsledkem potom je duální výraz tvořený přímým součtem nebo součinem definovanými ve tvaru inverzním. Rovnice 4-1 De Morganovy zákony
A ⋅ B ⋅ C... = A + B + C ... A + B + C... = A ⋅ B ⋅ C ... Jedním z omezení je, že proměnné jsou pouze v jednom tvaru - přímém, nebo negovaném, dále pak je použit pouze jeden typ operátoru, aby byl převod možný. Ze zákonů je také patrné, že každé hradlo NAND lze nahradit hradlem OR a NOR hradlem AND. Toho se využívá především tehdy, je-li logická funkce realizována různými logickými operátory. Při návrhu je totiž výhodnější použít pouze jeden typ operátoru. Například používáme-li integrované obvody plnící určitou log. funkci, často jich bývá více v jednom pouzdře - zpravidla násobky dvou. Oproti využití 3 ze 4 integrovaných invertorů, 3 ze 4 hradel AND a jednoho logického součtu, jak je tomu na obrázku níže, lze po zjednodušení stejnou funkci zrealizovat pomocí 3 ze 4 integrovaných invertorů a 4 ze 4 hradel NAND, čímž odpadá nutnost použít o integrovaný obvod navíc.
Obr. 4-1 Zjednodušení obvodu s využitím de Morganových zákonů
11
Libovolnou základní logickou funkcí lze definovat vždy dvěma symboly. Jeden z nich využívá součinového, druhý součtového hradla. Stejně užitečná je i úprava symbolu invertoru. Podle principu de Morganových zákonů lze také odvodit obdobný zákon pro další log. funkce.
Obr. 4-2 Ekvivalentní funkce hradel
I když de Morganovy zákony názorně objasňují princip duality Booleovy algebry, nejsou ve své základní formě dostatečně univerzální, neumožňují přehlednou práci se složitějšími výrazy nebo proměnnými v obecném tvaru.
4.3. Karnaughova mapa Karnaughovy mapa je to matematický nástroj pro práci s logickými funkcemi. Umožňuje realizovat prakticky všechny operace Booleovy algebry a téměř vždy platí pravidlo, že pro zjednodušení funkce o více než dvou proměnných je výhodnější použít mapu. Do mapy může být zapsána i obecná logická funkce upravená do tvaru DNT. Tvar mapy pak odpovídá plnému počtu proměnných logické funkce, pravdivostní tabulky Karnaughova mapa umožňuje: - zápis disjunkční funkce nebo pravdivostní tabulky - minimalizaci nebo jiné logické úpravy (např. rozvoj funkce až do úrovně UDNT) - inverzi funkce - určení duální funkce, vzhledem k zápisu zpravidla v konjunkčním tvaru *) DNT – Disjunktivní normální tvar
UDNT – Úplná disjunktivní normální forma
Zapisovaná funkce musí být ve tvaru: Y = f1 ( A) ⋅ f 2 (B ) ⋅ f 3 (C ) ⋅ f 4 (D ) + f 5 ( A) ⋅ f 6 (B ) ⋅ f 7 (C ) ⋅ f 8 (D ) + ...
12
4.3.1. Sestavení Karnaughovy mapy Karnaughova mapa je tvořena tabulkou o 2n políček, kde n je počet vstupních proměnných, platí n = 1, 2, 3, 4…, a počet buněk v řádku či sloupci je násobkem čísla 2. Pro názornost viz obr. 4-3
Obr. 4-3 Odvození velikosti tabulky pro Karnaughovu mapu
Dalším krokem po sestavení tabulky pro Karnaughovu mapu je vytvoření souřadnicového systému. Ten reprezentují vstupní proměnné funkce v závislosti na jejich počtu a je zapisován dle Grayova kódu, tzn. kódu specifického tím, že následující hodnota se od předchozí liší pouze v jednom bitu (viz Obr. 4-4). Ve stejném obrázku je také znázorněno, jak se postupuje při zařazení vstupních proměnných do souřadnic. Když zachováme uvedený postup vytvoření tabulky Karnaughovy mapy platí, že má-li mapa v ose X 2n buněk, pak n je počet proměnných potřebných k určení souřadnice buňky v této ose. To stejné platí pro osu Y. V uvedeném příkladu (obr. 4-4) je tabulka pro 4 vstupní proměnné - N = 4. Tabulka má tedy 16 buněk a rozměr 4 x 4. Protože jsou v ose X 4 buňky (2n = 4), k určení souřadnice buňky na řádku jsou třeba 2 proměnné. V tomto případě totéž platí i pro buňku ve sloupci. Nezáleží na tom, jaké pořadí proměnných zvolíme, avšak je nutné toto pořadí dále respektovat. Tak, jak je uvedeno na příkladu (obr. 4-4), označíme řádek proměnnými. Protože jsou dvě, budou souřadnice popsány Grayovým kódem pro 2 proměnné. Existuje i další způsob označení souřadnic – sloupce a řádky se označí čarou, která reprezentuje souřadnice, kde příslušná proměnná nabývá log. 1. Vychází rovněž z Grayova kódu.
Obr. 4-4 Grayův Karnaughovy mapy
kód
13
a
příklady
označení
souřadnic
4.3.2. Zapsání funkce do Karnaughovy mapy Pro vyplnění Karnaughovy mapy platí pravidla: -
Obvykle se zapisuje pouze ‘1’, nevyplněná buňka odpovídá ‘0’ Pro neúplné funkce se prázdná políčka vyplňují X
Jestliže je sloupec určen například kódem 00, bude na něj odkazovat součin negovaných proměnných A a B ve členu zapisované funkce v úplné normální disjunktivní formě, resp. na buňky pod X-ovou souřadnicí 00 je odkazováno všemi součiny, kde se vyskytuje A ⋅ B . Podobně je tomu u X-ové souřadnice 01, na kterou odkazuje výskyt A ⋅ B v součinu atd. Pokud bude v zapisovaném součinu chybět jedna z proměnných X-ových souřadnic, určující je výskyt druhé z proměnných. Např. výskyt A v zapisovaném součinu ukazuje na buňky ve sloupcích 00 a 01. Stejně tak mohou chybět i všechny proměnné X-ových souřadnic. Na buňky tak ukazují pouze Y-ové souřadnice. Obecně je vybraná buňka na průsečíku řádku a sloupce označených příslušnými souřadnicemi. Obdobně se postupuje pro Y-ové souřadnice. Příklad doplnění funkce Y = ABCD + ABCD + ABC D je na obr. 4-5.
Obr. 4-5 Doplňování funkce do Karnaughovy mapy
Doplňovaná funkce nemusí vždy definovat obsah všech políček Karnaughovy mapy. To může nastat např. v případě, že se jedná o funkci Z proměnných zapsanou pravdivostní tabulkou, která pracuje pouze s některými hodnotami, jež je možné těmito proměnnými popsat. Konkrétně budeme-li chtít extrahovat funkci výstupu logického obvodu funkce tří proměnných - Z = 3: lze popsat 8 stavů (0-7). Jestliže funkce pracuje pouze se stavy 0 – 5, pak jsou zbylé nedefinované a do Karnaughovy mapy je do příslušné buňky zanesen křížek ‘X’ (viz obr. 4-6).
Obr. 4-6 Vytvoření Karnaughovy mapy funkce Y určené tabulkou s některými stavy nedefinovanými
14
4.3.3. Vyhodnocení Karnaughovy mapy Protože tato práce pojednává především o minimalizování logických funkcí, bude vyhodnocení Karnaughovy mapy zaměřeno stejně. Postup zjištění nejjednoduššího možného tvaru logické funkce se odvíjí od utváření co největší skupiny buněk s hodnotou ‘1’ v mapě, které mohou mít pouze 2n buněk (n = 1,2,3 …) a mají tvar obdélníku, přičemž nejmenší obdélník je jedna buňka. Dalšími pravidly pro vyhodnocení mapy jsou: -
-
První a poslední buňka řádku, stejně tak první a poslední buňka sloupce, jsou sousedními buňkami Pokud skupina zabírá v dané ose více buněk, její souřadnice v tomto směru je ta, která se nemění, případně, že zabírá všechny buňky v tomto směru, je určena pouze souřadnicemi směru kolmého Buňka s hodnotou ‘1’ může být obsažena ve dvou i více skupinách Zjednodušenou funkci tvoří součet všech souřadnic určujících skupiny buněk s hodnotou ‘1’, přičemž jsou tyto souřadnice součinovými členy S buňkami s vyznačenými nedefinovanými stavy ‘X’ je možné, pokud je to výhodné pro zjednodušení, pracovat jako s buňkami ‘1’ a tvořit s nimi skupiny dle předchozích pravidel
Na obr. 4-7 jsou příklady vyhodnocení.
Obr. 4-7 Příklady vyhodnocení Karnaughovy mapy
15
Krom Karnaughovy mapy existují i další metody zjednodušení logických funkcí. Pro informaci jsme vybrali tyto dvě: Quine-McCluskeyho metoda Vychází ze stejných principů jako metoda Karnaughových map. Pracuje s implikanty (konjunkcemi) funkce a zjednodušování probíhá ve dvou fázích. Nejprve hledání prostého implikantu (konjunkce minimální součtové formy dané funkce), v druhém kroku se pak vybírá minimální počet prostých implikantů, jejichž součet tvoří formu Patrickova metoda Stejně jako Quine-McCluskeyho metoda pracuje s množinami prostých implikantů a jednotlivých stavů dané funkce. Podle daných pravidel sestavuje tabulku, ze které se vychází při minimalizaci
5. Závěr Cílem práce bylo seznámit studenty se základními principy postupu minimalizace logických funkcí, především s Booleovou algebrou, De Morganovými zákony a Karnaughovými mapami. Problematika těchto metod je mnohem složitější a i ty uvedené se komplikují se zvyšováním počtu proměnných. Často je proces minimalizace automatizován, což jistě šetří návrháři čas, ale i v případech méně rozsáhlých ručních minimalizací je úspora v dalším návrhu značná, a to včetně úspory materiálu, energie a času zpracování informace, jak bylo řečeno již v úvodu.
6. Zdroje Logická funkce
http://cs.wikipedia.org/wiki/Logick%C3%A1_funkce
Logické operace
http://cs.wikipedia.org/wiki/Logick%C3%A1_operace
Bitové operátory
http://cs.wikipedia.org/wiki/Bitov%C3%BD_oper%C3%A1tor
Booleho algebra
http://elektronika.ezin.cz/ http://mvt.ic.cz/dva/prp/prp-03.pdf http://www.prochazka.profitux.cz/booleova-algebra.a6.html http://artemis.osu.cz/polpo/07/05a_Booleova_algebra.pdf
Minimalizační metody
http://jjohnyk.sweb.cz/elektronika/12.htm http://ww.webpark.cz/cviceni02.pdf
De Morganovy zákony
http://www.prochazka.profitux.cz/de-morganovy-zakony.a7.html
Logické členy
http://cs.wikipedia.org/wiki/Logick%C3%BD_%C4%8Dlen#AND Arendáš V.: Číslicová technika. Bohumín, 2002
Karnaughova mapa
http://www.prochazka.profitux.cz/karnaughova-mapa.a12.html
16
7. Zadání cvičení A) Zrealizujte pomocí hradel funkci Y a pro hodnoty A = 1, B = 1 a C = 1. Zobrazte její výsledek na sedmisegmentovém displayi, případně na diodě. Po té funkci zjednodušte pomocí Karnaughovy mapy a opět zobrazte. Porovnejte původní a zjednodušenou funkci i logické obvody, které ji realizovaly. Y = A ⋅ B ⋅ C + A ⋅ ( B + C ) + ( A + B) ⋅ ( A + C )
Postup minimalizování 1. Úprava na úplnou součtovou normální formu s pomocí zákonů Booleovy algebry Y = A ⋅ B ⋅ C + A ⋅ ( B + C ) + ( A + B) ⋅ ( A + C ) Y = A ⋅ B ⋅ C + AB + AC + A A + AC + B A + BC Y = A ⋅ B ⋅ C + AB + AC + AC + B A + BC 2. Sestavení a vyhodnocení Karnaughovy mapy
3. Minimalizovaná funkce Y = A+ B
17
B) Vytvořte dekodér kódu 2 z 5 na BCD. Ze zadané tabulky získejte využitím Karnaughovy mapy minimalizovanou funkci a nakreslete schéma logické sítě. 7-1 Pravdivostní tabulka převodu kódu 2z5 do BCD 2z5 BCD S 0 1 2 3 4 5 6 7 8 9
X1 1 0 0 0 0 0 0 1 1 1
X2 1 0 0 0 1 1 1 0 0 0
X3 0 0 1 1 0 0 1 0 0 1
X4 0 1 0 1 0 1 0 0 1 0
X5 0 1 1 0 1 0 0 1 0 0
y1 0 0 0 0 0 0 0 0 1 1
y2 0 0 0 0 1 1 1 1 0 0
y3 0 0 1 1 0 0 1 1 0 0
y4 0 1 0 1 0 1 0 1 0 1
1. Sestavení Karnaughových map a jejich vyhodnocení y1:
y2:
y1 = X 1 X 4 + X 1 X 3
y2 = X 1 X 2 + X 1 X 5
y3:
y4:
y4 = X 1 X 4 + X 1 X 2 X 4
y3 = X 1 X 3 + X 1 X 5
18
2. Sestavení logické sítě
19
