Quine – McCluskey-algoritme - Quine–McCluskey algorithm

Hasse-diagram over algoritmens søgegraf for 3 variabler. Givet f.eks. Delmængden af de nederste knudepunkter (lysegrøn), beregner algoritmen et minimalt sæt noder (her :, mørkegrøn), der dækker nøjagtigt .${\ displaystyle S = \ {abc, a {\ overline {b}} c, {\ overline {a}} bc, {\ overline {a}} b {\ overline {c}}, {\ overline {a} } {\ overline {b}} c \}}$${\ displaystyle \ {{\ overline {a}} b, c \}}$${\ displaystyle S}$

Den Quine-McCluskey algoritmen ( QMC ), også kendt som metode til prime implicants , er en metode til minimering af Boolske funktioner der blev udviklet af Willard V. Quine i 1952 og forlænget ved Edward J. McCluskey i 1956. Som en generel princippet denne tilgang var allerede blevet demonstreret af logikeren Hugh McColl i 1878, blev bevist af Archie Blake i 1937 og blev genopdaget af Edward W. Samson og Burton E. Mills i 1954 og af Raymond J. Nelson i 1955.Også i 1955 foreslog Paul W. Abrahams og John G. Nordahl samt Albert A. Mullin og Wayne G. Kellner en decimalvariant af metoden.

Quine – McCluskey-algoritmen er funktionelt identisk med Karnaugh-kortlægning , men tabelformularen gør den mere effektiv til brug i computeralgoritmer, og den giver også en deterministisk måde at kontrollere, at den minimale form for en boolsk funktion er nået. Det kaldes undertiden tabuleringsmetoden.

Metoden involverer to trin:

1. Finde alle primære implikanter af funktionen.
2. Brug disse primære implikanter i et primært implikantdiagram for at finde de væsentligste primære implikanter af funktionen såvel som andre primære implikanter, der er nødvendige for at dække funktionen.

Kompleksitet

Selvom det er mere praktisk end Karnaugh-kortlægning, når det drejer sig om mere end fire variabler, har Quine – McCluskey-algoritmen også et begrænset anvendelsesområde, da det problem, den løser, er NP-komplet . Den køretid for Quine-McCluskey algoritmen vokser eksponentielt med antallet af variable. For en funktion af n variabler kan antallet af primimplantater være så stort som 3 ⁿ / ln ( n ), fx for 32 variabler kan der være over 534 × 10 ¹² primære implikanter. Funktioner med et stort antal variabler skal minimeres med potentielt ikke-optimale heuristiske metoder, hvoraf Espresso heuristisk logik minimering var de facto standard i 1995.

Trin to af algoritmen svarer til at løse problemet med indstillet dækning ; NP-hårde forekomster af dette problem kan forekomme i dette algoritmetrin.

Eksempel

Indgang

I dette eksempel indgangen er en boolesk funktion i fire variable, som evalueres til på værdier og , evaluerer en ukendt værdi på og , og til alle andre steder (hvor disse heltal fortolkes i deres binær form for input til for kort og præcist og af notation). De input, der evalueres til kaldes 'mintermer'. Vi koder alle disse oplysninger ved at skrive ${\ displaystyle f: \ {0,1 \} ^ {4} \ til \ {0,1 \}}$${\ displaystyle 1}$${\ displaystyle 4,8,10,11,12}$${\ displaystyle 15}$${\ displaystyle 9}$${\ displaystyle 14}$${\ displaystyle 0}$${\ displaystyle f}$${\ displaystyle 1}$

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

Dette udtryk siger, at outputfunktionen f vil være 1 for mintermerne og (betegnet med 'm' sigtet), og at vi ikke er ligeglade med output for og kombinationer (betegnet med 'd' sigtet). ${\ displaystyle 4,8,10,11,12}$${\ displaystyle 15}$${\ displaystyle 9}$${\ displaystyle 14}$

Trin 1: Find primære implikanter

Først skriver vi funktionen som en tabel (hvor 'x' står for ligeglad):

	EN	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 let danne den kanoniske sum af produktudtryk fra denne tabel ved simpelthen at summere mintermerne (udelader ikke-ligegyldige udtryk ), hvor funktionen evalueres til en:

f _{A, B, C, D} = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.

hvilket ikke er minimalt. Så for at optimere placeres alle mintermer, der vurderes til en, først i en mintabell. Ikke-pleje-vilkår tilføjes også i denne tabel (navne i parentes), så de kan kombineres med mintermer:

Antal 1s	Minterm	Binær repræsentation
1	m4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

På dette tidspunkt kan man begynde at kombinere mintermer med andre mintermer. Hvis to udtryk kun adskiller sig med et enkelt ciffer, kan dette ciffer erstattes med en bindestreg, der indikerer, at cifret ikke betyder noget. Vilkår, der ikke kan kombineres mere, er markeret med en stjerne (*). For eksempel 1000og 1001kan kombineres for at give 100-, hvilket indikerer, at begge mintermer antyder, at det første ciffer er, 1og de næste to er 0.

Antal 1s	Minterm	0-terning	Implantater i størrelse 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	-

Når du går fra størrelse 2 til størrelse 4, skal du behandle den -som en tredje bitværdi. For eksempel -110og -100kan kombineres for at give -1-0, som kan -110og -11-give -11-, men -110og 011-kan ikke, fordi det -110er underforstået af 1110mens 011-det ikke er. (Trick: Match det -første.)

Antal 1s	Minterm	0-terning	Implantater i størrelse 2		Implantater i størrelse 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		-	-

Bemærk: I dette eksempel kan ingen af ​​udtrykkene i tabellen størrelse 4 implikanter kombineres yderligere. Generelt skal denne proces fortsættes (størrelse 8, 16 osv.), Indtil der ikke kan kombineres flere termer.

Trin 2: Diagram med primært implikant

Ingen af ​​termerne kan kombineres længere end dette, så på dette tidspunkt konstruerer vi en vigtig primær implikanttabel. Langs siden går de primære implikanter, der lige er genereret, og langs toppen går de tidligere angivne mintermer. De ligegyldige vilkår er ikke placeret øverst - de er udeladt fra dette afsnit, fordi de ikke er nødvendige input.

	4	8	10	11	12	15	⇒	EN	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	-

For at finde de væsentligste primære implikanter løber vi langs den øverste række. Vi skal kigge efter kolonner med kun en "✓". Hvis en kolonne kun har et "✓", betyder det, at minterm kun kan dækkes af et primært implikant. Dette primære implikant er vigtigt .

For eksempel: i den første kolonne, med minterm 4, er der kun en "✓". Dette betyder, at m (4,12) er afgørende. Så vi placerer en stjerne ved siden af ​​den. Minterm 15 har også kun et "✓", så m (10,11,14,15) er også vigtigt. Nu er alle kolonner med en "✓" dækket.

Det andet primære implikant kan 'dækkes' af det tredje og det fjerde, og det tredje primære implikant kan 'dækkes' af det andet og første, og ingen af ​​dem er således væsentlige. Hvis et primært implikant er vigtigt, er det som forventet nødvendigt at inkludere det i den minimerede boolske ligning. I nogle tilfælde dækker de væsentligste primære implikanter ikke alle mintermer, i hvilket tilfælde yderligere procedurer til kortreduktion kan anvendes. Den enkleste "yderligere procedure" er forsøg og fejl, men en mere systematisk måde er Petricks metode . I det nuværende eksempel håndterer de essentielle primære implikanter ikke alle mintermerne, så i dette tilfælde kan de essentielle implikanter kombineres med en af ​​de to ikke-essentielle for at give en ligning:

f _{A, B, C, D} = BC'D '+ AB' + AC

eller

f _{A, B, C, D} = BC'D '+ AD' + AC

Begge disse endelige ligninger svarer funktionelt til den originale, detaljerede ligning:

f _{A, B, C, D} = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.

Se også

• Blake kanonisk form
• Buchbergers algoritme - analog algoritme til algebraisk geometri
• Petricks metode
• Kvalitativ komparativ analyse (QCA)

Referencer

Yderligere læsning

• Curtis, Herbert Allen (1962). "Kapitel 2.3. McCluskeys metode". En ny tilgang til design af koblingskredsløb . The Bell Laboratories Series (1 udgave). 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 sider) (NB. Denne bog blev genoptrykt af Chin Jih i 1969.)
• Coudert, Olivier (oktober 1994). "To-niveau logisk minimering: en oversigt" (PDF) . Integration, VLSI Journal . 17–2 (2): 97–140. doi : 10.1016 / 0167-9260 (94) 00007-7 . ISSN  0167-9260 . Arkiveret (PDF) fra originalen den 2020-05-10 . Hentet 10.05.2020 . (47 sider)
• Jadhav, Vitthal; Buchade, Amar (2012-03-08). "Modificeret Quine-McCluskey-metode". arXiv : 1203.2289 [ cs.OH ]. (4 sider)
• Crenshaw, Jack (2004-08-19). "Alt om Quine-McClusky" . embedded.com . Arkiveret fra originalen 2020-05-10 . Hentet 10.05.2020 .
• Tomaszewski, Sebastian P .; Celik, Ilgaz U .; Antoniou, George E. (december 2003) [2003-03-05, 2002-04-09]. "WWW-baseret boolsk funktionsminimering" (PDF) . International Journal of Applied Mathematics and Computer Science . 13 (4): 577-584. Arkiveret (PDF) fra originalen den 2020-05-10 . Hentet 10.05.2020 . [7] [8] (7 sider)
• Duşa, Adrian (2008-10-01) [september 2007]. "En matematisk tilgang til det boolske minimeringsproblem". Kvalitet og mængde . 44 : 99–113. doi : 10.1007 / s11135-008-9183-x . S2CID  123042755 . Artikelnummer: 99 (2010). [9] (22 sider)
• Duşa, Adrian (2007). "Forbedring af Quine-McCluskey" (PDF) . University of Bucharest . Arkiveret (PDF) fra originalen den 2020-05-12 . Hentet 12-05-2020 .(16 sider) (NB. QCA , en open source, R-baseret implementering anvendt inden for samfundsvidenskab.)

eksterne links

• Quine-McCluskey algoritme implementering med en søgning efter alle løsninger , af Frédéric Carpon.
• Karċma 3 , Et sæt logiske synteseværktøjer inklusive Karnaugh-kort, Quine-McCluskey-minimering, BDD'er, sandsynligheder, undervisningsmodul og mere. Logic Circuits Synthesis Labs (LogiCS) - UFRGS , Brasilien.
• BFunc , QMC-baserede boolske logiske forenklere, der understøtter op til 64 indgange / 64 udgange (uafhængigt) eller 32 udgange (samtidigt), af António Costa
• Python- implementering af Robert Dick med en optimeret version .
• Python- implementering til symbolsk reduktion af boolske udtryk.
• Quinessence , en open source-implementering skrevet i Free Pascal af Marco Caminati.
• minBool en implementering af Andrey Popov.
• QMC applet , en applet til en trinvis analyse af QMC-algoritmen af ​​Christian Roth
• C ++ implementering SourceForge.net C ++ program, der implementerer algoritmen.
• Perl-modul af Darren M. Kulp.
• Tutorial Tutorial om Quine-McCluskey og Petricks metode.
• Petrick C ++ implementering (inklusive Petrick) baseret på vejledningen ovenfor.
• C-program Public Domain-konsolbaseret C-program på SourceForge.net.
• For et fuldt udarbejdet eksempel, besøg: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• The Boolean Bot: En JavaScript-implementering til internettet: http://booleanbot.com/
• open source gui QMC minimizer
• Computersimuleringskoder til Quine-McCluskey-metoden , af Sourangsu Banerji.