binäres Entscheidungsdiagramm

Ein binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt. Ein BED kann als eine Art Flussdiagramm zur Auswertung einer Booleschen Funktion verstanden werden. Dabei wird nacheinander der Wert der Variablen , , ... abgefragt, mit den zwei Entscheidungsmöglichkeiten Wahr oder Falsch, welche jeweils in unterschiedliche Teilbereiche des Diagramms verzweigen. Als Ergebnis erhält man schließlich den Wert der Booleschen Funktion unter der gewählten Variablenbelegung. Die Darstellung des Diagramms ist dabei weitestgehend komprimiert, so dass für das Ergebnis irrelevante Fragen ausgelassen und doppelte Teildiagramme zusammengelegt werden.