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
Download

4. Minimalizace logické funkce