1.1
N-rozměrná tělesa a jejich rovinný rozvoj
Základní popis n-rozměrných těles a jejich rovinný rozvoj byl uveden v předešlém textu „Úvod do logických funkcí a logických obvodů“.
Souhrn
Metoda n-rozměrných těles a jejich rovinných rozvojů patří do skupiny grafických metod minimalizace logických funkcí [4]. Obecně lze říci, že základní idea vychází ze stejných principů, jako Karnaughovy mapy, n-rozměrná tělesa nabízí pouze mírně odlišnou grafickou interpretaci a vyjádření.
Způsob zakreslení rovinných n-rozměrných těles pro jednu až čtyři nezávisle proměnné jsme si uvedli v předchozím textu „Úvod do logických funkcí a logických obvodů“. Abychom mohli tělesa použít pro minimalizace logických funkcí v tomto textu, raději si jejich nakreslení zopakujeme na obrázku 1.
+
1. Rovinná n-rozměrná tělesa pro jednu až čtyři proměnné.
Obr. 1. Rovinná n-rozměrná tělesa pro jednu až čtyři proměnné.
Poznámka
Protože pro každou nezávisle proměnnou je potřeba přidat do grafického vyjádření tělesa nový rozměr, lze reálně nakreslit tělesa pouze do velikosti tří rozměrů [3]. Pro více proměnných jsou pak n-rozměrná (prostorová) tělesa nahrazována jejich rovinnými rozvoji [4].
Základní způsob zakreslení tělesa a postup pro hledání minimální formy funkce můžeme shrnout do několika bodů [5].
Definice
  • Pro n nezávisle proměnných obsahuje těleso přesně 2n vrcholů. Pro jejich očíslování použijeme Grayův kód (stejně jako v případě číslování políček v Karnaughových mapách).
  • Při hledání MNDF do tělesa vyznačíme jednotkové body a neurčité stavy, pro získání MNKF pak naopak nulové body a neurčité stavy:
    • jednotkové body vyznačíme plným kroužkem,
    • nulové body do tělesa obvykle nevyznačujeme,
    • neurčité stavy zakreslíme jako prázdný kroužek s tečkou.
  • Nyní hledáme a vytváříme tzv. podtělesa. Pro jejich vyznačení platí následující pravidla:
  1. Velikost podtělesa, respektive počet jeho vrcholů, musí odpovídat mocnině čísla 2. Tzn. můžeme vytvářet podtělesa o počtu vrcholů: 1, 2, 4, 8, 16…
  1. Podtělesa musí tvořit vždy uzavřené tvary a být tvořena pouze odpovídajícími vrcholy (viz následující bod).
  1. Pro získání MNDF funkce vytváříme podtělesa z jednotkových bodů a neurčitých stavů. Každý jednotkový bod musí být pokryt alespoň jedním podtělesem, neurčité stavy není nutno pokrývat (pokud se nám daný neurčitý stav hodí pro vytvoření většího podtělesa, použijeme jej).
  1. Naopak pro hledání MNKF funkce, je potřeba podtělesy pokrýt všechny nulové body a neurčité stavy, pouze pokud se nám k tomu hodí.
  1. Spojit do podtělesa můžeme navzájem vždy pouze sousední vrcholy tělesa. Díky použití Grayova kódu pro číslování vrcholů jsou sousední vrcholy v tělese umístěny vždy na spojnici.
  1. Pro získání minimální formy funkce (MNDF i MNKF) se snažíme nalézt a vyznačit co možná nejmenší počet co největších podtěles.
  • Indexy vrcholů v každém podtělese zapíšeme pod sebe v jejich binárním vyjádření. Výsledný součinový term (implikant) pro dané podtěleso získáme tak, že zapíšeme logický součin nezávisle proměnných, které se v rámci celého tohoto tělesa nemění.
  • Výslednou MNDF zapíšeme jako logický součet těchto součinových termů (implikantů) vzniklých z jednotkových bodů a neurčitých stavů, MNKF pak jako negaci logického součtu jednotlivých součinových termů (implikantů) získaných z nulových bodů a neurčitých stavů.
Postup minimalizace a získání formy funkce MNDF i MNKF pomocí tělesa si předvedeme na příkladu.
Příklad
Příklad:
Proveďte minimalizaci logické funkce zadané pomocí zkráceného seznamu stavových indexů a nalezněte její formu MNDF i MNKF pomocí tělesa. MNDF realizujte pomocí hradel NAND a MNKF pomocí hradel NOR.
f = 2, (3), 4, 6, (7)
Zobrazit řešení
Řešení
Řešení:
Postup řešení rozdělíme opět na hledání každé formy funkce zvlášť.
1. MNDF funkce
  1. Nejprve nakreslíme těleso pro tři nezávisle proměnné.
  1. Do tělesa vyznačíme zadané indexy funkce, jak ukazuje obrázek 2.
+
2. Nakreslení tělesa zadané funkce tří proměnných při řešení příkladu.
Obr. 2. Nakreslení tělesa zadané funkce tří proměnných při řešení příkladu.
  1. Na základě postupu uvedeném výše vyznačíme v tělese dvě podtělesa. Zadaná funkce obsahuje jednotkové body 2, 4, 6, které musíme pokrýt, a dva neurčité stavy (3) a (7), které můžeme použít, pokud by nám pomohly vytvořit co největší podtělesa. Pro pokrytí bodů a nalezení MNDF vytvoříme jedno podtěleso o velikosti 4 (vrcholy: 2, 3, 6 a 7) a jedno podtěleso o velikosti 2 (vrcholy: 4 a 6), jak ukazuje obrázek 3.
+
3. Nalezení a vyznačení dvojice podtěles při hledání MNDF zadané funkce.
Obr. 3. Nalezení a vyznačení dvojice podtěles při hledání MNDF zadané funkce.
  1. Zapíšeme nyní indexy daných podtěles v binárním vyjádření, a nalezneme tak součinové termy (implikanty) pro jednotlivá tělesa.
1. podtěleso (červené)
2. podtěleso (modré)
c
b
a
c
b
a
0
1
0
1
0
0
0
1
1
1
1
0
1
1
0
   
1
1
1
   
  1. V případě prvního podtělesa složeného z vrcholů 2, 3, 6 a 7 vidíme z tabulky, že jediná proměnná, která nabývá pro všechny tyto vrcholy vyjádřené v binárním zápise stejné hodnoty, je b a protože její hodnota je logická 1, zapíšeme jako výsledný implikant (součinový term): b .
  1. Z tabulky pro druhé těleso obsahující vrcholy 4 a 6 je zřejmé, že proměnná c nabývá pro oba vrcholy hodnoty logická 1 a proměnná a naopak hodnoty logická 0. Výsledný součinový term (prostý implikant) vyplývající z tohoto tělesa je tedy: a¯⋅c .
  1. Výslednou MNDF funkce získáme jako logický součet jednotlivých prostých implikantů, tedy:
    fD=b∨a¯⋅c .
  1. Zbývá již jen realizovat MNDF funkce pomocí hradel NAND. Opět jako ve všech předešlých případech upravíme nejprve vyjádření MNDF pomocí zákona dvojité negace a následně dle zákona o negaci logického součtu a získáme výraz:
    fD=b∨a¯⋅c¯¯=b¯⋅a¯⋅c¯¯ .
    Realizaci tohoto upraveného tvaru MNDF pak ukazuje obrázek 4.
+
4. Realizace tvaru MNDF zadané funkce f.
Obr. 4. Realizace tvaru MNDF zadané funkce f.
2. MNKF funkce
  1. Pro nalezení MNKF funkce f využijeme opět stejné těleso, neboť nulové body se do těles nezakreslují. Získáme tak těleso dle obrázku 5.
+
5. Nakreslení tělesa zadané funkce tří proměnných při řešení příkladu.
Obr. 5. Nakreslení tělesa zadané funkce tří proměnných při řešení příkladu.
  1. V tělese opět najdeme a vyznačíme co nejmenší počet co největších podtěles tak, abychom pokryli všechny nulové body a neurčité stavy použili, jen pokud je to výhodné. V tomto případě vytvoříme v tělese dvojici podtěles. První podtěleso (na obrázku 6 vyznačeno červeně) obsahuje vrcholy: 1, 3, 5 a 7, druhé (modré) pak vrcholy: 0 a 1. Situaci ilustruje obrázek 6.
+
6. Dvojice podtěles pro pokrytí nulových bodů při hledáni MNKF funkce f.
Obr. 6. Dvojice podtěles pro pokrytí nulových bodů při hledáni MNKF funkce f.
  1. Opět do tabulky zapíšeme indexy vrcholů obou vyznačených podtěles v binárním tvaru, abychom získali příslušné termy.
1. podtěleso (červené)
2. podtěleso (modré)
c
b
a
c
b
a
0
0
1
0
0
0
0
1
1
0
0
1
1
0
1
   
1
1
1
   
  1. Prostý implikant získaný z prvního (červené) podtělesa můžeme vyjádřit jako a , neboť zbylé proměnné se v rámci daných indexů vrcholů mění.
  1. Obdobně pro druhé (modré) podtěleso můžeme vyjádřit prostý implikant jako b¯⋅c¯ . Tyto dvě proměnné opět nabývají shodně hodnoty logická 0 pro oba vrcholy.
  1. MNKF funkce pak zapíšeme jako negaci logického součtu jednotlivých nalezených implikantů funkce, tedy:
    fK=a∨b¯⋅c¯¯=a¯⋅b∨c .
  1. Pro její realizaci hradly NOR nejprve výraz opět upravíme a získáme:
    fK=a¯⋅b∨c¯¯=a¯∨b∨c¯¯ .
    Ten pak již snadno realizujeme pomocí hradel NOR, jak ukazuje obrázek 7.
+
7. Výsledná realizace MNKF funkce f.
Obr. 7. Výsledná realizace MNKF funkce f.
Poznámka
Uvedený příklad se pokuste vyřešit pomocí Karnaughovy mapy a porovnejte, zda se obě řešení shodují či nikoliv.
Další příklad si uvedeme na použití tělesa pro čtyři nezávisle proměnné.
Příklad
Příklad:
Funkce čtyř proměnných je zadána pomocí zkráceného seznamu stavových indexů. Nalezněte její formu MNDF i MNKF za použití tělesa, realizujte obě formy pomocí příslušných hradel.
Funkce je zadána: f = 1, 5, 8, (9), 12, (13), (14), 15.
Zobrazit řešení
Řešení
Řešení:
Řešení příkladu rozdělíme opět na část určení MNDF a část hledání MNKF zadané funkce. Tentokrát budeme používat těleso pro čtyři nezávisle proměnné. Do něho, respektive do jeho vrcholů, zakreslíme zadané indexy funkce f. Získáme tak situaci na obrázku 8.
+
8. Nakreslené těleso s vyznačenými indexy zadaných vrcholů pro hledání MNDF a MNKF funkce f.
Obr. 8. Nakreslené těleso s vyznačenými indexy zadaných vrcholů pro hledání MNDF a MNKF funkce f.
Nyní budeme postupovat opět stejným způsobem jako u výše řešeného příkladu. Nejprve tedy budeme určovat MNDF funkce, v tělese se tudíž budeme snažit spojit pomocí co nejmenšího počtu co největších podtěles vrcholy obsahující logické 1 a případně i neurčité stavy a pokrýt všechny jednotkové body zadané funkce. Pro každé těleso vyjádříme jemu odpovídající implikant a MNDF získáme jejich logickým součtem.
Pro hledání MNKF bude postup obdobný s tím rozdílem, že pokrývat pomocí podtěles budeme naopak nulové body i neurčité stavy. Konečné vyjádření MNKF pak určíme z negace logického součtu součinových termů (implikantů) těchto jednotlivých podtěles.
Celý postup včetně výsledného řešení přehledně představuje následující animace 1.
Animace 1. Řešení nalezení MNDF i MNKF zadané funkce f čtyř proměnných.
Výsledkem minimalizace jsou MNDF a MNKF:
fD=a⋅b¯∨b¯⋅d∨c⋅d .
fK=b⋅d¯∨b⋅c¯∨a¯⋅d¯¯=b¯∨d⋅b¯∨c⋅a∨d .
Abychom mohli obě formy realizovat pomocí hradel (MNDF pomocí hradel NAND, MNKF pomocí hradel NOR), je opět potřeba upravit výrazy pomocí zákona dvojité negace a zákonů o negaci logického součtu a součinu:
fD=a⋅b¯∨b¯⋅d∨c⋅d=a⋅b¯¯⋅b¯⋅d¯⋅c⋅d¯¯ ,
fK=b¯∨d⋅b¯∨c⋅a∨d=b¯∨d¯∨b¯∨c¯∨a∨d¯¯ .
Výslednou realizaci MNDF pomocí hradel NAND představuje obrázek 9.
+
9. Realizace MNDF zadané funkce pomocí hradel NAND.
Obr. 9. Realizace MNDF zadané funkce pomocí hradel NAND.
Díky úpravě výrazu MNKF můžeme tuto formu realizovat pomocí hradel NOR, viz obrázek 10.
+
10. MNKF funkce f realizovaná hradly NOR.
Obr. 10. MNKF funkce f realizovaná hradly NOR.
Výhody
Minimalizace pomocí těles obdobně jako minimalizace Karnaughovými mapami nabízí graficky přehlednou a rychlou metodu minimalizace logických funkcí [1].
Nevýhody
Avšak pro více než pět proměnných se tělesa i jejich rovinné rozvoje stávají značně složitými a pracnými na nakreslení [3]. Obdobně jako metoda založená na Karnaughových mapách i použití těles je do značné míry intuitivní způsob minimalizace, který vyžaduje zkušenosti při hledání podtěles a jejich vyjádření.