Tarea 4 - BDD y ROBDD

Introducción

Primero que nada veamos unas definiciones de la semana correspondiente donde se habló en clase sobre los diagramas binarios de decisión BDD, donde aprendimos que en si estos diagramas son representaciones de expresiones booleanas. Las características principales de estos diagramas son:

Poseen nodos de decisión, y dos nodos finales 0,1.

Cada nodo es una variable y deben de ir ordenadas.

Cada nodo tiene dos hijos, hijo menor e hijo mayor.

Las aristas que unen los nodos tienen una asignación de valor 0 y 1 que representan falso y verdadero respectivamente.

Y aprendimos como se hace a partir de un BDD obtener un ROBDD.

Se refiere a la reducción del diagrama a partir de ciertas reglas:

Los términos que sean iguales se pueden unir y eliminar.

Se comienza de abajo hacia arriba.

Acomodo de variables puede afectar en la reducción total.

Aplicaciones de los ROBDD.

Son muy utilizados para sintetizar circuitos gracias a la lógica que poseen y a la verificación formal que aquí aplicaría del porque lo vemos en este curso.

Otras aplicaciones serian el análisis de fallos en árbol, razonamiento bayesiano y recuperación de información privada. [2]

Aqui un video de Stanford Center for Professional Development del profesor Donald Knuth  de la universidad de Stanford hablando sobre arboles BDD.

Tarea

Para esta cuarta tarea teníamos que primeramente inventar una expresión booleana que a su  vez debería de contener 3 variables y 4 conectivos básicos como mínimo, todo esto con la ayuda de la explicación en clase y observando el ejemplo dado en el pdf [1].

Y aquí está mi expresión que invente, que tiene 4 variables y 4 conectivos:

Después obtuve la tabla de verdad de esta expresión de acuerdo a las reglas de la lógica expresadas en el pdf que se vio en clase.

Imagen de [1]

Después obtenemos esta tabla de verdad:

x1	y1	x2	y2	f
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Posteriormente en base a la tabla de verdad obtenida se dibujaba su BDD (Binary Decision Diagram). En este diagrama en forma de árbol podemos ver la combinación de cada una de las variables y al final su resultado.

La línea punteada representa cuando es falso (0), y la línea continua representa verdadero (1).

Diagrama binario

Por ultimo teníamos que hacer su ROBDD (Reduced Ordered Binary Decision

Diagram) y aquí muestro los pasos de como se fue reduciendo el árbol para llegar a su mínima expresión.

Comenzando de abajo para arriba vamos uniendo los que son iguales, primero y2 conectando a cada uno solamente 2 salidas 0 y 1.

Siguiendo con las x2 más arriba se va reduciendo cada vez más los nodos y flechas del diagrama.

Por ultimo, esta es la expresión con su máxima reducción posible.

Podemos observar que inicialmente se tenían 15 nodos y con la reducción fue posible llegar a tener 5 nodos para las dos salidas 0 y 1.

Bibliografía:

[1] http://itu.dk/courses/AVA/E2005/bdd-eap.pdf
[2] http://en.wikipedia.org/wiki/Binary_decision_diagram