Karnaugh-Diagramme und Bedingungen für Don’t-cares

Von der Wahrheitstabelle zu Implementierungskosten

Die Wahrheitstabelle^{iWahrheitstabelle Vollständige Liste aller Eingangskombinationen mit jeweiligem Ausgang. Zeitliche Änderungen werden gesondert im Zeitdiagramm geprüft. Mehr erfahren} legt die Funktion fest; die Logikminimierung entscheidet über ihren Ausdruck. Bei drei Eingängen sei die Mintermnummer die Binärzahl ABC mit A als höchstwertigem Bit.

Minterm 4 ist zum Beispiel ABC=100. Die nicht aufgeführten Zeilen 0, 2 und 6 liefern 0. Statt stets fünf Produktterme zu implementieren, können wir Terme zusammenfassen, die sich nur in einem Bit unterscheiden.

Ein Karnaugh-Diagramm ist eine umsortierte Wahrheitstabelle

Die Spalten stehen in der Reihenfolge BC=00, 01, 11, 10. Diese Gray-Code-Reihenfolge ändert zwischen Nachbarn genau ein Bit. Auch die äußerste linke und rechte Spalte sind benachbart.

Gruppen müssen Rechtecke aus $1,2,4,8,\ldots$ Zellen sein. Eine enthaltene Null würde die Funktion ändern. Dieselbe Eins darf mehreren Gruppen angehören.

1. Die vier Zellen der beiden C=1-Spalten bleiben 1, während A und B wechseln. Übrig bleibt C.
2. In der A=1-Zeile wechseln zwischen BC=00 und 01 nur die C-Werte. Übrig bleibt $A\overline B$.
3. Das OR beider Gruppen deckt alle Einsen ab und vermeidet alle Nullen.

Vergleichen Sie Original und minimierten Ausdruck bei allen acht Eingaben. Prüfen Sie getrennt, dass der Ausdruck kürzer geworden ist und dass die Funktion erhalten bleibt.

Der folgende Ablauf überträgt die beiden Gruppen in einen Ausdruck. In der C-Gruppe wechseln A und B, in der Zweiergruppe C; genau diese Variablen entfallen.

Don't-care ist Optimierungsfreiheit unter einer Eingangsannahme

Angenommen, der Systemvertrag schließt ABC=000 aus. Setzen wir diese Zelle auf X, darf sie je nach Bedarf als 0 oder 1 verwendet werden. Eine Vierergruppe mit B=0 ergibt einen einfacheren Ausdruck:

Der neue Ausdruck liefert für ABC=000 eine 1 und unterscheidet sich damit von der ursprünglichen vollständigen Wahrheitstabelle. Eine Aussage über Äquivalenz muss also die Bedingung ABC≠000 einschließen. Kann 000 bei Initialisierung oder Fehlerbehebung auftreten, verletzt diese Optimierung möglicherweise die Systemanforderungen.

Ein minimaler Ausdruck ist kein minimaler Chip

Weniger Literale garantieren in einer konkreten Standardzellbibliothek keine optimale Fläche, Verzögerung oder Leistung. Lasten, Fan-out, verfügbare komplexe Gatter, Verdrahtung und Glitches beeinflussen das Ergebnis. Hier sichern wir funktionale Äquivalenz und Eingangsannahmen ab; physische Kosten beurteilen wir anhand von Synthese- und Timing-Ergebnissen.

Weiterführend: MIT OpenCourseWare — Combinational Logic

Übung · Überlappende Gruppen und Don't-care-Bedingungen prüfen

1. Wählen Sie die C-Gruppe. Innerhalb der vier Zellen ändern sich A und B; nur C bleibt.
2. Wählen Sie A·¬B. Die Gruppe deckt m4 und m5 ab; m5 überschneidet sich mit C. Überlappung ist erlaubt, eine Null in der Gruppe nicht.
3. Klicken Sie zweimal auf m0: 0 → 1 → X. Mit X ist die Spezifikation unvollständig und enthält d(0). Die B=0-Gruppe wird größer; der Ausdruck lautet $C+\overline B$.
4. Klicken Sie erneut auf m0, um 0 wiederherzustellen. Mit der ursprünglichen Anforderung muss die größere Gruppe verschwinden.

Eine Gruppenauswahl ändert keinen Wert. Der vollständige Ausdruck deckt weiterhin alle Einsen ab; der Rahmen hebt nur den gerade betrachteten Term hervor. „Minimal“ bedeutet hier zuerst möglichst wenige Produktterme, danach möglichst wenige Literale; bei mehreren Lösungen wird eine angezeigt.