Minimierungsverfahren nach Quine McCluskey

Ausgangspunkt:

Belegungsindexmengen

Idee:

 

• Benachbarte Belegungen unterscheiden sich in der Anzahl der mit 1 belegten Bits um genau 1 Indexgruppenbildung
• Die Differenz der Indizes benachbarter Belegungen ist eine Potenz von 2 systematische Differenzbildung zwischen Elementen zweier benachbarter Indexgruppen

Verfahren:

 

1. Aufstellen der Indexgruppen als 1. Kürzungstabelle enthält genau j 1-Belegungen; }
2. Differenzbildung in der 1. Kürzungstabelle zwischen allen Indizes k und l    (mit   )
   • Eintragen von k,l und der Differenz in die Indexgruppe der 2. Kürzungstabelle und markieren der Belegungen k und l in der 1. Kürzungstabelle
   • ignorieren
3. Differenzbildung in der 2. Kürzungstabelle zwischen Indizes k,l aus der Indexgruppe und r,s aus mit gleicher Differenz bei den bisherigen Kürzungen
   • Eintragen von k,l,r,s und der beiden Differenzen in einer weiteren Kürzungstabelle unter der Indexgruppe und markieren der Belegungen k,l und r,s
   • ignorieren
4. Wiederholung der Differenzbildung, bis keine weitere Kürzungstabelle mehr erzeugbar ist.
5. Die Elemente der letzten Kürzungstabelle sowie alle nicht markierten Indizes der übrigen Kürzungstabellen stehen jeweils für eine Menge nicht weiter kürzbarer Belegungen.
6. Eintragen von und der Elemente von in eine Auswahltabelle; Auswahl solcher , so das gilt.
7. Ermittlung der Primimplikanten aus
8. Aufstellen der expliziten BOOLEschen Gleichung entsprechend der Auswahl unter (6).

Beispiel:

5. Schritt: Ermittlung von aus den Kürzungstabellen

8. Schritt: Aufstellen der expliziten BOOLEschen Gleichung

mit

mit

Anmerkung: enthält die zur Minimierung benutzten Elemente aus