Quine-McCluskey Algorithmus

Heute, der QMC-Algorithmus. Ist mir mittlerweile schon ein paar Mal begegnet, nur vergesse ich immer Teile davon.
Mit der Quine-Mc-Cluskey Methode erhält man, anders wie mit KV-Diagrammen, die minimale Schaltfunktion, ausgehend von einer Wahrheitstabelle.

Über Google findet man meist Uniskripte, die nur so vor Formeln strotzen. Da schaffe ich jetzt Abhilfe.
Konkrete Anwendung, mit der interaktiven Realisierung von Uni Marburg.
Vorteil des QMC ist, dass ich eben wirklich die Minimalfunktion bekomme, ohne mich mit boolescher Algebra plagen zu müssen.
Nachteil, es ist ein ineffizienter Algorithmus, aber wer macht das auch schon von Hand?

Ausgangspunkt ist eine Wahrheitstabelle mit einem Ausgang und 2n Eingängen.
Um am Ende die Disjunktive Minimalform (DMF) zu erhalten, also eine Schaltfunktion, für den der Ausgang 1 ergibt, werden zuerst alle Zeilen der Wahrheitstabelle, die 1 oder x (don't care) ergeben, rausgeschrieben.
Das kann man auch irgendwie anders als Funktion aufschreiben.



Das wäre die 2. Tabelle von links (Implicants Order 0).

Vorneweg, die Hamming-Distanz
101 - 5
101 - 5
======== Distanz: 0
100 - 4
101 - 5
======== Distanz: 1
000 - 0
101 - 5
======== Distanz: 2

Bedeutet, die Anzahl Bits, in der sich zwei Zahlen unterscheiden.

Gesucht sind jetzt Zahlenpaare, die eine Hamming-Distanz von 1 haben.

Hier könnte man zuerst auch noch nach Anzahl Einsen gruppieren...

Jedes mit jedem kombinieren, ineffizient, führt aber zum Ziel.
Bei einer Hamming-Distanz von 1 bekommt das Paar einen Pfeil und wird in die nächste Wahrheitstabelle geschrieben. An der Stelle, an der sich die beiden Einträge unterscheiden, muss gekürzt werden (-).
Finden sich keine Kombinationen (mehr), Haken dran, fertig.
Eventuell gekürzten Stellen müssen sich beim nächsten Vergleich an der selben Stelle befinden, sonst kann das Kriterium mit der Hamming-Distanz = 1 nicht erfüllt werden.
Das wird so lange wiederholt, bis keine Kombinationen mehr möglich sind.

Mit den abgehakten Zeilen ließe sich schon eine DMF aufstellen, jedoch nicht minimiert.


Die Minimierung erfolgt folgendermaßen:


Die obere Tabelle. Sind links erst einmal die abgehakten Zeilen.
Darauf folgt für die Spalten, alle Zahlen (so eine unprofessionelle Ausdrucksweise, aber ich selbst möchte es in 1-2 Jahren ja auch noch verstehen 🙃) die in der Wahrheitstabelle 1 ergeben, don't care interessiert, wie der Name schon sagt, nicht mehr. (hier: 2, 9, 10, 11, 13).

Für im vorderen Teil enthaltenen Zahlenwerte (schwarz umkreist) wird ein Kreis in die entsprechende Spalte gesetzt.
Nachdem alle Zeilen ausgefüllt wurden, kann ich nun das Geheimnis der Minimierung lüften:

In jeder Spalte, in der es nur einen Punkt (in der Spalte, vertikal) gibt, wird der Punkt grün markiert. Das bezeichnet man als essentiellen Primimplikand. Bleiben wir bei Grün. Dieser muss zwingend in der endgültigen Schaltfunktion vorkommen.
Habe ich eine Zeile markiert (gelb), werden die Spalten, an denen es in meiner Zeile Kreise gibt, eliminiert (gelbe vertikale Linien).
Es werden immer zuerst die Zeilen mit grünem Punkt abgearbeitet!
Danach heißt es Raten und Ausprobieren?, welcher Ausdruck die meisten Spalten abdecken kann. (lila).

Anderes Beispiel

Angefangen mit der Markierung der Zeile(n) mit Primimplikand(en), hier in blau, sind die meisten Spalten schon mal gestrichen.
Daraufhin gehe ich die Zeilen durch, die, die die meisten Punkte in der Zeile hat, ist ein guter Kandidat, zum Markieren.

Abschließend dieses Monster hier:

Zusammengefasst noch einmal der Minimierungsvorgang:

  1. Spalten durchgehen, hat diese nur einen einzigen Punkt, diesen grün markieren
  2. Jede Zeile mit grünem Punkt markieren.
  3. In markierter Zeile, werden die Spalten, von Feldern, die einen Punkt enthalten, komplett durch markiert.

Dieses Schema wird danach einfach auf die am vielversprechendste Zeile angewandt, um so viel wie möglich streichen zu können.

Quellen:
http://users.encs.concordia.ca/~asim/coen312/Lectures/McClusky.pdf
http://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/
Youtube - Quine-McCluskey Method