Don't-Care-Bedingungen in Karnaugh-Karten

Kurz gesagt: Ein Don’t-Care ist die Erlaubnis, einen Ausgangswert dort zu wählen, wo der Systemvertrag ihn nicht festlegt. Beziehen Sie in einer K-Karte X-Zellen nur ein, wenn sie eine nützliche Gruppe vergrößern; decken Sie bei SOP niemals eine erforderliche Null und bei POS niemals eine erforderliche Eins ab. Die Optimierung ist nur gültig, wenn die Annahme über die Care-Menge am Einsatzort stimmt. Ein HDL-X, ein unbekannter Simulationswert und ein Synthese-Don’t-Care sind nicht automatisch dasselbe.

Bei der Logikminimierung wird eine Funktion normalerweise für jeden möglichen Eingang erhalten. Don’t-Care-Bedingungen lockern diese Anforderung: Ausgewählte Eingangs-/Ausgangsfälle dürfen entweder 0 oder 1 zugewiesen bekommen, sodass eine kleinere Implementierung für die tatsächlich relevanten Fälle möglich wird.

Diese Freiheit kann Literale und Gatter einsparen. Sie kann aber auch die Wiederherstellung nach einem Reset entfernen, ein ungültiges Anzeigemuster sichtbar machen oder bei einer falschen Annahme eine Abweichung zwischen Simulation und Silizium erzeugen. Ein professionelles Design dokumentiert drei Dinge gemeinsam:

1. die erforderliche On-Menge, in der der Ausgang 1 sein muss;
2. die erforderliche Off-Menge, in der der Ausgang 0 sein muss;
3. die Don’t-Care-Menge, in der jedes Ergebnis den Systemvertrag erfüllt.

Zwei Gründe für einen unbestimmten Ausgang

1. Der Eingang ist unerreichbar

Die Umgebung garantiert, dass ein bestimmter Eingangsvektor zu einem relevanten Beobachtungszeitpunkt diese Logik nicht erreichen kann.

Eine gültige BCD-Ziffer liegt in der Menge 0–9; 10–15 können unerreichbar sein, wenn:

• die Quelle stets gültige BCD-Werte erzeugt;
• Reset und Einschalten keinen anderen Wert sichtbar machen können;
• Zwischenübergänge nicht als Ziffern abgetastet werden;
• Fehler, die den Code verfälschen, außerhalb des erforderlichen Fehlermodells liegen.

„Der Algorithmus fragt nie nach 12“ reicht nicht, wenn ein Vierbitbus beim Wechsel zwischen zwei gültigen registrierten Werten kurz 1100 annehmen kann.

2. Der Eingang kann vorkommen, aber dieser Ausgang wird nicht beobachtet

Eine Pipeline-Stufe kann beliebige Daten führen, während valid=0 ist. Wenn jeder Verbraucher die Daten mit demselben Valid-Zustand qualifiziert, ist der Datenausgang während ungültiger Zyklen irrelevant.

Das ist eine Beobachtbarkeitsbedingung und kein unerreichbarer Eingang. Sie bleibt nur so lange sicher, wie kein Verbraucher das nominell irrelevante Feld protokolliert, vergleicht, weiterleitet oder anderweitig verwendet.

Beide Fälle werden in einem zweiwertigen Minimierungsproblem zu X-Zellen. Ihre Beweise sind verschieden; bewahren Sie den Grund in der Spezifikation.

X bedeutet nicht immer dasselbe

Das Symbol X ist überladen:

• Auf einer K-Karte bedeutet X: „Die Implementierung darf 0 oder 1 wählen.“
• In einer HDL-Simulation mit vier Zuständen bedeutet X häufig „unbekannt, konfliktbehaftet oder nicht initialisiert“.
• In einem Wahrheitstabellendokument kann X bedeuten, dass ein Eingangswert für diese Zeile irrelevant ist.
• In einer Syntheseanweisung kann ein werkzeugspezifisches Konstrukt eine Optimierung erlauben.

Diese Bedeutungen sind nicht austauschbar.

Die Zuweisung von 'x in RTL kann in manchen Flows die Optimierung verbessern, in der Simulation Unbekanntheiten weitergeben, in einem anderen Flow ignoriert oder umgewandelt werden und einen echten Initialisierungsfehler verschleiern. Eine unvollständige kombinatorische Zuweisung kann statt eines Don’t-Cares ein Latch ableiten. Tool-Anweisungen wie full_case können ebenfalls dazu führen, dass sich das Syntheseverhalten von der Simulation unterscheidet; die Dokumentation von Intel warnt ausdrücklich vor dieser Möglichkeit.

Drücken Sie die Absicht so aus, wie es Zielsprache, Simulator, Synthesewerkzeug, Lint-Regeln und formaler Flow unterstützen. Verifizieren Sie anschließend das synthetisierte Ergebnis unter denselben Umgebungsannahmen.

Regeln für K-Karten

Für eine minimierte Summe von Produkten:

1. Tragen Sie jede Zelle als erforderliche 0, erforderliche 1 oder X ein.
2. Bilden Sie Rechtecke mit Zweierpotenzgröße, die nur 1en und X enthalten.
3. Decken Sie jede erforderliche 1 ab.
4. Nehmen Sie niemals eine erforderliche 0 auf.
5. Lassen Sie ein X ungenutzt, wenn es die Überdeckung nicht verbessert.
6. Wählen Sie eine Überdeckung anhand des tatsächlichen Kostenziels: Literale, Zellen, Tiefe, gemeinsam genutzte Terme oder ein anderes Implementierungsmaß.

Für das Produkt von Summen gilt der Dual:

• Gruppieren Sie erforderliche 0en mit optionalen Xen.
• Decken Sie jede erforderliche 0 ab.
• Nehmen Sie niemals eine erforderliche 1 auf.

Jeder Ausgang darf ein X unterschiedlich nutzen. Eine Segmentfunktion kann eine ungültige BCD-Zelle als 1 wählen, während eine andere sie als 0 wählt. Es besteht keine Anforderung, einem ungültigen Muster global einen Wert zuzuweisen, sofern die Schnittstellenspezifikation dies nicht verlangt.

Durchgerechnetes Beispiel: Eine gültige BCD-Ziffer ist mindestens 5

Sei A das höchstwertige BCD-Bit und D das LSB. Das erforderliche Verhalten lautet:

• F=0 für die Ziffern 0–4;
• F=1 für die Ziffern 5–9;
• X für die Codes 10–15.

In der Gray-Code-Reihenfolge für Zeilen und Spalten:

              CD
           00  01  11  10
AB = 00     0   0   0   0
AB = 01     0   1   1   1
AB = 11     X   X   X   X
AB = 10     1   1   X   X

Die X-Zellen ermöglichen drei nützliche Gruppen:

• Beide Zeilen mit A=1 bilden ein Oktett und ergeben A.
• 0110, 0111, 1110 und 1111 ergeben BC.
• 0101, 0111, 1101 und 1111 ergeben BD.

Daher gilt:

oder faktorisiert:

Prüfen Sie die Care-Menge:

• Die Ziffern 0–4 erzeugen 0.
• Die Ziffern 5–7 erfüllen $B(C+D)$.
• Die Ziffern 8–9 erfüllen A.

Der Ausdruck erzeugt zufällig für jeden ungültigen Code 10–15 eine 1. Das ist nur deshalb zulässig, weil diese Zeilen ausdrücklich unbestimmt waren.

Wenn ungültige Codes 0 erzeugen müssen

Dann sind sie keine Don’t-Cares mehr. Mit F=0 für 10–15 ist eine gültige SOP:

Diese Version erhält die erforderliche Null für ungültige Codes. Sie ist größer, weil der Schnittstellenvertrag stärker ist.

Ein Fall, in dem Don’t-Cares nicht helfen

Für eine gültige BCD-Ziffer lautet „gerade sein“:

Das LSB kodiert die Parität bereits. Das Zulassen von X für die Codes 10–15 kann das einzige Literal nicht entfernen, ohne erforderliche Werte zu verändern; das Minimum bleibt gleich.

Don’t-Cares vergrößern den Optimierungsraum, garantieren aber keine Verbesserung.

Ein Fall, in dem ein Literal verschwindet

Definieren wir F=1 für die gültigen BCD-Ziffern 8 und 9 und F=0 für die gültigen Ziffern 0–7.

Wenn ungültige Codes 10–15 ebenfalls 0 erzeugen müssen:

Nur 1000 und 1001 erfüllen den Ausdruck.

Wenn 10–15 Don’t-Cares sind, können die erforderlichen Einsen mit allen sechs X-Zellen gruppiert werden:

Beide Implementierungen stimmen für gültige BCD-Werte überein. Bei einigen ungültigen Eingängen unterscheiden sie sich absichtlich.

Dieser korrekte Vergleich ist wichtig: Ein Design kann nicht behaupten, „ohne Don’t-Cares“ zu arbeiten, während es stillschweigend ungültige Zellen zur Vergrößerung einer Gruppe nutzt.

Transiente Eingänge und Abtastgrenzen

Selbst wenn Quell- und Zielregister gültige Codes enthalten, wechseln kombinatorische Bits nicht gleichzeitig. Ein Übergang von BCD 7 (0111) nach 8 (1000) ändert vier Bits und kann durch andere elektrische Kombinationen laufen.

Ob das relevant ist, hängt von der Grenze ab:

• Ein Zielregister, das erst nach dem Einschwingen des Decoders abtastet, erfasst das Zwischenergebnis möglicherweise nie.
• Ein asynchrones Output-Enable, ein Schreib-Strobe oder ein aus der minimierten Logik abgeleiteter Takt kann auf einen transienten Wert reagieren.
• Eine Multiplexanzeige kann kurz ein Geistermuster zeigen.
• Ein Logikanalysator kann Werte zeigen, die Software niemals beobachtet.

Der Beweis für die Unerreichbarkeit muss daher festhalten, wann der Ausgang relevant ist, nicht nur, welche stabilen Werte die Software beabsichtigt.

Das Registrieren von Eingängen oder Ausgängen, das Einschränken des Timings, hazard-freie Steuerungslogik oder eine Ausblendung können die Annahme wahr machen. Ein X in einer K-Karte tut das nicht.

Ungültige Zustände in Zustandsautomaten

Angenommen, fünf Zustände sind mit drei Bits kodiert. Drei Codes werden im Normalbetrieb nicht verwendet. Die Optimierung der Next-State- und Ausgangslogik mit diesen Codes als Don’t-Cares kann sinnvoll sein, wenn Reset garantiert ist und Zustandsverfälschung außerhalb des Umfangs liegt.

Wenn Single-Event-Upset, CDC-Fehler, partieller Reset oder Fehlerinjektion berücksichtigt werden, sind diese Codes nicht irrelevant. Das Design muss möglicherweise:

• einen illegalen Zustand erkennen;
• gefährliche Ausgänge sofort unterdrücken;
• zum Reset oder einem anderen sicheren Zustand zurückkehren;
• den Fehler melden;
• eine Kodierung mit vorgeschriebenem Hamming-Abstand verwenden.

FPGA-Werkzeuge bieten explizite Mechanismen für sichere Zustände. AMD Vivados FSM_SAFE_STATE fügt beispielsweise Erkennung und Wiederherstellung ungültiger Zustände hinzu, mit einem Kompromiss zwischen Fläche und Leistung. Auch die Quartus-Dokumentation von Intel unterscheidet gewöhnliche Synthese von Optionen für sichere Zustandsautomaten.

Optimieren Sie illegale Zustände nicht weg und behaupten Sie gleichzeitig eine garantierte Wiederherstellung daraus. Das sind unterschiedliche Spezifikationen.

One-Hot- und Prioritätseingänge

Eine exakt One-Hot-kodierte $n$-Bit-Schnittstelle hat n gültige Vektoren und $2^n-n$ weitere Vektoren. Der Nullvektor ist ebenfalls gültig, wenn das Protokoll One-Hot-oder-Null lautet.

Ein normaler Encoder kann mehrere gesetzte Bits als Don’t-Cares behandeln, wenn die vorgelagerte Logik einen exakt One-Hot-kodierten Eingang garantiert. Ein Priority-Encoder definiert die Many-Hot-Zeilen absichtlich und kann sie daher nicht als unbestimmt behandeln. Er kann den Code dennoch als irrelevant definieren, wenn keine Anfrage aktiv ist und ein gültiger Ausgang den Code qualifiziert.

Diese Unterscheidung ist ein Grund dafür, Eingangsannahmen an Modulgrenzen zu dokumentieren, statt sie aus einem Namen wie „Encoder“ abzuleiten.

Daten mit irrelevantem Ausgang

Betrachten Sie:

valid = 0
data  = anything

Abhängige Logik, die von Daten abhängt, darf nur dann sicher optimiert werden, wenn jede beobachtbare Wirkung gegated ist:

write_enable = valid AND condition(data)

Doch selbst hier kann das physische Schalten von condition(data) Leistung verbrauchen, Seitenkanäle erzeugen oder das Timing beeinflussen. „Funktional unbeobachtet“ bedeutet nicht unbedingt „elektrisch irrelevant“.

Für klare Simulation weisen viele Teams ungültigen Daten weiterhin einen deterministischen Wert zu und lassen die Synthese durch explizite Constraints oder umgebende Enables optimieren. Die beste Wahl hängt vom Verifikations- und Implementierungs-Flow ab.

Hinweise zu HDL

Vermeiden Sie es, die K-Map-Notation direkt in beiläufige HDL-X-Zuweisungen zu übersetzen.

Ein konservatives kombinatorisches Muster definiert jeden Ausgang:

always_comb begin
  valid = (bcd <= 4'd9);
  ge_five = 1'b0;
  if (valid)
    ge_five = (bcd >= 4'd5);
end

Dies legt das Verhalten ungültiger Eingänge als Null fest. Wenn das Projekt ungültige Eingänge als Don’t-Cares für die Synthese behandeln möchte, kodieren Sie diese Absicht mit einem geprüften, vom Werkzeug unterstützten Mechanismus und einer zugehörigen Annahme. Beispiele können formale Eingangsbeschränkungen, Syntheseattribute, eingeschränkte Modulschnittstellen oder eine technologiespezifische Primitive sein.

Unabhängig von der gewählten Methode:

• auf unvollständige Zuweisungen und unbeabsichtigte Latches linten;
• RTL- und Gate-Level-Verhalten vergleichen, wenn der Flow dies verlangt;
• Äquivalenz auf der Care-Menge beweisen;
• prüfen, dass Umgebungsannahmen gelten;
• Warnungen zu unerreichbaren Zuständen und Case-Abdeckung untersuchen;
• casex oder Wildcard-Matching vermeiden, das unbekannte Steuerbits verbergen kann, sofern dieses Verhalten nicht ausdrücklich beabsichtigt ist.

Verifikationsplan

Eine Don’t-Care-Optimierung benötigt zwei komplementäre Prüfungen.

Funktionale Äquivalenz auf der Care-Menge

Für jeden erforderlichen Eingang gilt:

Bei vier Variablen können Sie die vollständige Wahrheitstabelle aufzählen. Verwenden Sie bei größerer Logik Assertions oder formale Äquivalenz mit einer ausdrücklichen Einschränkung der Care-Menge.

Validierung der Annahme

Beweisen oder testen Sie, dass:

• ungültige Kodierungen nicht abgetastet werden können, wenn der Ausgang relevant ist;
• Reset und Einschalten die Annahme einhalten;
• CDC-Pfade keine nicht unterstützten Kombinationen erzeugen können;
• die Fehleranforderungen die „unerreichbare“ Menge nicht einschließen;
• die gültige Gattersteuerung jede Nebenwirkung abdeckt;
• Test- und Debug-Modi den Qualifizierer nicht umgehen.

Nur die minimierte Boolesche Gleichung zu testen, verifiziert die falsche Hälfte des Vertrags, wenn die Umgebung das X erst zulässig macht.

Das BCD-Beispiel in DigiSim bauen

Konstruieren Sie zwei Detektoren für „Ziffer mindestens 5“:

1. Version mit definiert ungültigem Verhalten: Implementieren Sie $F=\overline A BC+\overline A BD+A\overline B\overline C$.
2. Don’t-Care-optimierte Version: Implementieren Sie $F=A+BC+BD$.
3. Durchlaufen Sie alle sechzehn Eingänge.
4. Bestätigen Sie, dass beide für 0–9 übereinstimmen.
5. Dokumentieren Sie ihre absichtlichen Unterschiede für 10–15.
6. Ergänzen Sie valid = NOT(A AND (B OR C)) für BCD 0–9 und gaten Sie einen beobachtbaren Ausgang damit.
7. Ändern Sie mehrere Eingangsbits gemeinsam und prüfen Sie, ob der Simulator Zwischenübergänge modelliert; leiten Sie kein analoges Hazard-Verhalten ab, wenn er ideale gleichzeitige Aktualisierungen verwendet.

Die Übung zeigt den richtigen Tausch: kleinere Logik gegen ein engeres Verhaltensversprechen.

Checkliste zur Prüfung

Fragen Sie sich vor jeder X-Zelle:

• Warum ist dieser Ausgang unbestimmt: unerreichbarer Eingang oder unbeobachteter Ausgang?
• An welcher Abtast- oder Beobachtungsgrenze gilt diese Aussage?
• Verletzen Reset, CDC, Testmodus oder Fehlerverhalten sie?
• Ist X eine K-Map-Erlaubnis, ein HDL-Unbekannt oder eine Werkzeuganweisung?
• Müssen illegale Zustände wiederhergestellt werden?
• Ist die optimierte Implementierung für jeden Eingang der Care-Menge verifiziert?
• Ist die Annahme selbst als Assertion festgehalten oder bewiesen?

Don’t-Cares sind keine „kostenlosen Gatter“. Sie tauschen Verhalten außerhalb einer definierten Care-Menge gegen Implementierungsfreiheit. Wenn die Care-Menge explizit und verifiziert ist, handelt es sich um disziplinierte Optimierung. Wenn sie nur angenommen wird, ist es verborgene Funktionalität.

Lesen Sie weiter in den BCD-Grundlagen zum Kodiervertrag, im Artikel zum BCD-zu-7-Segment-Decoder zu einer Anwendung mit sieben Ausgängen und bei statischen und dynamischen Hazards zum Verhalten während Übergängen.

Referenzen

• AMD-Vivado-Synthese: FSM_SAFE_STATE
• Intel Quartus: HDL-Richtlinien für Zustandsautomaten
• Intel Quartus: full_case-Syntheseattribut und Warnung vor Simulationsabweichung