Quine–McCluskey-algoritm

Hasse diagram över sökgrafen för algoritmen för 3 variabler. Givet t.ex. delmängden ${\displaystyle S=\{abc,a{\overline {b}} c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}} av$ bottennivån noder (ljusgrön), beräknar algoritmen en minimal uppsättning noder (här: $\{{\overline {a}}b,c\}$ , mörkgrön) som täcker exakt $S$ .

Quine –McCluskey-algoritmen ( QMC ), även känd som metoden för prime implicants , är en metod som används för att minimera booleska funktioner som utvecklades av Willard V. Quine 1952 och utökades av Edward J. McCluskey 1956. Som en allmän princip detta tillvägagångssätt hade redan demonstrerats av logikern Hugh McColl 1878, bevisades av Archie Blake 1937 och återupptäcktes av Edward W. Samson och Burton E. Mills 1954 och av Raymond J. Nelson 1955. Även 1955 , Paul W. Abrahams och John G. Nordahl samt Albert A. Mullin och Wayne G. Kellner föreslog en decimalvariant av metoden.

Quine–McCluskey-algoritmen är funktionellt identisk med Karnaugh-mappning , men tabellformen gör den mer effektiv för användning i datoralgoritmer, och den ger också ett deterministiskt sätt att kontrollera att den minimala formen av en boolesk funktion har uppnåtts. Det kallas ibland för tabuleringsmetoden.

Metoden innefattar två steg:

1. Att hitta alla viktiga implikationer av funktionen.
2. Använd dessa prime implikanter i ett prime implicant diagram för att hitta de väsentliga prime implikanterna för funktionen, såväl som andra prime implikanter som är nödvändiga för att täcka funktionen.

Komplexitet

Även om den är mer praktisk än Karnaugh-kartläggning när den hanterar fler än fyra variabler, har Quine–McCluskey-algoritmen också ett begränsat användningsområde eftersom problemet den löser är NP-komplett . Körtiden för Quine–McCluskey-algoritmen växer exponentiellt med antalet variabler. För en funktion av n variabler kan antalet prim-implikanter vara så stort som ${\displaystyle 3^{n}/{\sqrt {n}}},$ t.ex. för 32 variabler kan det vara över 534 × 10 ¹² främsta implikanter. Funktioner med ett stort antal variabler måste minimeras med potentiellt icke-optimala heuristiska metoder, av vilka Espresso heuristisk logikminimering var de facto-standarden 1995.

Steg två av algoritmen går ut på att lösa uppsättningsskyddsproblemet ; NP-hårda instanser av detta problem kan förekomma i detta algoritmsteg.

Exempel

Inmatning

I det här exemplet är indata en boolesk funktion i fyra variabler, $f:\{0,1\}^{4}\to \{0,1\ }$ som utvärderas till $1$ på värdena $4,8,10,11,12$ och $15$ , utvärderas till ett okänt värde på $9$ och $14$ och till $0$ överallt (där dessa heltal tolkas i sin binära form för inmatning till $f$ för kortfattad notation). Ingångarna som utvärderas till $1$ kallas 'minterms'. Vi kodar all denna information genom att skriva

$f(A,B,C,D)=\summa m(4,8,10,11,12,15)+d(9,14).\,$

Detta uttryck säger att utdatafunktionen f kommer att vara 1 för mintermerna $4,8,10,11,12$ och $15$ (betecknas med 'm' term) och att vi inte bryr oss om utdata för $9$ och $14$ kombinationer (betecknas med 'd'-termen). Summeringssymbolen $\sum$ betecknar den logiska summan (logisk ELLER eller disjunktion) av alla termer som summeras.

Steg 1: hitta viktiga implikanter

Först skriver vi funktionen som en tabell (där 'x' står för don't care):

	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

Man kan enkelt bilda den kanoniska summan av produkter uttryck från denna tabell, helt enkelt genom att summera minterms (utelämna don't-care termer ) där funktionen utvärderas till en:

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

vilket inte är minimalt. Så för att optimera placeras alla minterms som utvärderas till en först i en minterm-tabell. Don't care-termer läggs också till i den här tabellen (namn inom parentes), så att de kan kombineras med minterms:

Antal 1:or	Minterm	Binär representation
1	m4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

0 Vid det här laget kan man börja kombinera minterms med andra minterms. Om två termer skiljer sig åt med endast en siffra kan den siffran ersättas med ett streck som anger att siffran inte spelar någon roll. Termer som inte längre kan kombineras är markerade med en asterisk ( * ). Till exempel 1000 och 1001 kombineras för att ge 100- , vilket indikerar att båda mintermerna antyder att den första siffran är 1 och de två nästa är .

Antal 1:or	Minterm	0-Kub	Storlek 2 implikanter
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	—

När du går från storlek 2 till storlek 4, behandla - som ett tredje bitvärde. Matcha - först. Termerna representerar produkter och för att kombinera två produkttermer måste de ha samma variabler. En av variablerna ska kompletteras i en term och ofullbordad i den andra. De återstående variablerna bör överensstämma. Så för att matcha två termer - s passa in och alla utom en av de andra siffrorna måste vara samma. Till exempel -110 och -100 kombineras för att ge -1-0 , liksom -110 och -010 för att ge -10 , men -110 och 011- kan inte eftersom -: en inte är i linje. -110 motsvarar BCD' medan 011- motsvarar A'BC, och BCD' + A'BC motsvarar inte en produktterm.

Antal 1:or	Minterm	0-Kub	Storlek 2 implikanter		Storlek 4 implikanter
1	m4	0100	m(4,12)	-100 *	—
	m8	1000	m(8,9)	100-	m(8,9,10,11)	10-- *
	—		m(8,10)	10-0	m(8,10,12,14)	1--0 *
	—		m(8,12)	1-00	—
2	m9	1001	m(9,11)	10-1	—
	m10	1010	m(10,11)	101-	m(10,11,14,15)	1-1- *
	—		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	—		—

Obs: I det här exemplet kan ingen av termerna i tabellen över implikanter för storlek 4 kombineras ytterligare. I allmänhet bör denna process fortsätta (storlek 8, 16 etc.) tills inga fler termer kan kombineras.

Steg 2: prime implikant diagram

Ingen av termerna kan kombineras längre än så här, så vid denna tidpunkt konstruerar vi en viktig prime implicant-tabell. Längs sidan går de primära implikanterna som just har genererats (detta är de som har markerats med " * " i föregående steg), och längst upp går de mintermer som specificerats tidigare. De bryr sig inte-termerna placeras inte överst – de utelämnas från det här avsnittet eftersom de inte är nödvändiga indata.

	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	—

För att hitta de väsentliga huvudimplikanterna letar vi efter kolumner med endast en "✓". Om en kolumn bara har en "✓", betyder det att mintermen endast kan täckas av en prime implicant. Denna främsta implikant är väsentlig .

Till exempel: i den första kolumnen, med minterm 4, finns det bara en "✓". Detta betyder att m(4,12) är väsentligt. Minterm 15 har också bara en "✓", så m(10,11,14,15) är också viktigt. Nu är alla kolumner med en "✓" täckta.

Den andra prime implikanten kan "täckas" av den tredje och fjärde, och den tredje prime implikanten kan "täckas" av den andra och första, och ingendera är således väsentlig. Om en primär implikant är väsentlig är det, som förväntat, nödvändigt att inkludera den i den minimerade booleska ekvationen. I vissa fall täcker de väsentliga primära implikanterna inte alla minterms, i vilket fall ytterligare procedurer för kortminskning kan användas. Det enklaste "tilläggsförfarandet" är försök och misstag, men ett mer systematiskt sätt är Petricks metod . I det aktuella exemplet hanterar inte de väsentliga primära implikanterna alla minterms, så i det här fallet kan de väsentliga implikanterna kombineras med en av de två icke-väsentliga för att ge en ekvation:

f _A,B,C,D = BC'D' + AB' + AC

eller

f _A,B,C,D = BC'D' + AD' + AC

Båda dessa slutliga ekvationer är funktionellt ekvivalenta med den ursprungliga, utförliga ekvationen:

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

Se även

• Blake kanonisk form
• Buchbergers algoritm – analog algoritm för algebraisk geometri
• Petricks metod
• Kvalitativ jämförande analys (QCA)

Vidare läsning

•       Curtis, Herbert Allen (1962). "Kapitel 2.3. McCluskeys metod". Ett nytt tillvägagångssätt för utformningen av kopplingskretsar . The Bell Laboratories Series (1 upplaga). Princeton, New Jersey, USA: D. van Nostrand Company, Inc. s. 90–160. ISBN 0-44201794-4 . OCLC 1036797958 . S2CID 57068910 . ISBN 978-0-44201794-1 . ark:/13960/t56d6st0q. (viii+635 sidor) (OBS. Den här boken trycktes om av Chin Jih 1969.)
•   Coudert, Olivier (oktober 1994). "Minimering av logik på två nivåer: en översikt" (PDF) . Integration, VLSI Journal . 17–2 (2): 97–140. doi : 10.1016/0167-9260(94)00007-7 . ISSN 0167-9260 . Arkiverad (PDF) från originalet 2020-05-10 . Hämtad 2020-05-10 . (47 sidor)
• Jadhav, Vitthal; Buchade, Amar (2012-03-08). "Modifierad Quine-McCluskey-metod". arXiv : 1203.2289 [ cs.OH ]. (4 sidor)
• Crenshaw, Jack (2004-08-19). "Allt om Quine-McClusky" . embedded.com . Arkiverad från originalet 2020-05-10 . Hämtad 2020-05-10 .
• Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (december 2003) [2003-03-05, 2002-04-09]. "WWW-baserad boolesk funktionsminimering" (PDF) . International Journal of Applied Mathematics and Computer Science . 13 (4): 577–584. Arkiverad (PDF) från originalet 2020-05-10 . Hämtad 2020-05-10 . [7] [8] (7 sidor)
•   Duşa, Adrian (2008-10-01) [september 2007]. "Ett matematiskt förhållningssätt till det booleska minimeringsproblemet". Kvalitet & kvantitet . 44 : 99–113. doi : 10.1007/s11135-008-9183-x . S2CID 123042755 . Artikelnummer: 99 (2010). [9] (22 sidor)
• Duşa, Adrian (2007). "Enhancing Quine-McCluskey" (PDF) . Universitetet i Bukarest . Arkiverad (PDF) från originalet 2020-05-12 . Hämtad 2020-05-12 . (16 sidor) (OBS. QCA , en öppen källkod, R-baserad implementering som används inom samhällsvetenskap.)

externa länkar

• Quine-McCluskey-algoritmimplementering med en sökning av alla lösningar, av Frédéric Carpon.
• Karċma 3 , En uppsättning verktyg för logiksyntes inklusive Karnaugh-kartor, Quine-McCluskey-minimering, BDD:er, sannolikheter, undervisningsmodul och mer. Logic Circuits Synthesis Labs (LogiCS) - UFRGS , Brasilien.
• BFunc , QMC-baserade booleska logiska förenklare som stöder upp till 64 ingångar / 64 utgångar (oberoende) eller 32 utgångar (samtidigt), av António Costa
• Python Implementation av Robert Dick, med en optimerad version .
• Python- implementering för att symboliskt reducera booleska uttryck.
• Quinessence , en implementering med öppen källkod skriven i Free Pascal av Marco Caminati.
• minBool en implementering av Andrey Popov.
• QMC-applet , en applet för en steg-för-steg-analys av QMC-algoritmen av Christian Roth
• C++-implementering SourceForge.net C++-program som implementerar algoritmen.
• Perl Module av Darren M. Kulp.
• Handledning Handledning om Quine-McCluskey och Petricks metod.
• Petrick C++-implementering (inklusive Petrick) baserat på handledningen ovan.
• C-program Public Domain-konsolbaserat C-program på SourceForge.net.
• För ett genomarbetat exempel besök: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• The Boolean Bot: En JavaScript-implementering för webben: http://booleanbot.com/
• öppen källkod gui QMC minimizer
• Datorsimuleringskoder för Quine-McCluskey-metoden, av Sourangsu Banerji.