Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
BDD/Bestimmung von Primimplikanten
Wie funktioniert das erstellen eines BDD/OBBD Diagramm genau?
Wie kann man aus einer Funktion die Primimplikanten/Primimplikate herauslesen ohne eines Symmetriediagrammes?
Wie kann man eine DNF/KNF erstellen ohne Freistellen? muss jeder Term etweder 1 oder 0 ergeben ?
Am Beispiel:
[m]f(x,y,z) = (NOT(x * y) + NOT(z))[/m]
Wir erstellen einen BDD. Dazu suchen wir uns, wenn nicht anders gegeben, eine Variablenordnung aus, wir nehmen hier: [m]z < x < y[/m].
Wir erstellen zuerst eine Entwicklung nach Shannon:
[m]f(x,y,z) = z * ( NOT(x * y) ) + NOT(z) * (1) = z * ( x * (NOT(y)) + NOT(x) * (1)) + NOT(z) * (1) = z * ( x * ( y * (0) + NOT(y) * (1) ) + NOT(x) * (1) ) + NOT(z) * (1)[/m]
Jetzt können wir direkt den BDD bauen. Für jede Stufe, sprich Schritt, erstellen wir einen Knoten mit der Variablen, nach welcher wir entwickelt haben, hier also zuerst z:
BDD – Schritt 1:
[m] (z)[/m]
Gehen wir nun den Schritt mit z * (…) hinab, so ist das eine 1-Kante und wird als solche explizit und eindeutig kenntlich gemacht, gehen wir den Schritt mit NOT(z) * (…) hinab, so ist das eine 0-Kante und wird als solche explizit und eindeutig kenntlich gemacht. Kommst du zu einer Konstanten (1 oder 0), so fügst du einen Knoten mit 1 oder 0 hinzu, bei diesem gibt es dann keine Kindknoten mehr.
weitere BDD-Schritte:
[m] (z)
1 / \ 0
/
(x) (1)
1 / \ 0
/
(y) (1)
1 / \ 0
/
(0) (1)[/m]
Jetzt kann man gleiche (isomorphe) Teilbäume noch zusammenfassen, in diesem Fall also die Konstanten. Es gibtsollte aber kein Problem geben, wenn du dies nicht machst, außer es ist ein reduzierter OBDD (ROBBD) gefordert.
EDIT: Für das direkte Ablesen macht man schlussendlich auch eine Entwicklung nach Shannon, dann bloß im Kopf statt wie hier explizit.
Dies haben wir in Übung 8 (Aufgaben 1 und 3) gemacht, hier gibt es sowohl das Nelson-, als auch das Quine/McCluskey-Verfahren.
Dies haben wir in Übung 6 (Aufgabe 2) gemacht. Du schaust dir dazu einfach alle Eins- oder Nullstellen an, je nachdem ob du eine DNF oder KNF haben möchtest. Um ehrlich zu sein, verstehe ich hierbei dein Problem nicht, da das erstmal gar nichts mit den Redundanzstellen zu tun hat. Diese spielen ja erst beim Minimieren eine wirkliche Rolle. Hast du nur Redundanzstellen und keine respektiven Eins- oder Nullstellen, so wäre die DNF 1 und KNF 0. Du brauchst also wirklich keine don’t care-Terme.
del
del