Vier Slide-Kapitel (k610–k630), 0 Punkte in beiden Klausuren, 0 Übungsaufgaben. ABER: Der ITE-Operator aus k623 ist strukturell analog zum Fredkin-Gate (Klausuraufgabe A4c, 12 Punkte). Wer ITE versteht — if F then G else H — hat das mentale Modell für Fredkin: das Fredkin-Gate ist ein physikalisches ITE. Dies ist der einzige indirekte Pfad von diesem Topic in die Klausur.

Direkt: LOW — 0 Punkte in beiden Klausuren.

Indirekt: MITTEL — Der ITE-Operator aus k623-Binaere_Entscheidungsdiagramme_BDDs_ITE-Beispiel_Variablenordnung ist strukturell identisch mit dem Fredkin-Gate aus Klausuraufgabe A4c (12 Punkte). Das Fredkin-Gate ist ein controlled swap: wenn das Kontrollbit , werden die beiden Datenleitungen vertauscht — genau . Wer die ITE-Rekursion und die Shannon-Zerlegung verstanden hat, kann Fredkin ohne weitere Vorbereitung lösen.

Boolesche Ausdrücke sind induktiv definiert über Syntax (Konstanten , Variablen , Operationen ) und Semantik (Interpretationsfunktion ). Die Darstellung einer Booleschen Funktion als Ausdruck oder Schaltkreis ist nicht eindeutig — z. B. und sind äquivalent aber verschieden.

Eindeutige Darstellungen existieren (Funktionstabelle, KDNF), sind aber sperrig: Einträge für Variablen. Ziel: eindeutige und kompakte Darstellung → BDDs.

Siehe: k610-Boolesche_Ausdruecke_Wiederholung

Ein Binary Decision Diagram ist ein azyklischer gerichteter Graph mit:

Kompositionsregel (Semantik):

Ein BDD enthält dieselbe Information wie eine Funktionstabelle, aber kompakter.

Siehe: k621-Binaere_Entscheidungsdiagramme_BDDs_ROBDDs_kanonische_Darstellung

Ein Reduced Ordered BDD (ROBDD) ist ein BDD mit zwei zusätzlichen Eigenschaften:

Ab der Vorlesung wird "BDD" synonym für "ROBDD" verwendet.

Bedeutung: Zwei Funktionen und sind genau dann äquivalent, wenn ihre ROBDDs (bei gleicher Variablenordnung) identisch sind. Dies ermöglicht Äquivalenz-Checking in polynomieller Zeit (bezüglich BDD-Größe).

Für eine Boolesche Funktion und Variable :

Dabei sind und die Kofaktoren von nach :

Die Shannon-Zerlegung ist die Grundlage der BDD-Konstruktion: jeder innere Knoten berechnet die Zerlegung nach seiner Variablen, die Kinder sind die Kofaktor-BDDs.

Top-Down-Konstruktion: Zerlege rekursiv nach der Variablenordnung, bis nur noch Konstanten übrig bleiben.

Siehe: k622-Binaere_Entscheidungsdiagramme_BDDs_Konstruktion_von_BDDs

Bedeutung: If then else — der universelle Boolesche Operator.

Alle binären Operationen sind auf ITE zurückführbar:

Sei die oberste Variable in , , :

Terminalfälle:

Effizienz: Mit Computed Table (CT) für bereits berechnete ITE-Aufrufe und Unique Table (UT) für bereits existierende Knoten wird die Komplexität zu . Die UT garantiert, dass Ergebnisse bereits reduziert sind.

Das Fredkin-Gate mit Kontrollbit und Datenleitungen vertauscht und genau dann, wenn :

Wer die ITE-Definition und die Rekursionsstruktur verstanden hat, kann das Fredkin-Gate und seine Wahrheitstabelle direkt herleiten. Dies ist der Hauptgrund, k623 zu lesen.

Siehe: k623-Binaere_Entscheidungsdiagramme_BDDs_ITE-Beispiel_Variablenordnung

Die Größe eines BDDs hängt stark von der Variablenordnung ab.

Beispiel:

Vergleich von Spezifikation und Implementierung:

Fehlerdiagnose: Falls nicht äquivalent, berechne BDD für . Ein Pfad zum 1-Terminal liefert eine Belegung, bei der Implementierung und Spezifikation abweichen — dies lokalisiert den Entwurfsfehler.

Nachweis, dass eine Eigenschaft immer gilt. Beispiel aus der Vorlesung: Bus Contention auf ReTI-Bus — zeige, dass und nie gleichzeitig aktiv sind.

ü

Vorgehen: BDD für die OR-Verknüpfung beider Signale berechnen; muss aus einem einzigen 1-Terminal bestehen.

Schaltkreis wird Gatter für Gatter durch BDD-Operationen (AND, OR, XOR, NOT → alle via ITE) simuliert. Die BDDs repräsentieren alle möglichen Eingangsbelegungen gleichzeitig.

Siehe: k630-Anwendung_Formale_Verifikation

LOW für direkte Klausurrelevanz — 0 Punkte in beiden Klausuren.

ABER: k623-Binaere_Entscheidungsdiagramme_BDDs_ITE-Beispiel_Variablenordnung lesen für ITE → Fredkin (A4c, 12P). Die Definition und die Erkenntnis, dass Fredkin = physikalisches ITE, reicht. Rest nur bei Zeitüberschuss.