Kapitola1
Minimalizace logických funkcí, použití zákonů Booleovy algebry
V předchozím textu „Úvod do logických funkcí a logických obvodů“ jsme se zabývali základy logických funkcí, logických obvodů, jejich realizace pomocí elementárních logických hradel a způsoby zápisu a vyjádření logických funkcí. Tento text se pak věnuje problematice minimalizace logických funkcí a jejich realizace pomocí základních logických hradel.
Definice
Minimalizaci logické funkce můžeme definovat jako proces hledání minimální formy funkce [1].
Definice
Minimální forma logické funkce je taková forma, která obsahuje minimální počet termů a/nebo tyto termy funkce obsahují minimální počet nezávisle proměnných [1].
Poznámka
Pojmy logická funkce, nezávisle proměnná a term jsme definovali v předchozím textu „Úvod do logických funkcí a logických obvodů“, raději je však pro jejich připomenutí zopakujeme:
  • Logická funkce – funkce obecně představuje soubor pravidel pro jednoznačné přiřazení mezi kombinacemi nezávisle proměnných a funkčních hodnot. Logická funkce pak navíc uvažuje logické proměnné a logické funkční hodnoty. V případě tzv. dvouhodnotové logiky jsou jimi logická 0 a logická 1, často doplněné o tzv. neurčitý stav [1].
  • Nezávisle proměnná (logická) – je myšlena jako obecná proměnná nezávislá na jiných proměnných nebo funkčních hodnotách, která může nabývat jen omezeného počtu logických hodnot, logické 0, logické 1, případně neurčitého stavu [1].
  • Term – představuje matematický výraz obsahující každou nezávisle proměnnou jedenkrát, buď v přímém či negovaném tvaru. Termy rozdělujeme na součinové (pokud obsahují operaci logického součinu mezi jednotlivými proměnnými) a součtové (obsahují naopak operaci logický součet proměnných) [1].
Souhrn
Pod pojmem minimalizace logické funkce lze tedy v zásadě chápat zjednodušení tvaru (vyjádření) dané logické funkce.
Při minimalizaci logické funkce je však potřeba mít stále na paměti, že minimalizací nelze změnit funkční hodnoty, tzn. minimalizovaná forma funkce musí být stále tou stejnou funkcí, jako funkce na počátku procesu minimalizace!
Výhody
Důvody pro minimalizace funkcí a z toho plynoucí výhody lze zejména uvést [2]:
  • Minimalizací můžeme potenciálně snížit počet nezávisle proměnných funkce a/nebo jejích termů.
  • Pro realizaci minimální formy v podobě logického obvodu je obvykle potřeba nižší počet hradel.
  • Díky zapojení nižšího počtu hradel můžeme snížit zpoždění obvodu, jeho spotřebu, plochu, kterou zabírá např. v FPGA (Field Programmable Gate Array) poli, apod.
  • V průběhu minimalizace můžeme rovněž provádět převod formy funkce, upravit počty proměnných v jejích termech a jinak upravit vyjádření funkce s ohledem na její realizaci požadovanými typy logických hradel a jejich parametrů (počty vstupů) apod.
Nevýhody
Z možných nevýhod minimalizace logických funkcí můžeme uvést potenciální riziko vzniku tzv. logického hazardu v obvodu realizujícím minimální tvar funkce [2]. Problematikou logických hazardů se bude blíže zabývat navazující text „Kombinační logické obvody a hazardy v kombinačních obvodech“.
Z předchozího textu „Úvod do logických funkcí a logických obvodů“ můžeme pro další vysvětlení a popis procesu minimalizace logických funkcí a jejich realizace pomocí hradel shrnout důležité poznatky.
Souhrn
  • Jednotkový bod funkce – jedná se o takový stav (kombinaci nezávisle proměnných) funkce, kdy funkce nabývá hodnoty logické 1 [3].
  • Nulový bod funkce – je naopak stav, kdy funkce nabývá hodnoty logické 0 [3].
  • Minimální úplný soubor logických funkcí – je takový soubor elementárních logických funkcí, pomocí kterého můžeme vyjádřit libovolnou logickou funkci a který obsahuje co nejmenší počet těchto elementárních funkcí. V praxi nejdůležitější jsou funkce (hradla) NAND a NOR, z nichž každá tvoří sama o sobě minimální úplný soubor logických funkcí [3].
Dále jsme si v případě algebraického vyjádření logických funkcí uvedli dva základní tvary (formy) funkce:
  • úplná normální disjunktní forma – součtová forma obsahující součty součinových termů,
  • úplná normální konjunktní forma – součinová forma obsahující součiny součtových termů.
A také jsme i z ukázkového příkladu v textu „Úvod do logických funkcí a logických obvodů“ odvodili, že pro vyjádření disjunktní formy funkce vybíráme jednotkové body funkce a neurčité stavy, zatímco pro získání konjunktní formy funkce jsou důležité nulové body funkce a neurčité stavy. Disjunktní formu funkce posléze snáze realizujeme pomocí hradel NAND, konjunktní forma funkce se lépe hodí pro realizaci hradly NOR [4].
Připomeňme si tedy také pravdivostní tabulky funkcí NAND a NOR, jak je uvádí tabulka 1 [4].
Tabulka 1. Pravdivostní tabulka funkcí NAND a NOR.
a
b
NAND=a⋅b¯
NOR=a+b¯
0
0
1
1
0
1
1
0
1
0
1
0
1
1
0
0
Pro další postup a pokračování v tématu minimalizace logických funkcí si uvedeme ještě další důležité pojmy a jejich vysvětlení.
Definice
  • Pokrytí – hovoříme o něm v souvislosti, kdy konkrétní term pokrývá stav či několik stavů konkrétní logické funkce a chápeme jej tedy tak, že daný term nabývá hodnoty logická 1 v těchto stavech funkce [4].
  • Implikant funkce – jedná se o term (součtový nebo součinový), který nabývá hodnoty logická 1 ve stejných stavech, kdy i daná logická funkce nabývá hodnoty logická 1 [4].
  • Prostý implikant funkce – je takový implikant funkce, který přestává být implikantem funkce, vyloučíme-li z něj kteroukoli z nezávisle proměnných [4].
Pro lepší představu si tyto důležité pojmy vysvětlíme i na příkladu funkce zapsané pomocí Karnaughovy mapy.
Příklad
Mějme funkci f 4 proměnných a, b, c, d zakreslenou do Karnaughovy mapy na obrázku 1 a zapsanou v disjunktním tvaru:
f=a⋅b¯⋅c∨a¯⋅c⋅d∨b⋅c⋅d .
+
1. Vysvětlení pojmů implikant a prostý implikant funkce pomocí příkladu Karnaughovy mapy.
Obr. 1. Vysvětlení pojmů implikant a prostý implikant funkce pomocí příkladu Karnaughovy mapy.
V mapě je vyplněno 5 jednotkových bodů funkce f (vysvětlíme si později) a naším úkolem je rozhodnout, zda jsou implikanty či prostými implikanty funkce f následující termy:
  1. ab¯cd  – jde o implikant funkce f (zelená smyčka v mapě), neboť tento term pokrývá jeden jednotkový bod funkce, ale zároveň vytvořená zelená smyčka není největší možná a z výrazu by šlo proměnnou d vyloučit (vysvětlíme si dále).
  1. cd  – jde o prostý implikant funkce f (červená smyčka v mapě), neboť pokrývá 4 jednotkové body funkce a nelze z něho již žádnou z obou proměnných vyloučit, aniž by přestal být implikantem funkce f.
  1. bc  – není implikantem funkce f (modrá smyčka v mapě), protože pokrývá sice 2 jednotkové body funkce f, ale zbylé 2 body z tohoto termu leží v nulových bodech funkce f.
Tak, jak jsme si definovali úplné normální formy funkce ÚNDF a ÚNKF, doplníme je o jejich minimální varianty.
Definice
  • Minimální normální disjunktní forma funkce (MNDF) – vznikne minimalizací ÚNDF, jedná se tedy o součtový tvar funkce obsahující nejmenší počet prostých součinových implikantů funkce [5].
  • Minimální normální konjunktní forma funkce (MNKF) – analogicky se jedná o minimalizovanou formu ÚNKF, jde o součinový tvar funkce obsahující nejmenší počet prostých součtových implikantů funkce [5].
Souhrn
Proces minimalizace logické funkce tedy můžeme definovat jako hledání prostých součtových či součinových implikantů funkce.
Pro minimalizaci logických funkcí existuje několik různých metod, každá má své výhody a nevýhody. V praxi nejužívanější jsou zejména:
  • algebraická metoda pomocí přímé aplikace zákonů Booleovy algebry,
  • minimalizace pomocí Karnaughových map,
  • minimalizace pomocí rovinných n-rozměrných těles,
  • minimalizace pomocí algoritmu Quine-McCluskey.
V tomto textu se zaměříme na první dvě metody, metody. Minimalizace pomocí těles a pomocí algoritmu Quine-McCluskey budou popsány v navazujícím textu.