| |
Algorithmus Quine & McCluskey |
Ermittelt kostenminimale Darstellung durch Primimplikanten PI (f).
Eingabe
Funktionstabelle (x, f (x)), x  Bn,
f Boolesche Funktion.
| 1) |
Berechne
Qn :=
{Minterme aller einschlägigen Indizes von f};
d.h. alle Literale mit f = 1
j := n;
PI (f) := { };
|
| 2) |
Solange Qj nichtleer, wiederhole: |
| 2a) |
j := j – 1; |
| 2b) |
Qj
:= {µ | Ex. k: xk, ¬xk sind nicht aus µ; µ xk, µ ¬xk Qj+1
}
d.h. vergleiche Literale (geordnet nach Anzahl der Negationen)
mit um 1 unterschiedlicher Negationsanzahl
|
| 2c) |
Pj+1
:= {µ Qj+1 | Ex. keine Verkürzung von µ in Qj
}
d.h. Literale, die beim Vergleich keinen Partner gefunden haben
|
| 2d) |
PI (f)
:= PI (f)  Pj+1
|
Also: Bestimmung aller Primimplikanten.
Kostenminimale Auswahl von Primimplikanten durch Matrixverfahren (s.u.).
Aufwand
O (3n • n2)
worst case; n Variable, ca. (3n ÷ n) Primimplikanten.
vgl. auch R. Klar, "Digitale Rechenautomaten"
|
| Matrixverfahren |
f: B4 B in DNF mit
Kosten: K (fDNF) = n k – 1
= 4•7 – 1 = 27
- Gruppiere nach Anzahl der negativen Literale:
| Anzahl Negationen |
Literale |
Einschlägiger Index i |
i dezimal geschrieben |
| 1 |
|
1 0 1 1
1 1 0 1
1 1 1 0
|
11
13
14 |
| 2 |
|
0 1 1 0
1 1 0 0
|
6
12 |
| 3 |
|
0 1 0 0 |
4 |
| 4 |
|
0 0 0 0 |
0 |
Resolution für Terme in benachbarten Gruppen:
| Anzahl Negationen |
Literale |
Minterm-Nummern |
| 1 |
|
11 |
| 1 |
|
6, 14
12, 13
12, 14 |
| 2 |
|
4, 6
4, 12 |
| 3 |
|
0, 4 |
Erste Tabellenzeile: P4
Restliche Zeilen: Q3
| Anzahl Negationen |
Literale |
Minterm-Nummern |
| 1 |
|
11
12, 13 |
| 2 |
|
4, 6 |
| 3 |
|
0, 4 |
1. Literal: P4
2. Literal: P3
3. Literal: Q2 = P2
4. Literal: P1
4 Primimplikanten.
f
= x1 ¬x2 x3 x4 + x1 ;x2 ¬x3 + x2 ¬x4 + ¬x1 ¬x3 ¬x4
Also Anzahl der Terme: k = 4
Kosten: K (f)
= (k – 1) + 3 + 2 + 1 + 2
= (4 – 1) + 8
= 3 + 8
= 11
Das folgende System ist minimal:
| i |
Minterme |
|
| 0 |
4 |
6 |
11 |
12 |
13 |
14 |
x1 ¬x2 x3 x4
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
}
}
}
}
PI
}
}
}
|
x1 x2 ¬x3
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
x2 ¬x4
|
0 |
1 |
1 |
0 |
10 |
0 |
1 |
|
¬x1 ¬x3 ¬x4
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
Beachte: (Mindestens) eine 1 in jeder Spalte.
Aufwand von Schritt (2)
Problem der minimalen Überdeckung
(Stichwort Überdeckungsmatrix) ist NP-vollständig und
sehr zeitaufwendig!
|
zurück zur Übersicht
Teil I
Teil II
