Reduced ordered binary decision diagram

Reduced ordered binary decision diagram

1. REDUCED ORDERED BINARY DECISION DIAGRAM (ROBDD) Devi Sivaraman 12ECP026 M.Tech-VLSI

2. Binary Decision Diagrams Boolean function of m variables defines a Boolean space of 2 m points The data structure to represent Boolean function should be compact and easy to manipulate A binary decision diagram (BDD) is a data structure that is used to represent a Boolean function, directly derivable from Shannon’s expansion

3. Shannon’s Expansion Shannon's expansion is a method by which a Boolean function can be represented by the sum of two sub-functions of the original For Example:

4. Binary Tree Representation 1 1 1 x y y

5. ROBDD Flow

6. Example 1: XOR Truth Table Binary Decision Tree A B F 1 1 1 1 1 1 A B B 1 1 1 1 1

7. Binary Decision Diagram

8. OBDD Ordered BDD (OBDD) : Input variables are ordered – each path from root to sink visits nodes with labels (variables) in ascending order . a c c b 1 ordered order = a,c,b a b c c 1 not ordered b

9. Ordered Binary Decision Tree (OBDT) This graph representation is called OBDT or OBDD (Ordered binary Decision Diagram) which has a directed tree structure Each vertex has two children. Two edges originated from a vertex are called high (positive co-factor) & low (negative co-factor)

10. OBDT to ROBDD ROBDD can be obtained from an OBDT (Ordered Binary Decision Tree) by repeatedly applying following reduction rules (until none of the them can be applied anymore): Remove duplicate terminal (leaf) nodes Remove duplicate non-terminal (internal) nodes Remove nodes with redundant tests

11. Reduction rules of OBDD Elimination rule Reduction Rule

12. OBDT to ROBDD Rule 1: Collapse Leaf Nodes to remove redundant tests It’s no longer a tree

13. OBDT to ROBDD Rule 2: Isomorphic sub-graphs

14. OBDT to ROBDD Final Representation

15. ROBDDs Directed acyclic graph (DAG) O ne root node per function, two terminals 0, 1 E ach node, two children, and a variable Shannon co-factoring tree, except reduced and ordered (ROBDD) Reduced : any node with two identical children is removed two nodes with isomorphic BDD’s are merged Ordered: Co-factoring variables (splitting variables) always follow the same order from a root to a terminal x i 1 < x i 2 < x i 3 < … < x i n BDDs 15

16. Example 2 Binary Decision Tree 16 a c b f a b b c c c c 1 1 1 1 1 1 1 1 1 1 1 Graph representation of a Boolean function. Leaf nodes

17. Ordered Binary Decision Diagram (OBDD) 17 a c b f a b b c c 1 1 1 1 1 1 1 1 a b b c c c c 1 1 1 1 1 1 1 1 1 1 1 Tree OBDD

18. OBDD With Different Input Ordering 18 a c b f a b b c c 1 1 1 1 1 1 1 1 c b b a 1 1 1 1 1 1 a 1 0 1

19. Reduction: OBDD to ROBDD 19 a c b f a b b c c 1 1 1 1 1 1 1 1 a 1 c c b b 1 1 1 1 1

20. Properties of ROBDD The 0- and 1-succesor of any node should not be identical ROBDDs provide canonical representation of switching functions ROBDDs can be manipulated efficiently ROBDDs representations are small for many important switching functions Isomorphic graph should not be there i.e. sub-graphs that yields same information about function several times

21. Thank You