Quine-McCluskeyova metoda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. března 2021; kontroly vyžadují 23 úprav .

Quine -McCluskey metoda je  tabulková metoda pro minimalizaci booleovských funkcí navržená Willardem Quinem a vylepšená Edwardem McCluskeyem . Jde o snahu zbavit se nedostatků Quineovy metody .

Minimalizační algoritmus

  1. Termíny (konjunktivní v případě SDNF a disjunktivní v případě SKNF ), na kterých je definována funkce logické algebry (FAL), jsou zapsány jako jejich binární ekvivalenty;
  2. Tyto ekvivalenty jsou rozděleny do skupin, každá skupina obsahuje ekvivalenty se stejným počtem jedniček (nul);
  3. Párové srovnání ekvivalentů (pojmů) v sousedních skupinách se provádí za účelem vytvoření členů nižších řad;
  4. Je sestavena tabulka, ve které jsou záhlaví řádků počátečními termíny a záhlaví sloupců jsou termíny nižších pozic;
  5. Jsou umístěny štítky, které odrážejí absorpci termínů vyšších úrovní (počáteční termíny) a poté je provedena minimalizace podle Quineovy metody .

Funkce

Specifikem metody Quine-McCluskey ve srovnání s metodou Quine je snížení počtu párových srovnání pro jejich lepení. Snížení je dosaženo díky počátečnímu rozdělení členů do skupin se stejným počtem jedniček (nul). To umožňuje vyloučit srovnání, která zjevně nedávají lepení.

Ačkoli je metoda Quine-McCluskey praktičtější než Karnaughovy mapy , pokud jde o více než čtyři proměnné, má také omezení rozsahu, protože doba běhu metody roste exponenciálně s rostoucími vstupními daty. Lze ukázat, že pro funkci n proměnných je horní hranice počtu hlavních implikantů 3 n / n . Pokud n = 32, může být více než 6,5 * 10 15 . Viz také problém transcomputingu .

Funkce s velkým počtem proměnných musí být minimalizovány pomocí potenciálně suboptimální heuristiky . Dnes je heuristický algoritmus minimalizace espressa de facto světovým standardem [1] .

Příklad

Krok 1: najděte hlavní implikanty

Nechť funkci zadáme pomocí následující pravdivostní tabulky :

#
0 0 0 0 0 0
jeden 0 0 0 jeden 0
2 0 0 jeden 0 0
3 0 0 jeden jeden 0
čtyři 0 jeden 0 0 jeden
5 0 jeden 0 jeden 0
6 0 jeden jeden 0 0
7 0 jeden jeden jeden 0
#
osm jeden 0 0 0 jeden
9 jeden 0 0 jeden jeden
deset jeden 0 jeden 0 jeden
jedenáct jeden 0 jeden jeden jeden
12 jeden jeden 0 0 jeden
13 jeden jeden 0 jeden 0
čtrnáct jeden jeden jeden 0 jeden
patnáct jeden jeden jeden jeden jeden

SDNF lze snadno napsat jednoduchým sečtením mintermů (ignorováním neúplně definovaných pojmů ), kde funkce nabývá hodnoty 1.

Pro optimalizaci zapisujeme mintermy, včetně těch, které odpovídají indiferentním stavům, do následující tabulky:

Množství 1 Minterm Binární reprezentace
jeden M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
čtyři M15 1111

Nyní můžete začít kombinovat mintermy mezi sebou, to znamená provádět operaci lepení. Pokud se dva mintermové liší pouze znakem, který je v obou na stejné pozici, nahradíme tento znak znakem „-“, což znamená, že tento znak pro nás není důležitý. Termíny, které nelze dále kombinovat, jsou označeny „*“. Při přechodu na implikanty druhé řady interpretujeme "-" jako třetí hodnotu. Například: -110 a -100 nebo -11- lze kombinovat, ale ne -110 a 011-. (Tip: Nejprve porovnejte "-".)

Množství "1" Minterms | Implikanti úrovně 1 | Implikanti úrovně 2 ------------------------------------|------------- ------- ----|--------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* ------------------------------| m(8,10) 10-0 |----------------------- 2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-----------------------| m12 1100 | m(9,11) 10-1 | ------------------------------| m(10,11) 101- | 3 m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ------------------------------------|------------- ------- ----| 4 m15 1111 | m(11,15) 1-11 | | m(14,15) 111- |

Krok 2: Tabulka primárních implikantů

Když další kombinace již není možná, sestrojíme tabulku hlavních implikantů. Zde bereme v úvahu pouze ty výstupy funkce, na kterých záleží, tedy nevěnujeme pozornost neúplně definovaným stavům.

čtyři osm 9 deset jedenáct 12 čtrnáct patnáct
m(4,12) X X -100
m(8,9,10,11) X X X X deset--
m(8,10,12,14) X X X X 1--0
m(10,11,14,15) X X X X 1-1-

Princip implikantního výběru je stejný jako v Quineově metodě . Jednoduché implikanty, které jsou jádry, jsou zobrazeny tučně. V tomto příkladu jádra nepokrývají všechny mintermy, v takovém případě lze provést další postup zjednodušení tabulky (viz Petrikova metoda ). Dostaneme následující možnost:

Poznámky

  1. ↑ VP Nelson ea, Digital Circuit Analysis and Design , Prentice Hall, 1995, str. 234

Odkazy