Verfahren nach Quine und McCluskey

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Verfahren nach Quine und McCluskey (QMCV, nach Willard Van Orman Quine und Edward J. McCluskey) ist eine Methode, um Boolesche Funktionen zu minimieren. Der Kern des Verfahrens wurde bereits von Quine vollständig beschrieben. Die Verfeinerungen von McCluskey betreffen im Wesentlichen die praktische algorithmische Durchführbarkeit. Die Minimierung ist u. a. deshalb wichtig, weil dadurch die hardwaretechnische Realisierung einfacher und daher kostengünstiger wird. Der Vorteil dieses Verfahrens ist, dass es sich verhältnismäßig leicht in ein Computerprogramm fassen und so mittels eines Computers ausführen lässt. Das Verfahren benötigt im schlechtesten Fall exponentielle Laufzeit, um eine minimale Lösung zu finden. Das Verfahren findet immer eine minimale Lösung, es ist jedoch möglich, dass es noch andere (gleichwertige) Lösungen gibt, die nicht gefunden werden. Da das zugrunde liegende Problem NP-vollständig ist, gibt es unter der Annahme, dass P ≠ NP gilt, kein in diesem Sinne effizientes Verfahren.

Das Verfahren bezieht sich zunächst nur auf Funktionsdarstellungen in kanonischer disjunktiver Normalform (KDNF). Ausdrücke in konjunktiver Normalform (KNF) lassen sich jedoch ohne weiteres über die Verneinung der betrachteten Funktion zunächst in eine DNF umwandeln, dann wie unten beschrieben minimieren und schließlich durch erneute Verneinung in eine KNF zurücktransformieren.

Beschreibung des Verfahrens[Bearbeiten]

Prinzip[Bearbeiten]

Das Grundprinzip des Quine-McCluskey-Verfahrens beruht auf der folgenden Eigenschaft von Konjunktionstermen: Unterscheiden sich zwei durch Disjunktion verknüpfte Konjunktionsterme nur durch die Negation einer einzigen Variablen, so kann man diese beiden Terme verschmelzen und dabei die betreffende Variable entfernen. Diese Eigenschaft erklärt sich aus folgendem algebraischen Zusammenhang:

x_1 \cdot \ldots \cdot x_i \cdot \ldots \cdot x_n + x_1 \cdot \ldots \cdot \overline{x_i}\cdot \ldots \cdot x_n
= x_1 \cdot \ldots \cdot (x_i + \overline{x_i})\cdot \ldots \cdot x_n
= x_1 \cdot \ldots \cdot x_{i-1} \cdot 1 \cdot x_{i+1} \cdot \ldots \cdot x_n
= x_1 \cdot \ldots \cdot x_{i-1} \cdot x_{i+1} \cdot \ldots \cdot x_n

In diesem Zusammenhang ist es zweckmäßig, eine Boolesche Funktion unter dem Aspekt der Mengenlehre zu betrachten. (Es werden hier nur vollständig definierte Funktionen berücksichtigt):

  • Eine Boolesche Funktion ist als Menge von Konjunktionen aller unabhängigen Variablen darstellbar. Dies entspricht den Funktionswerten der Wahrheitstabelle und ist die Gesamtmenge. Für n unabhängige Variablen beträgt ihre Mächtigkeit 2^n Elemente.
  • Die Elemente werden hierbei auch Elementarkonjunktionen genannt. Dies ist also ein einzelner Funktionswert.
  • Diese Menge teilt sich in zwei Teilmengen auf. Ein Teil, welcher die Funktion zur wahren Aussage macht und ein Teil, welcher die Funktion nicht erfüllt. (Bei Verwendung von '0' und '1' also die Teilmenge der '1' und die Teilmenge der '0' in der Wahrheitstabelle).
  • Eine Konjunktion ist eine Teilmenge dieser Gesamtmenge. Es gibt 3^n mögliche Konjunktionen. (inkl. der Gesamtmenge selbst).

Ein Element der Gesamtmenge ist Element einer Konjunktion, wenn die Belegung der in der Konjunktion enthaltenen Variablen mit den entsprechenden Werten des Elements (Elementarkonjunktion) die Konjunktion zur wahren Aussage macht.

Beispiel:

 x_0 \cdot x_1 \cdot \overline{x_2} \in x_0 \cdot x_1
 \overline{x_0} \cdot x_1 \cdot \overline{x_2} \in\!\!\!\!\!/\, x_0 \cdot x_1

Erstellen der kanonischen disjunktiven Normalform[Bearbeiten]

Das Quine-McCluskey-Verfahren geht nun von einer algebraischen Darstellung der Formel in kanonischer disjunktiver Normalform (KDNF) aus. Eine solche KDNF besteht aus einer Disjunktion von Mintermen. Eine andere Darstellung muss also zuerst in diese Form gebracht werden.

Da in diesem Schritt unter Umständen bis zu 2^n Terme erzeugt werden, gibt es auch Varianten des Verfahrens, die nur eine DNF (statt einer KDNF) benötigen, wie z. B. die Resolventenmethode.

Ermitteln der Primterme[Bearbeiten]

Alle Minterme werden jetzt nach aufsteigender Klasse sortiert, in einer Tabelle aufgelistet. Die Klasse einer Konjunktion ist die Anzahl der darin vorkommenden nicht negierten Variablen.

Man vergleicht nun alle Minterme benachbarter Klassen daraufhin, ob sie sich paarweise um eine einzige Negation unterscheiden. Ist dies der Fall, so verschmilzt man die beiden Terme zu einem neuen Term (der dann natürlich kein Minterm mehr ist) und trägt ihn in eine zweite Tabelle ein. Die beiden verwendeten Terme werden (z. B. durch Abhaken) gekennzeichnet, sind aber auch weiterhin für Vergleiche heranzuziehen.

Auf die verschmolzenen Terme wendet man das Verfahren rekursiv in mehreren Stufen so lange an, bis keine weiteren Verschmelzungen mehr möglich sind. Es ist darauf zu achten, dass beide Terme (Tabellenzeilen) die gleichen Variablen enthalten. Während dieses Vorganges verbleiben einige Terme, die nicht verschmolzen werden konnten. Diese Terme bezeichnet man als Primterme bzw. Primkonjunktionen.

Hierbei treten ab der zweiten Minimierungsstufe die gleichen Konjunktionen mehrfach auf, sie sind jedoch nur einmal in die neue Tabelle einzutragen.

Erstellen der Primtermtabelle[Bearbeiten]

Es ist durchaus möglich, dass nicht alle Primterme benötigt werden. Um herauszufinden, welche Primterme man unbedingt benötigt, erstellt man eine sogenannte Primtermtabelle. Als Spaltenköpfe der Tabelle werden die Minterme verwendet. Als Zeilenköpfe trägt man die Primterme ein. Die einzelnen Zellen der Tabelle sind also Kreuzungspunkte bestimmter Minterme mit bestimmten Primtermen.

Man trägt nun immer dann eine Markierung in der jeweiligen Zelle ein, wenn der Minterm Element des Primterms ist (s. o.).

Dominanzprüfung[Bearbeiten]

Bei der Dominanzprüfung werden obsolete Zeilen und Spalten ermittelt.

Spaltendominanzprüfung[Bearbeiten]

Die Spalten werden paarweise darauf verglichen, ob nicht eine Spalte existiert, in der die markierten Primterme eine Teilmenge der markierten Primterme der anderen Spalte sind. Ist dies der Fall, so kann die Spalte mit der Obermenge gestrichen werden, denn es müssen alle Konjunktionen erfasst werden und daher ist die Konjunktion mit der Obermenge durch Auswahl der Konjunktion mit der Teilmenge ebenfalls erfasst.

Beispiel:

In einer Tabelle stehen u. A. die beiden Spalten

K_a  =  P_1 + P_2 + P_4
K_b  =  P_1 + P_4

Hier kann K_a gestrichen werden, weil er K_b vollständig dominiert. K_a ist daher obsolet und wird ab jetzt nicht mehr berücksichtigt.

Zeilendominanzprüfung[Bearbeiten]

Jetzt vergleicht man die Zeilen (Primterme) der Tabelle paarweise, ob nicht eine Zeile existiert, in denen die markierten Minterme eine Teilmenge der markierten Minterme der anderen Zeile sind. Ist dies der Fall, so kann der Primterm mit der Teilmenge gestrichen werden, denn man kann für jede Markierung des gestrichenen Primterms den anderen Primterm als Ersatz nehmen. Die Relation ist hier also genau umgekehrt wie bei der Spaltendominanz.

Beispiel:

In einer Tabelle stehen u. A. die beiden Zeilen

P_a  =  K_1 + K_2 + K_6 + K_7
P_b  =  K_1 + K_2

Hier kann P_b gestrichen werden, weil er von P_a vollständig dominiert wird. P_b ist daher obsolet und wird ab jetzt nicht mehr berücksichtigt.

Diese beiden Prüfungen werden solange abwechselnd wiederholt, bis bei einer Prüfung keine Zeile/Spalte mehr gestrichen werden kann, mindestens jedoch je einmal.

Auswahl der Primterme[Bearbeiten]

Die verbleibenden Primterme muss man jetzt so auswählen, dass alle Minterme abgedeckt werden. Hierfür kann es mehrere (ggf. gleichwertige) Möglichkeiten geben. Man wählt dabei möglichst wenige und kleine Primterme, da man ja eine optimierte Funktion erreichen möchte, die schließlich mit möglichst wenigen Schaltgattern technisch realisiert werden kann.

Beispiel[Bearbeiten]

Es folgt ein Beispiel, um die Methode zu erklären:

Darstellung als kanonische disjunktive Normalform[Bearbeiten]

Wir gehen von einer Booleschen Funktion f mit vier Eingangsvariablen x_0\dots x_3 aus, deren kanonische disjunktive Normalform so aussieht:

\, f(x_0 , x_1 , x_2 , x_3) = Y =
\begin{matrix}
\\ \overline{x_0} * \overline{x_1} * \overline{x_2} * \overline{x_3} \, + \,
            {x_0} * \overline{x_1} * \overline{x_2} * \overline{x_3} \, + \,
\\ \overline{x_0} * \overline{x_1} *          {x_2} * \overline{x_3} \, + \,
            {x_0} * \overline{x_1} *          {x_2} * \overline{x_3} \, + \,
\\ \overline{x_0} *          {x_1} *          {x_2} * \overline{x_3} \, + \,
            {x_0} *          {x_1} *          {x_2} * \overline{x_3} \, + \, 
\\ \overline{x_0} * \overline{x_1} * \overline{x_2} *          {x_3} \, + \,
            {x_0} * \overline{x_1} * \overline{x_2} *          {x_3} \, + \, 
\\          {x_0} *          {x_1} * \overline{x_2} *          {x_3} \, + \, 
            {x_0} *          {x_1} *          {x_2} *          {x_3} \ \ \ 
\end{matrix}

In anderer Schreibweise:

 Y = m_0 \, + \, m_1 \, + \, m_4 \, + \, m_5 \, + \, m_6 \, + \, m_7 \, + \, m_8 \, + \, m_9 \, + \, m_{11} \, + \, m_{15}

Ermitteln der Primterme[Bearbeiten]


Die Auswahltabellen
Die Ausgangstabelle: Die erste Zusammenfassung ergibt: Es dürfen nur Zeilen zusammengefasst werden, die die "-" an den gleichen Positionen haben (!) Dritte Zusammenfassung
Tabelle 1
m_x x_3 x_2 x_1 x_0 OK

m_0 0 0 0 0

m_1 0 0 0 1
m_4 0 1 0 0
m_8 1 0 0 0

m_5 0 1 0 1
m_6 0 1 1 0
m_9 1 0 0 1

m_7 0 1 1 1
m_{11} 1 0 1 1

m_{15} 1 1 1 1
Tabelle 2
m_x+m_y x_3 x_2 x_1 x_0 OK

m_0+m_1 0 0 0 -
m_0+m_4 0 - 0 0
m_0+m_8 - 0 0 0

m_1+m_5 0 - 0 1
m_1+m_9 - 0 0 1
m_4+m_6 0 1 - 0
m_4+m_5 0 1 0 -
m_8+m_9 1 0 0 -

m_5+m_7 0 1 - 1
m_6+m_7 0 1 1 -
m_9+m_{11} 1 0 - 1 P1

m_7+m_{15} - 1 1 1 P2
m_{11}+m_{15} 1 - 1 1 P3
Tabelle 3
m_w+m_x+m_y+m_z x_3 x_2 x_1 x_0 OK

m_0+m_1+m_4+m_5 0 - 0 - P4
m_0+m_1+m_8+m_9 - 0 0 - P5

m_4+m_6+m_5+m_7 0 1 - - P6
Keine weiteren Zusammenfassungen möglich.


Es ergeben sich daher sechs Primterme:

 \, P_1 =      x_0   *  \overline{x_2}  *  x_3 = m_9     +  m_{11}
 \, P_2 =      x_0   *       x_1   *  x_2 = m_7     +  m_{15}
 \, P_3 =      x_0   *       x_1   *  x_3 = m_{11}  +  m_{15}
 \, P_4 = \overline{x_1}  *  \overline{x_3} =  m_0  +   m_1  +  m_4  +  m_5
 \, P_5 = \overline{x_1}  *  \overline{x_2} =  m_0  +   m_1  +  m_8  +  m_9
 \, P_6 =      x_2   *  \overline{x_3} =  m_4  +   m_5  +  m_6  +  m_7

Erstellen der Primtermtabelle[Bearbeiten]

Die Primtermtabelle sieht so aus:

  m_0 m_1 m_4 m_5 m_6 m_7 m_8 m_9 m_{11} m_{15}
P_1                
P_2                
P_3                
P_4            
P_5            
P_6            

Dominanzprüfung[Bearbeiten]

Die erste Spaltendominanzprüfung ergibt:

  • Streichen von m_0, m_1 und m_9 wegen Spalte m_8
  • Streichen von m_4, m_5 und m_7 wegen Spalte m_6

Danach sieht die Tabelle so aus:

  m_6 m_8 m_{11} m_{15}
P_1      
P_2      
P_3    
P_4        
P_5      
P_6      

Die Zeilendominanzprüfung ergibt:

  • Streichen von P_4 (leer).
  • Streichen von P_2 wegen P_3
  • Streichen von P_1 wegen P_3

Somit erhält man:

  m_6 m_8 m_{11} m_{15}
P_3    
P_5      
P_6      

Eine Zweite Spaltendominanzprüfung ergibt:

  • Streichen von m_{15} wegen m_{11}

Ergebnis:

  m_6 m_8 m_{11}
P_3    
P_5    
P_6    

Eine zweite Zeilendominanzprüfung ergibt keine Streichungen mehr. Damit ist die Dominanzprüfung beendet.

Auswahl der Primterme[Bearbeiten]

Die Auswahl geeigneter Primterme ist hier jetzt sehr einfach, da es nur eine Möglichkeit gibt: Benötigt werden die Primterme P_3, P_5 und P_6.

Verknüpfung der gewählten Primterme[Bearbeiten]

Jetzt müssen die ausgewählten Primterme mittels Disjunktion zur Lösungsgleichung verknüpft werden:

\, Y = P_3\ + P_5 \ + \ P_6
\, Y = x_0 * x_1 * x_3 \quad + \quad \overline{x_1}\ * \overline{x_2} \quad + \quad x_2 * \overline{x_3}

Anmerkung[Bearbeiten]

Das Problem, eine minimale Anzahl von Primtermen aus der Primtermtabelle auszuwählen, ist NP-vollständig; d.h., für viele Fälle ist kein wesentlich besseres Verfahren bekannt, als alle möglichen Auswahlen auszuprobieren. Deshalb bietet es sich an, das Minimum nur näherungsweise zu bestimmen. Beispielsweise wählt man zuerst die Spalten mit nur einer Markierung aus (diese sind zwingend notwendig), danach sucht man in den Spalten mit wenig Markierungen oder in Zeilen mit vielen Markierungen nach geeigneten Termen.

Das Verfahren hat insbesondere bei höherer Variablenzahl Vorteile gegenüber dem Karnaugh-Veitch-Diagramm (KVD). Als Faustregel gilt: Bis fünf Variablen ist das KVD besser, ab sechs Variablen das QMCV.

Weblinks[Bearbeiten]