Algoritmus Quine – McCluskey - Quine–McCluskey algorithm

Hasseův diagram vyhledávacího grafu algoritmu pro 3 proměnné. Dáno např. podmnožina ${ displaystyle S = {abc, a { overline {b}} c, { overline {a}} bc, { overline {a}} b { overline {c}}, { overline {a} } { overline {b}} c }}$ uzlů spodní úrovně (světle zelená), algoritmus vypočítá minimální sadu uzlů (zde: ${ displaystyle {{ overline {a}} b, c }}$, tmavě zelená), která přesně kryje ${ displaystyle S}$.

The Algoritmus Quine – McCluskey (QMC), také známý jako metoda hlavních implikantů, je metoda používaná pro minimalizace z Booleovské funkce který vyvinul Willard V. Quine v roce 1952^[1][2] a prodlouženo o Edward J. McCluskey v roce 1956.^[3] Obecně tento přístup logik již prokázal Hugh McColl v roce 1878,^[4][5][6] bylo prokázáno Archiem Blakem v roce 1937,^[7][8][9][6] a byl znovuobjeven Edwardem W. Samsonem a Burtonem E. Millsem v roce 1954^[10][6] a Raymond J. Nelson v roce 1955.^[11][6] Také v roce 1955 Paul W. Abrahams a John G. Nordahl^[12] stejně jako Albert A. Mullin a Wayne G. Kellner^{[13][14][15][16]} navrhl desítkovou variantu metody.^{[17][14][15][16][18][19][20][21]}

Algoritmus Quine – McCluskey je funkčně shodný s Karnaughovo mapování, ale tabulkový tvar umožňuje jeho efektivnější použití v počítačových algoritmech a také poskytuje deterministický způsob kontroly, zda bylo dosaženo minimální formy booleovské funkce. Někdy se jí říká tabelační metoda.

Metoda zahrnuje dva kroky:

1. Nalezení všech hlavní implikanti funkce.
2. Použijte tyto hlavní implikanty v a primární implicitní graf najít základní primární implikátory funkce, stejně jako další primární implikanty, které jsou nezbytné k pokrytí funkce.

Složitost

Ačkoli praktičtější než Karnaughovo mapování při práci s více než čtyřmi proměnnými má algoritmus Quine – McCluskey také omezený rozsah použití, protože problém řeší to NP-kompletní.^[22][23][24] The provozní doba algoritmu Quine – McCluskey roste exponenciálně s počtem proměnných. Pro funkci n proměnných může být počet hlavních implikantů až 3ⁿln (n), např. pro 32 proměnných může být více než 534 × 10¹² hlavní implikanti. Funkce s velkým počtem proměnných musí být minimalizovány s potenciálně neoptimálními heuristický metody, z nichž Minimalizátor heuristické logiky espressa byl de facto standardem v roce 1995.^{[potřebuje aktualizaci ][25]}

Druhý krok algoritmu představuje řešení nastavit problém s krytem;^[26] NP-tvrdé instance tohoto problému mohou nastat v tomto kroku algoritmu.^[27][28]

Příklad

Vstup

V tomto příkladu je vstup booleovská funkce ve čtyřech proměnných, ${ displaystyle f: {0,1 } ^ {4} do {0,1 }}$ který se hodnotí na ${ displaystyle 1}$ na hodnotách ${ displaystyle 4,8,10,11,12}$ a ${ displaystyle 15}$, vyhodnotí neznámou hodnotu dne ${ displaystyle 9}$ a ${ displaystyle 14}$a do ${ displaystyle 0}$ všude jinde (kde jsou tato celá čísla pro vstup interpretována v binární formě ${ displaystyle f}$ pro stručnost notace). Vstupy, které se vyhodnotí ${ displaystyle 1}$ se nazývají „mintermy“. Všechny tyto informace zakódujeme písemně

${ displaystyle f (A, B, C, D) = součet m (4,8,10,11,12,15) + d (9,14). ,}$

Tento výraz říká, že výstupní funkce f bude 1 pro mintermy ${ displaystyle 4,8,10,11,12}$ a ${ displaystyle 15}$ (označeno výrazem „m“) a že nás nezajímá výstup pro ${ displaystyle 9}$ a ${ displaystyle 14}$ kombinace (označené výrazem „d“).

Krok 1: Hledání hlavních implikantů

Nejprve napíšeme funkci jako tabulku (kde 'x' znamená nestarám se):

	A	B	C	D	F
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	0	0	1	1	0
m4	0	1	0	0	1
m5	0	1	0	1	0
m6	0	1	1	0	0
m7	0	1	1	1	0
m8	1	0	0	0	1
m9	1	0	0	1	X
m10	1	0	1	0	1
m11	1	0	1	1	1
m12	1	1	0	0	1
m13	1	1	0	1	0
m14	1	1	1	0	X
m15	1	1	1	1	1

Jeden může snadno vytvořit kanonický součet produktů výraz z této tabulky, jednoduše sečtením mintermy (vynechat nezáleží na tom ) kde se funkce vyhodnotí jako jedna:

F_ABECEDA = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.

což není minimální. Abychom to optimalizovali, všechny mintermy, které se vyhodnotí jako jedna, jsou nejprve umístěny v minterm tabulce. Do této tabulky jsou také přidány termíny, které se nestarají (názvy v závorkách), takže je lze kombinovat s mintermy:

Číslo 1 s	Minterm	Binární Zastoupení
1	m4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

V tomto okamžiku lze začít kombinovat mintermy s jinými mintermy. Pokud se dva výrazy liší pouze o jednu číslici, lze tuto číslici nahradit pomlčkou, která označuje, že na číslici nezáleží. Výrazy, které již nelze kombinovat, jsou označeny hvězdičkou (*). Například 1000 a 1001 lze kombinovat dát 100-, což znamená, že obě mintermy znamenají, že první číslice je 1 a další dva jsou 0.

Číslo 1 s	Minterm	0-kostka	Implikátoři velikosti 2
1	m4	0100	m (4,12)	-100*
	m8	1000	m (8,9)	100-
	—	—	m (8,10)	10-0
	—	—	m (8,12)	1-00
2	m9	1001	m (9,11)	10-1
	m10	1010	m (10,11)	101-
	—	—	m (10,14)	1-10
	m12	1100	m (12,14)	11-0
3	m11	1011	m (11,15)	1-11
	m14	1110	m (14,15)	111-
4	m15	1111	—

Při přechodu z velikosti 2 na velikost 4 zacházejte - jako třetí bitová hodnota. Například, -110 a -100 lze kombinovat dát -1-0, jak může -110 a -11- dát -11-, ale -110 a 011- nemůže, protože -110 je naznačeno 1110 zatímco 011- není. (Trik: Spojte se - za prvé.)

Číslo 1 s	Minterm	0-kostka	Implikátoři velikosti 2		Implikátoři velikosti 4
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	—
	—	—	m (8,12)	1-00	—
2	m9	1001	m (9,11)	10-1	m (10,11,14,15)	1-1-*
	m10	1010	m (10,11)	101-	—
	—	—	m (10,14)	1-10	—
	m12	1100	m (12,14)	11-0	—
3	m11	1011	m (11,15)	1-11	—
	m14	1110	m (14,15)	111-	—
4	m15	1111		—	—

Poznámka: V tomto příkladu nelze dále kombinovat žádný z výrazů v tabulce implikantů velikosti 4. Obecně by tento proces měl pokračovat (velikosti 8, 16 atd.), Dokud nebude možné kombinovat další výrazy.

Krok 2: Připravte implicitní graf

Žádný z těchto výrazů nelze kombinovat dále, takže v tomto okamžiku vytvoříme základní primární implikativní tabulku. Podél strany jsou hlavní implikátoři, kteří byli právě vygenerováni, a podél horní části mintermy specifikované dříve. Termíny, které se nestarají, nejsou umístěny nahoře - jsou z této části vynechány, protože nejsou nezbytnými vstupy.

	4	8	10	11	12	15	⇒	A	B	C	D
m (4,12) *							⇒	—	1	0	0
m (8,9,10,11)							⇒	1	0	—	—
m (8,10,12,14)							⇒	1	—	—	0
m (10,11,14,15) *							⇒	1	—	1	—

Abychom našli základní primární implikanty, běžíme podél horní řady. Musíme hledat sloupce pouze s jedním „✓“. Pokud má sloupec pouze jeden znak „✓“, znamená to, že minterm lze pokrýt pouze jedním hlavním implikantem. Tento hlavní implikant je nezbytný.

Například: v prvním sloupci s minterm 4 je pouze jedno „✓“. To znamená, že m (4,12) je zásadní. Vedle toho tedy umístíme hvězdu. Minterm 15 má také pouze jedno „✓“, takže m (10,11,14,15) je také nezbytné. Nyní jsou pokryty všechny sloupce s jedním „✓“.

Druhý hlavní implikant může být „krytý“ třetím a čtvrtým a třetí primární implikant může být „pokrytý“ druhým a prvním, a žádný z nich tedy není nezbytný. Pokud je primární implikant zásadní, pak je podle očekávání nutné jej zahrnout do minimalizované booleovské rovnice. V některých případech základní hlavní implikátoři nepokrývají všechny mintermy, v takovém případě lze použít další postupy pro redukci grafů. Nejjednodušší „další postup“ je pokus a omyl, ale je to systematičtější Petrickova metoda. V aktuálním příkladu základní prvočíselné implikanty nezpracovávají všechny mintermy, takže v tomto případě lze základní implikáty kombinovat s jedním ze dvou nepodstatných, čímž se získá jedna rovnice:

F_ABECEDA = BC'D '+ AB' + AC^[29]

nebo

F_ABECEDA = BC'D '+ AD' + AC

Obě tyto konečné rovnice jsou funkčně ekvivalentní původní, podrobné rovnici:

F_ABECEDA = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.

Viz také

• Blake kanonická forma^[7][6]
• Buchbergerův algoritmus - analogický algoritmus pro algebraickou geometrii
• Petrickova metoda
• Kvalitativní srovnávací analýza (QCA)

Reference

Další čtení

• Curtis, H. Allen (1962). „Kapitola 2.3. McCluskeyova metoda“. Nový přístup k návrhu spínacích obvodů. Série Bell Laboratories. Princeton, New Jersey, USA: D. van Nostrand Company, Inc. str. 90–160.
• Coudert, Olivier (říjen 1994). „Minimalizace logiky na dvou úrovních: přehled“ (PDF). Integrace, deník VLSI. 17–2 (2): 97–140. doi:10.1016/0167-9260(94)00007-7. ISSN  0167-9260. Archivováno (PDF) od původního dne 2020-05-10. Citováno 2020-05-10. (47 stránek)
• Jadhav, Vitthal; Buchade, Amar (08.03.2012). "Modifikovaná metoda Quine-McCluskey". arXiv:1203.2289 [cs.OH ]. (4 stránky)
• Crenshaw, Jack (2004-08-19). „Vše o Quine-McClusky“. embedded.com. Archivováno od původního dne 2020-05-10. Citováno 2020-05-10.
• Tomaszewski, Sebastian P .; Celik, Ilgaz U .; Antoniou, George E. (prosinec 2003) [2003-03-05, 2002-04-09]. ""Minimalizace booleovských funkcí na základě WWW " (PDF). International Journal of Applied Mathematics and Computer Science. 13 (4): 577–584. Archivováno (PDF) od původního dne 2020-05-10. Citováno 2020-05-10. [7][8] (7 stránek)
• Duşa, Adrian (01.10.2008) [září 2007]. "Matematický přístup k booleovskému problému minimalizace". Kvalita kvantita. 44: 99–113. doi:10.1007 / s11135-008-9183-x. S2CID  123042755. Číslo článku: 99 (2010). [9] (22 stránek)
• Duşa, Adrian (2007). „Enhancing Quine-McCluskey“ (PDF). Univerzita v Bukurešti. Archivováno (PDF) od původního dne 2020-05-12. Citováno 2020-05-12. (16 stránek) (pozn. QCA, otevřený zdroj, implementace založená na R používaná ve společenských vědách.)

externí odkazy

• Implementace algoritmu Quine-McCluskey s hledáním všech řešení autor: Frédéric Carpon.
• Karċma 3 Sada nástrojů logické syntézy včetně Karnaughových map, minimalizace Quine-McCluskey, BDD, pravděpodobností, výukového modulu a dalších. Laboratoře syntézy logických obvodů (LogiCS) - UFRGS, Brazílie.
• BFunc, Logické zjednodušovače logické logiky založené na QMC podporující až 64 vstupů / 64 výstupů (samostatně) nebo 32 výstupů (současně), António Costa
• Krajta Implementace Robert Dick, s optimalizovaná verze.
• Krajta Implementace pro symbolické snížení logických výrazů.
• Quinessence, implementace open source napsaná ve Free Pascal Marco Caminati.
• minBool implementace Andrey Popov.
• Applet QMC, applet pro podrobnou analýzu algoritmu QMC od Christiana Rotha
• C ++ implementace Program SourceForge.net C ++ implementující algoritmus.
• Perl modul autor: Darren M. Kulp.
• Tutorial Výukový program o Quine-McCluskey a Petrickově metodě.
• Petrick Implementace C ++ (včetně Petricka) na základě výše uvedeného tutoriálu.
• Program C. Program C založený na veřejné doméně na SourceForge.net.
• Úplně propracovaný příklad naleznete na adrese: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• Boolean Bot: Implementace JavaScriptu pro web: http://booleanbot.com/
• open source gui QMC minimalizátor
• Kódy počítačové simulace pro metodu Quine-McCluskey autor: Sourangsu Banerji.