Quine-McCluskey-Algorithmus - Quine–McCluskey algorithm

Hasse-Diagramm des Suchgraphen des Algorithmus für 3 Variablen. Gegeben zB die Untermenge der untersten Knoten (hellgrün), berechnet der Algorithmus eine minimale Menge von Knoten (hier: , dunkelgrün), die genau überdeckt .${\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}$

Der Quine-McCluskey Algorithmus ( QMC ), auch bekannt als die Methode der Primimplikanten , ist ein Verfahren zur verwendet Minimierung der Booleschen Funktionen , die entwickelt wurde , durch Willard V. Quine 1952 und verlängert durch Edward J. McCluskey 1956. Als allgemeines Prinzip wurde dieser Ansatz bereits 1878 von dem Logiker Hugh McColl demonstriert , 1937 von Archie Blake bewiesen und 1954 von Edward W. Samson und Burton E. Mills sowie 1955 von Raymond J. Nelson wiederentdeckt.Ebenfalls 1955 schlugen Paul W. Abrahams und John G. Nordahl sowie Albert A. Mullin und Wayne G. Kellner eine dezimale Variante der Methode vor.

Der Quine-McCluskey-Algorithmus ist funktional identisch mit dem Karnaugh-Mapping , aber die Tabellenform macht ihn effizienter für die Verwendung in Computeralgorithmen und bietet auch eine deterministische Möglichkeit, zu überprüfen, ob die minimale Form einer Booleschen Funktion erreicht wurde. Es wird manchmal als die Tabellenmethode bezeichnet.

Die Methode umfasst zwei Schritte:

1. Finde alle Primimplikanten der Funktion.
2. Verwenden Sie diese Primimplikanten in einem Primimplikantendiagramm , um die wesentlichen Primimplikanten der Funktion sowie andere Primimplikanten zu finden, die zur Abdeckung der Funktion erforderlich sind.

Komplexität

Der Quine-McCluskey-Algorithmus ist zwar praktischer als Karnaugh-Mapping, wenn es um mehr als vier Variablen geht, hat aber auch einen begrenzten Anwendungsbereich, da das Problem, das er löst, NP-vollständig ist . Die Laufzeit des Quine-McCluskey-Algorithmus wächst exponentiell mit der Anzahl der Variablen. Für eine Funktion von n Variablen kann die Anzahl der Primimplikanten bis zu 3 ⁿ / ln( n ) betragen , zB für 32 Variablen kann es über 534 × 10 ¹² Primimplikanten geben. Funktionen mit einer großen Anzahl von Variablen müssen mit potenziell nicht optimalen heuristischen Verfahren minimiert werden, von denen der heuristische Logikminimierer von Espresso 1995 der De-facto-Standard war.

Schritt zwei des Algorithmus läuft auf die Lösung des Mengenüberdeckungsproblems hinaus ; In diesem Algorithmusschritt können NP-harte Instanzen dieses Problems auftreten.

Beispiel

Eingang

In diesem Beispiel ist die Eingabe eine boolesche Funktion in vier Variablen, die auf die Werte und ausgewertet wird, auf und auf einen unbekannten Wert ausgewertet wird , und auf überall (wo diese ganzen Zahlen in ihrer binären Form für die Eingabe in für Prägnanz von interpretiert werden Notation). Die Eingaben, die ausgewertet werden, werden 'Minterms' genannt. Wir verschlüsseln all diese Informationen schriftlich ${\displaystyle f:\{0,1\}^{4}\to \{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).\,}$

Dieser Ausdruck besagt, dass die Ausgabefunktion f für die Minterms und 1 ist (bezeichnet durch den 'm'-Term) und dass wir uns nicht um die Ausgabe für und- Kombinationen (bezeichnet durch den 'd'-Term) kümmern . ${\displaystyle 4,8,10,11,12}$${\displaystyle 15}$${\displaystyle 9}$${\displaystyle 14}$

Schritt 1: Primimplikanten finden

Zuerst schreiben wir die Funktion als Tabelle (wobei 'x' für egal ist):

	EIN	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

Aus dieser Tabelle kann man leicht den kanonischen Produktsummenausdruck bilden , indem man einfach die Minterms summiert (wobei die egalen Terme weggelassen werden ), wobei die Funktion zu eins ausgewertet wird:

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

was nicht minimal ist. Zur Optimierung werden also alle Minterms, die zu Eins ausgewertet werden, zuerst in einer Minterm-Tabelle platziert. In diese Tabelle werden auch gleichgültige Begriffe eingefügt (Namen in Klammern), sodass sie mit Minterms kombiniert werden können:

Anzahl von 1s	Minterm	Binäre Darstellung
1	m4	0100
	m8	1000
2	(m9)	1001
	m10	1010
	m12	1100
3	m11	1011
	(m14)	1110
4	m15	1111

An dieser Stelle kann man beginnen, Minterms mit anderen Minterms zu kombinieren. Wenn sich zwei Begriffe nur durch eine einzige Ziffer unterscheiden, kann diese Ziffer durch einen Bindestrich ersetzt werden, der anzeigt, dass die Ziffer keine Rolle spielt. Nicht mehr kombinierbare Begriffe sind mit einem Stern (*) gekennzeichnet. Zum Beispiel 1000und 1001kann zu ergeben kombiniert werden, was 100-anzeigt, dass beide Minterms implizieren, dass die erste Ziffer ist 1und die nächsten beiden sind 0.

Anzahl von 1s	Minterm	0-Würfel	Implikanten der Größe 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	—

Wenn Sie von Größe 2 zu Größe 4 wechseln, wird es -als dritter Bitwert behandelt . Zum Beispiel -110und -100kann kombiniert werden, um zu geben -1-0, wie kann -110und -11-zu geben -11-, aber -110und 011-kann nicht, weil -110von 1110while 011-nicht impliziert wird. (Trick: Ordne den -ersten zu.)

Anzahl von 1s	Minterm	0-Würfel	Implikanten der Größe 2		Implikanten der Größe 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		—	—

Hinweis: In diesem Beispiel kann keiner der Terme der Implikantentabelle der Größe 4 weiter kombiniert werden. Generell sollte dieser Vorgang so lange fortgesetzt werden (Größen 8, 16 etc.), bis keine Begriffe mehr kombiniert werden können.

Schritt 2: Primimplikantendiagramm

Da keiner der Terme weiter kombiniert werden kann, konstruieren wir an dieser Stelle eine essentielle Primimplikantentabelle. An der Seite stehen die gerade erzeugten Primimplikanten und oben die zuvor angegebenen Minterms. Die egalen Begriffe werden nicht oben platziert – sie werden in diesem Abschnitt weggelassen, da sie keine notwendigen Eingaben sind.

	4	8	10	11	12	fünfzehn	⇒	EIN	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	—

Um die wesentlichen Primimplikanten zu finden, laufen wir entlang der obersten Reihe. Wir müssen nach Spalten mit nur einem "✓" suchen. Wenn eine Spalte nur ein "✓" hat, bedeutet dies, dass der Minterm nur von einem Primimplikanten abgedeckt werden kann. Dieser Primimplikant ist wesentlich .

Beispiel: In der ersten Spalte steht bei minterm 4 nur ein "✓". Dies bedeutet, dass m(4,12) wesentlich ist. Also platzieren wir einen Stern daneben. Minterm 15 hat auch nur ein "✓", also ist auch m(10,11,14,15) zwingend erforderlich. Nun sind alle Spalten mit einem „✓“ abgedeckt.

Der zweite Primimplikant kann durch den dritten und vierten 'überdeckt' werden, und der dritte Primimplikant kann durch den zweiten und ersten 'überdeckt' werden, und beides ist daher nicht wesentlich. Wenn ein Primimplikant essentiell ist, muss er erwartungsgemäß in die minimierte boolesche Gleichung aufgenommen werden. In einigen Fällen decken die wesentlichen Primimplikanten nicht alle Minterms ab, in diesem Fall können zusätzliche Verfahren zur Diagrammreduktion eingesetzt werden. Das einfachste "zusätzliche Verfahren" ist Versuch und Irrtum, aber ein systematischerer Weg ist die Methode von Petrick . Im aktuellen Beispiel verarbeiten die essentiellen Primimplikanten nicht alle Minterms, daher können in diesem Fall die essentiellen Implikanten mit einem der beiden nicht-essentiellen zu einer Gleichung kombiniert werden:

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

oder

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

Diese beiden letzten Gleichungen sind funktionell äquivalent zur ursprünglichen, ausführlichen Gleichung:

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

Siehe auch

• Kanonische Form von Blake
• Buchberger-Algorithmus – analoger Algorithmus für algebraische Geometrie
• Petricks Methode
• Qualitative Vergleichsanalyse (QCA)

Verweise

Weiterlesen

• Curtis, Herbert Allen (1962). „Kapitel 2.3. McCluskeys Methode“. Ein neuer Ansatz für das Design von Schaltkreisen . Die Bell Laboratories-Reihe (1 Hrsg.). 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 . arche:/13960/t56d6st0q. (viii+635 Seiten) (Hinweis: Dieses Buch wurde 1969 von Chin Jih nachgedruckt.)
• Coudert, Olivier (Oktober 1994). "Zweistufige Logikminimierung: ein Überblick" (PDF) . Integration, das VLSI-Journal . 17–2 (2): 97–140. doi : 10.1016/0167-9260(94)00007-7 . ISSN  0167-9260 . Archiviert (PDF) vom Original am 10.05.2020 . Abgerufen 2020-05-10 . (47 Seiten)
• Jadhav, Vitthal; Buchade, Amar (2012-03-08). „Modifizierte Quine-McCluskey-Methode“. arXiv : 1203,2289 [ cs.OH ]. (4 Seiten)
• Crenshaw, Jack (2004-08-19). "Alles über Quine-McClusky" . embedded.com . Archiviert vom Original am 10.05.2020 . Abgerufen 2020-05-10 .
• Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (Dezember 2003) [2003-03-05, 2002-04-09]. "WWW-basierte Boolesche Funktionsminimierung" (PDF) . Internationale Zeitschrift für Angewandte Mathematik und Informatik . 13 (4): 577–584. Archiviert (PDF) vom Original am 10.05.2020 . Abgerufen 2020-05-10 . [7] [8] (7 Seiten)
• Duşa, Adrian (2008-10-01) [September 2007]. „Ein mathematischer Ansatz für das Boolesche Minimierungsproblem“. Qualität & Quantität . 44 : 99–113. doi : 10.1007/s11135-008-9183-x . S2CID  123042755 . Artikelnummer: 99 (2010). [9] (22 Seiten)
• Duşa, Adrian (2007). "Verbesserung von Quine-McCluskey" (PDF) . Universität Bukarest . Archiviert (PDF) vom Original am 12.05.2020 . Abgerufen 2020-05-12 .(16 Seiten) (NB. QCA , eine Open Source, R-basierte Implementierung, die in den Sozialwissenschaften verwendet wird.)

Externe Links

• Implementierung des Quine-McCluskey-Algorithmus mit einer Suche nach allen Lösungen von Frédéric Carpon.
• Karċma 3 , Eine Reihe von Logiksynthesewerkzeugen, einschließlich Karnaugh-Maps, Quine-McCluskey-Minimierung, BDDs, Wahrscheinlichkeiten, Lehrmodul und mehr. Logic Circuits Synthesis Labs (LogiCS) - UFRGS , Brasilien.
• BFunc , QMC-basierte Boolesche Logik-Vereinfacher, die bis zu 64 Eingänge / 64 Ausgänge (unabhängig) oder 32 Ausgänge (gleichzeitig) unterstützen, von António Costa
• Python- Implementierung von Robert Dick, mit einer optimierten Version .
• Python- Implementierung zum symbolischen Reduzieren von Booleschen Ausdrücken.
• Quinessence , eine Open-Source-Implementierung, die in Free Pascal von Marco Caminati geschrieben wurde.
• minBool eine Implementierung von Andrey Popov.
• QMC-Applet , ein Applet zur schrittweisen Analyse des QMC-Algorithmus von Christian Roth
• C++-Implementierung SourceForge.net C++-Programm, das den Algorithmus implementiert.
• Perl-Modul von Darren M. Kulp.
• Tutorial Tutorial zur Methode von Quine-McCluskey und Petrick.
• Petrick C++-Implementierung (einschließlich Petrick) basierend auf dem obigen Tutorial.
• C-Programm Public Domain-Konsolenbasiertes C-Programm auf SourceForge.net.
• Ein vollständig ausgearbeitetes Beispiel finden Sie unter: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
• Der Boolean Bot: Eine JavaScript-Implementierung für das Web: http://booleanbot.com/
• Open Source GUI QMC Minimierer
• Computersimulationscodes für die Quine-McCluskey-Methode von Sourangsu Banerji.