DIAGRAMMA DI DECISIONE BINARIA

You are viewing the theme
[Voti: 0    Media Voto: 0/5]

diagramma di decisione binaria (BDD per Binary decision Diagram in inglese), come una forma normale negata o un grafico orientato aciclico propositionnel, è una struttura di dati utilizzata per rappresentare funzioni booléennes. Una funzione booléenne può essere rappresentata da uno grafico orientato aciclico con una radice che consiste in nodi di decisioni, e due nodi terminali chiamati 0-terminale e 1-terminale. Ogni nodo di decisione è etichettato da una variabile booléenne ed ha due nodi fili, chiamati fili bassi e fili alti. Il bordo di un nodo a fili bassi (resp. su) rappresenta l’incarico della variabile a 0 (resp. 1). Tale BBD è chiamata “ordinata„ se tutte le variabili appaiono nello stesso ordine su tutti i cammini dalla radice verso i nodi terminali. È chiamato “ridotto„ se il grafico è ridotto secondo due norme:

– tutti i sotto-grafici isomorphes hanno una rappresentazione unica;
– tutti i nodi i cui due fili sono isomorphes sono eliminati.

Nel suo impiego corrente, il termine diagramma di decisione binaria si riferisce praticamente tutto il tempo ad un diagramma di decisione binaria ordinato ridotto (ROBDD per Reduced Ordered Binary decision Diagram). Il vantaggio di una ROBDD è che è canonico (unico) per una funzione booléenne data. Questa proprietà lo rende utile, ad esempio, per la verifica d’equivalenza funzionale (che si traduce con l’uguaglianza delle ROBDD associato, che può essere valutata in tempo costante).

Un cammino della radice al nodo 1-terminale rappresenta un incarico di variabile (parziale o non) per il quale la funzione booléenne rappresentata è vera. Quando il cammino scende da un nodo verso fili bassi (resp. fili alto), si influisce alla variabile rappresentata da questo nodo sul valore 0 (resp. 1).

I diagrammi di decisione binari sono molto utilizzati dai programmi di concezione assistita mediante elaboratore(Cad) per generare circuiti (sintesi logica), e nella verifica formale.

ARTICOLO WIKIPEDIA

Example

The left figure below shows a binary decision tree (the reduction rules are not applied), and a truth table, each representing the function f (x1, x2, x3). In the tree on the left, the value of the function can be determined for a given variable assignment by following a path down the graph to a terminal. In the figures below, dotted lines represent edges to a low child, while solid lines represent edges to a high child. Therefore, to find (x1=0, x2=1, x3=1), begin at x1, traverse down the dotted line to x2 (since x1 has an assignment to 0), then down two solid lines (since x2 and x3 each have an assignment to one). This leads to the terminal 1, which is the value of f (x1=0, x2=1, x3=1).

The binary decision tree of the left figure can be transformed into a binary decision diagram by maximally reducing it according to the two reduction rules. The resulting BDD is shown in the right figure.

Binary decision tree and truth table for the function f(x_1, x_2, x_3)=bar{x_1} bar{x_2} bar{x_3} + x_1 x_2 + x_2 x_3