Boolesche Algebra, Äquivalenzumformungen und Implementierungskosten

Äquivalente Ausdrücke liefern für alle Eingaben dieselben Ausgaben

Kombinatorische Logik zu vereinfachen bedeutet mehr, als eine Formel zu verkürzen. Bei gleicher Funktion sind Logikstufen, Fan-in, Fan-out und verfügbare Bibliothekszellen zu berücksichtigen. Zunächst lesen wir $+$ und Multiplikation in der booleschen Algebra^{iBoolesche Algebra Algebra mit 0,1, AND, OR und NOT. Das Pluszeichen bedeutet meist OR und folgt anderen Regeln als Ganzzahladdition.} als OR und AND.

Die zweite Gleichung lässt sich nach Fällen prüfen: Bei $A=1$ sind beide Seiten 1, bei $A=0$ sind beide $B$. Auch nach Anwendung einer gelernten Identität sollten Sie ihre Bedeutung erklären können.

NAND- und NOR-Strukturen mit De Morgan lesen

So ist $Y=AB+AC$ gleich $A(B+C)$. Die erste Form benötigt in einer direkten Zeichnung zwei ANDs und ein OR, die zweite ein OR und ein AND. Wegen unterschiedlicher Ankunftszeiten und Lasten ist eine Schaltung mit weniger Gattern jedoch nicht unbedingt schneller.

Auch der Konsenssatz ist nützlich:

Wenn $BC=1$ gilt, ist bei $A=0$ bereits $\overline A C=1$ und bei $A=1$ bereits $AB=1$. Der Term $BC$ ist deshalb für die stationäre Funktion redundant. Ihn zu entfernen kann allerdings Hazards während eines Übergangs verändern. Dies behandeln wir später bei Verzögerungen.

Jede Spalte steht für eine ABC-Eingangskombination, nicht für einen Zeitabschnitt. Prüfen Sie, ob beide Ausgänge in jeder Spalte gleich sind. Trotz anderer Gatterzahl und Pfade ist die Funktion für stabile 0/1-Eingänge identisch.

Maßstab für Äquivalenzprüfungen

Bezeichnen Sie die ursprüngliche und optimierte Variante als y_ref und y_opt und vergleichen Sie bei kleinen Eingaberäumen alle Kombinationen. Ein oder zwei bestandene Beispiele beweisen keine Äquivalenz.

assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

Für alle acht 0/1-Kombinationen muss mismatch stets 0 sein. Vierzustandssimulation mit X/Z und die Äquivalenz sequenzieller Schaltungen benötigen weitere Bedingungen. Den tatsächlich bewiesenen Geltungsbereich ausdrücklich anzugeben gehört zu einer soliden Entwurfsprüfung.