Steuerungstasten

→ nächste Folie (auch Enter oder Spacebar).
← vorherige Folie
 d  schaltet das Zeichnen auf Folien ein/aus
 p  wechselt zwischen Druck- und Präsentationsansicht
CTRL  +  vergrößert die Folien
CTRL  -  verkleinert die Folien
CTRL  0  setzt die Größenänderung zurück

Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.

Notation

Typ Schriftart Beispiele
Variablen (Skalare) kursiv $a, b, x, y$
Funktionen aufrecht $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vektoren fett, Elemente zeilenweise $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrizen Schreibmaschine $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$
Mengen kalligrafisch $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Zahlenbereiche, Koordinatenräume doppelt gestrichen $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

Inhalt

  • Minimierung eines booleschen Ausdrucks mit dem Quine-McCluskey-Verfahren
    • Finden der Primimplikanten (Phase 1)
    • Aufstellen der Primimplikantentafel (Phase 2)
    • Lösen des Überdeckungsproblems (Phase 3)
    • Lösen zyklischer Überdeckungsprobleme mit dem Verfahren von Petrick

Quine-McCluskey-Verfahren

  • Das Quine-McCluskey-Verfahren erlaubt, boolesche Funktionen zu minimieren
  • Während bei KV-Diagrammen Funktionen mit bis zu 4 Variablen leicht minimiert werden können, ist das Quine-McCluskey-Verfahren auch für Funktionen mit mehr Variablen geeignet
  • Großer Vorteil des Quine-McCluskey-Verfahrens ist, dass es sich relativ einfach auf einem Computer implementieren lässt

Quine-McCluskey-Verfahren

x3x2x1x0y
0:00001
1:00010
2:00100
3:00110
4:01001
5:01010
6:01101
7:01110
8:10000
9:10010
10:10100
11:10111
12:11001
13:11011
14:11101
15:11110
  • Eingabe: Eine Funktion $y = \mathrm{f}(x_{n-1},\dots,x_1,x_0)$ der
    Stelligkeit $n$
    • Angabe z.B. durch DNF
      Beispiel:
      $\begin{align} y =& \mathrm{f}(x_{n-1},\dots,x_1,x_0) =\\ =& m_0 \lor m_4 \lor m_6 \lor m_{11} \lor m_{12} \lor m_{13} \lor m_{14} \\ =& \overline{x}_3 \overline{x}_2 \overline{x}_1 \overline{x}_0 \lor \overline{x}_3 x_2 \overline{x}_1 \overline{x}_0 \lor \\ & \overline{x}_3 x_2 x_1 \overline{x}_0 \lor x_3 \overline{x}_2 x_1 x_0 \lor \\ & x_3 x_2 \overline{x}_1 \overline{x}_0 \lor x_3 x_2 \overline{x}_1 x_0 \lor \\ & x_3 x_2 x_1 \overline{x}_0 \end{align} $
    • oder Wahrheitstafel (siehe rechts)
  • Ausgabe: Ein minimaler boolescher Ausdruck als ODER-Verknüpfung von Monomen (= UND-Verknüpfungen von Literalen)
    • Möglichst wenig ODER-Verknüpfungen
    • Möglichst wenig UND-Verknüpfungen

Quine-McCluskey-Verfahren

  • Die Minimierung nach dem Quine-McCluskey-Verfahren läuft in 3 Phasen ab:
    • Phase 1: Finden der Primimplikanten
    • Phase 2: Aufstellen der Primimplikantentafel
    • Phase 3: Lösen des Überdeckungsproblems

Phase 1: Finden der Primimplikanten

  • Um die Primimplikanten zu finden, wird (wie bei den KV-Diagrammen) das Vereinigungstheorem verwendet:
    $(a \land b) \lor (a \land \lnot b) = a$
  • Bei KV-Diagrammen wird das Vereinigungstheorem rekursiv angewendet, indem immer größere Blöcke aus benachbarten Blöcken gebildet werden
  • Beim Quine-McCluskey-Verfahren wird analog vorgegangen, nur dass statt mit graphischen Blöcken mit Tabelleneinträgen gearbeitet wird

Phase 1: Finden der Primimplikanten

  • Die erste Tabelle enthält die Implikanten der Ordnung 0. Sie wird aus der 1-Menge der Wahrheitstafel extrahiert
  • Die zweite Tabelle enthält die Implikanten der Ordnung 1. Sie wird aus der vorgegangenen Tabelle konstruiert, indem diejenigen Zeilen zusammengefasst werden, die sich in genau einer Variablen unterscheiden
  • Implikanten, die zusammengefasst wurden, werden geeignet markiert
    (hier wird das Zeichen → verwendet)
  • Selbst wenn Implikanten schon zusammengefasst wurden, stehen sie noch zur Verfügung, um mit anderen Implikanten zusammengefasst zu werden
  • Implikanten, die nicht zusammengefasst wurden, sind die gesuchten Primimplikanten. Sie werden ebenfalls markiert
    (hier wird das Zeichen ✓ verwendet)
  • Dieses Verfahren wird rekursiv für Implikanten höherer Ordnung fortgesetzt bis keine Zusammenfassung mehr möglich ist

Phase 1: Finden der Primimplikanten

Wahrheitstafel:

x3x2x1x0y
0:00001
1:00010
2:00100
3:00110
4:01001
5:01010
6:01101
7:01110
8:10000
9:10010
10:10100
11:10111
12:11001
13:11011
14:11101
15:11110

Implikanten (Ordnung 0):

x3x2x1x0
0:0000→
4:0100→
6:0110→
11:1011✓
12:1100→
13:1101→
14:1110→

Phase 1: Finden der Primimplikanten

Implikanten (Ordnung 0):

x3x2x1x0
0:0000→
4:0100→
6:0110→
11:1011✓
12:1100→
13:1101→
14:1110→

Implikanten (Ordnung 1):

x3x2x1x0
0, 4:0-00✓
4, 6:01-0→
4, 12:-100→
6, 14:-110→
12, 13:110-✓
12, 14:11-0→

Implikanten (Ordnung 2):

x3x2x1x0
4, 6, 12, 14:-1-0✓

Phase 2: Aufstellen der Primimplikantentafel

  • Die Primimplikatentafel besteht aus allen Primimplikanten
    (diese wurden in Phase 1 mit ✓ markiert)
  • Zeilen:
    • Pro Primimplikant jeweils eine Zeile
  • Spalten:
    • Jede Spalte steht für einen Minterm $m_i$ der DNF
    • In jeder Spalte wird markiert, ob der Primimplikant den Minterm überdeckt
      (hier wird das Zeichen ○ verwendet)
    • Ist der Primimplikant der einzige Primimplikant, der diesen Minterm überdeckt, so wird er "essentieller Primimplikant" genannt und besonders markiert
      (hier wird das Zeichen ● verwendet)
  • Essentielle Primimplikanten müssen in jedem Fall Teil des minimalen booleschen Ausdrucks sein und werden sofort übertragen

Phase 2: Aufstellen der Primimplikantentafel

Implikanten (Ordnung 0):

x3x2x1x0
0:0000→
4:0100→
6:0110→
11:1011✓
12:1100→
13:1101→
14:1110→

Implikanten (Ordnung 1):

x3x2x1x0
0, 4:0-00✓
4, 6:01-0→
4, 12:-100→
6, 14:-110→
12, 13:110-✓
12, 14:11-0→

Implikanten (Ordnung 2):

x3x2x1x0
4, 6, 12, 14:-1-0✓

Primimplikantentafel:

x3x2x1x004611121314
4, 6, 12, 14:-1-0○●○●(x2x̄0)
0, 4:0-00●○(x̄3x̄1x̄0)
12, 13:110-○●(x3x2x̄1)
11:1011●(x3x̄2x1x0)

Extrahierte essentielle Primimplikanten: (x̄3x̄1x̄0), (x2x̄0), (x3x̄2x1x0), (x3x2x̄1)

Phase 2: Aufstellen der Primimplikantentafel

  • Ist es zufällig so, dass die essentiellen Primimplikanten gemeinsam alle Minterme überdecken, kann der Algorithmus bereits hier beendet werden
  • Der minimale boolesche Ausdruck für das gezeigte Beispiel lautet daher:
    y = (x̄3x̄1x̄0) ∨ (x2x̄0) ∨ (x3x̄2x1x0) ∨ (x3x2x̄1)
  • Ist dies nicht der Fall, muss in Phase 3 eine geeignete Überdeckung gefunden werden

Phase 3: Lösen des Überdeckungsproblems

  • Die essentiellen Primimplikanten müssen in jedem Fall Teil des minimalen booleschen Ausdrucks sein
  • Daher können nach der Übertragung in den booleschen Ausdruck diese Zeilen in der Primimplikantentafel gestrichen werden
  • Ebenfalls können diejenigen Spalten gestrichen werden, die von den essentiellen Primimplikanten überdeckt werden
  • Es entsteht eine "reduzierte Primimplikantentafel"

Phase 3: Lösen des Überdeckungsproblems

  • Die reduzierte Primimplikantentafel kann folgendermaßen vereinfacht werden:
  • Zeilenregel:
    • Existiert für eine Zeile $z_i$ eine andere Zeile $z_j$, die die gleichen und noch weitere Minterme überdeckt, so wird $z_i$ gestrichen
    • Überdecken zwei Zeilen die gleichen Minterme, so wird die Zeile des Primimplikants behalten, der weniger Literale enthält
  • Spaltenregel
    • Wird ein Minterm immer überdeckt, wenn auch ein anderer überdeckt wird (alle Primterme behandeln diese beiden gleich), so kann eine der beiden zugehörigen Spalten gestrichen werden
    • Die Spaltenregel kann die reduzierte Primimplikantentafel übersichtlicher machen, ist aber letztendlich nicht wichtig für das Ergebnis des Verfahrens

Phase 3: Lösen des Überdeckungsproblems

Wahrheitstafel:

x3x2x1x0y
0:00001
1:00010
2:00101
3:00111
4:01000
5:01010
6:01100
7:01111
8:10001
9:10011
10:10100
11:10110
12:11001
13:11010
14:11101
15:11111

Implikanten (Ordnung 0):

x3x2x1x0
0:0000→
2:0010→
3:0011→
7:0111→
8:1000→
9:1001→
12:1100→
14:1110→
15:1111→

Implikanten (Ordnung 1):

x3x2x1x0
0, 2:00-0✓
0, 8:-000✓
2, 3:001-✓
3, 7:0-11✓
7, 15:-111✓
8, 9:100-✓
8, 12:1-00✓
12, 14:11-0✓
14, 15:111-✓

Phase 3: Lösen des Überdeckungsproblems

Primimplikantentafel:

x3x2x1x0023789121415
0, 2:00-0○○(x̄3x̄2x̄0)
0, 8:-000○○(x̄2x̄1x̄0)
2, 3:001-○○(x̄3x̄2x1)
3, 7:0-11○○(x̄3x1x0)
7, 15:-111○○(x2x1x0)
8, 9:100-○●(x3x̄2x̄1)
8, 12:1-00○○(x3x̄1x̄0)
12, 14:11-0○○(x3x2x̄0)
14, 15:111-○○(x3x2x1)

Extrahierte essentielle Primimplikanten: (x3x̄2x̄1)

Phase 3: Lösen des Überdeckungsproblems

Reduzierte Primimplikantentafel (Iteration 0):

x3x2x1x00237121415
0, 2:00-0●○(x̄3x̄2x̄0)
2, 3:001-○○(x̄3x̄2x1)
3, 7:0-11○○(x̄3x1x0)
7, 15:-111○○(x2x1x0)
12, 14:11-0●○(x3x2x̄0)
14, 15:111-○○(x3x2x1)

Extrahierte essentielle Primimplikanten: (x̄3x̄2x̄0), (x3x2x̄0)

Reduzierte Primimplikantentafel (Iteration 1):

x3x2x1x03715
3, 7:0-11●○(x̄3x1x0)
7, 15:-111○●(x2x1x0)

Extrahierte essentielle Primimplikanten: (x̄3x1x0), (x2x1x0)

Phase 3: Lösen des Überdeckungsproblems

  • Nach rekursiver Anwendung des Streichens der Zeilen der essentiellen Primimplikanten und Vereinfachung der reduzierten Primimplikantentafel terminiert das Verfahren häufig
  • Der minimale boolesche Ausdruck kann dann durch die essentiellen Primimplikanten aus allen Rekursionsschritten gebildet werden
  • Der minimale boolesche Ausdruck für das gezeigte Beispiel lautet daher:
    y = (x3x̄2x̄1) ∨ (x̄3x̄2x̄0) ∨ (x3x2x̄0) ∨ (x̄3x1x0) ∨ (x2x1x0)
  • Es gibt aber auch zyklische Überdeckungsprobleme, bei denen das Verfahren nicht terminiert

Zyklische Überdeckungsprobleme

  • Ob ein zyklisches Überdeckungsprobleme vorliegt, kann daran erkannt werden, dass in der Primimplikantentafel (oder der reduzierten Primimplikantentafel) keine essentiellen Primimpliktanten gefunden werden können
  • Damit ist es nicht eindeutig, welcher Primimplikant in die Lösung aufgenommen werden soll und welcher nicht
  • Eine einfache Lösung ist es, alle möglichen Kombinationen von Primimplikanten auszuprobieren, und die Kombination zu verwenden, die eine Überdeckung mit minimalen Kosten liefert
  • Die Anzahl der möglichen Kombinationen steigt jedoch schnell an. Es gibt $2^k$ Kombinationen, wenn $k$ die Anzahl der beteiligten Primimplikanten ist
  • Also z.B. $2^{32}=4294967296$ bei 32 Primimplikanten
  • Viele dieser Kombinationen liefern gar keine Überdeckung. Andere überdecken Minterme unnötigerweise mehrfach und erzeugen nicht minimale Lösungen.
  • Wie kann die Anzahl der betrachteten Kombinationen reduziert werden?

Verfahren von Petrick

  • Zunächst wird jeder Zeile $k$ (bzw. dem korrespondierenden Primterm) eine boolesche Variable $p_k$ zugeordnet
  • $(p_k = 1)$, wenn der Primterm in der Lösung verwendet wird, sonst $(p_k = 0)$
  • Mit den Variablen $p_k$ wird ein boolescher Ausdruck aufgestellt, der nur wahr ist, wenn alle Spalten überdeckt werden
    • Der boolesche Ausdruck besteht dabei aus so vielen UND-Verknüpfungen wie es Spalten gibt:
      (Spalte 1 überdeckt) UND (Spalte 2 überdeckt) UND ....
    • Die Aufgabe, eine Spalte zu überdecken, kann von einem beliebigen Primterm übernommen werden. Daher wird eine ODER-Verknüpfung aus alle Primtermen gebildet, die die jeweilige Spalte überdecken, z.B.:
      ( $p_1$ ODER $p_3$ ) UND ( $p_3$ ODER $p_5$ ) UND ...
  • Anschließend werden die Klammern aufgelöst und der Ausdruck vereinfacht
  • Vereinfacht wird dabei mit den beiden Theoremen:
    Idempotenz: $p_k \land p_k = p_k$ und Absorption: $p_k \lor (p_k \land p_j)= p_k$
  • Nach Auflösung besteht der Ausdruck aus ODER-Verknüpfungen von Monomen der Variablen $p_k$. Jedes Monom beschreibt eine mögliche Lösung

Verfahren von Petrick

Wahrheitstafel:

x2x1x0y
0:0001
1:0010
2:0101
3:0111
4:1001
5:1011
6:1100
7:1111

Implikanten (Ordnung 0):

x2x1x0
0:000→
2:010→
3:011→
4:100→
5:101→
7:111→

Implikanten (Ordnung 1):

x2x1x0
0, 2:0-0✓
0, 4:-00✓
2, 3:01-✓
3, 7:-11✓
4, 5:10-✓
5, 7:1-1✓

Verfahren von Petrick

Primimplikantentafel:

x2x1x0023457
0, 2:0-0○○(x̄2x̄0) ≡ p0
0, 4:-00○○(x̄1x̄0) ≡ p1
2, 3:01-○○(x̄2x1) ≡ p2
3, 7:-11○○(x1x0) ≡ p3
4, 5:10-○○(x2x̄1) ≡ p4
5, 7:1-1○○(x2x0) ≡ p5

(p0 ∨ p1)(p0 ∨ p2)(p2 ∨ p3)(p1 ∨ p4)(p4 ∨ p5)(p3 ∨ p5)

⇔ (p0 ∨ p0p2 ∨ p0p1 ∨ p1p2)(p1p2 ∨ p2p4 ∨ p1p3 ∨ p3p4)(p3p4 ∨ p4p5 ∨ p3p5 ∨ p5)

⇔ (p0 ∨ p1p2)(p1p2 ∨ p2p4 ∨ p1p3 ∨ p3p4)(p3p4 ∨ p5)

⇔ (p0p1p2 ∨ p0p2p4 ∨ p0p1p3 ∨ p0p3p4 ∨ p1p2 ∨ p1p2p4 ∨ p1p2p3 ∨ p1p2p3p4)(p3p4 ∨ p5)

⇔ (p0p2p4 ∨ p0p1p3 ∨ p0p3p4 ∨ p1p2)(p3p4 ∨ p5)

⇔ (p0p2p3p4 ∨ p0p2p4p5 ∨ p0p1p3p4 ∨ p0p1p3p5 ∨ p0p3p4 ∨ p0p3p4p5 ∨ p1p2p3p4 ∨ p1p2p5)

⇔ (p0p2p4p5 ∨ p0p1p3p5 ∨ p0p3p4 ∨ p1p2p3p4 ∨ p1p2p5)

Verfahren von Petrick

  • Jede Lösung kann bezüglich ihrer Kosten bewertet werden
  • Die geringste Anzahl an Primtermen haben die beiden Lösungen p0p3p4 und p1p2p5
  • Jedes Literal pk steht dabei für einen Primterm, der in die Lösung eingeht
  • Gibt es gleich viele Literale, wie im gezeigten Beispiel, entscheidet die Länge der einzelnen Primterme (im gezeigten Beispiel auch gleich)
  • Im gezeigten Beispiel sind daher folgende zwei Lösungen gleichwertig:
    • Lösung 1: y = (x̄2x̄0) ∨ (x1x0) ∨ (x2x̄1)
    • Lösung 2: y =  (x̄1x̄0) ∨ (x̄2x1)∨ (x2x0)

Interaktiver Quine-McCluskey Rechner

  • Durch Klicken auf die grauen Elemente kann die boolesche Funktion verändert werden
    Anzahl der Variablen:    Don’t-Cares erlauben:   

Gibt es Fragen?

questions

Anregungen oder Verbesserungsvorschläge können auch gerne per E-mail an mich gesendet werden: Kontakt


Weitere Vorlesungsfolien

Impressum, Datenschutz,