Publication Details
Title: On the Relation Between BDDs and FDDs
Author: B. Becker, R. Drechsler, and R. Werchner
Group: ICSI Technical Reports
Date: January 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-005.pdf
Overview:
Data structures for Boolean functions build an essential component of design automation tools, especially in the area of logic synthesis. The state of the art data-structure is the ordered binary decision diagram (OBDD), which results from general binary decision diagrams (BDDs), also called branching programs, by ordering restrictions. In the context of EXOR-based logic synthesis another type of decision diagram (DD), called (ordered) functional decision diagram ((O)FDD) becomes increasingly important. BDDs (FDDs) are directed acyclic graphs, where a Shannon decomposition (Reed-Muller decomposition) is carried out in each node. We study the relation between BDDs and FDDs. Both, BDDs and FDDs, result from DDs by defining the represented function in differing ways. If the underlying DD is complete, the relation between both types of interpretation can be described by a well-known Boolean transformation tau. This allows us to relate the OFDD-size of f and the OBDD-size of tau(f). We use this property to derive several results on the computational power of OFDDs and OBDDs. Symmetric functions are shown to have efficient representations as OBDDs and OFDDs as well. Classes of functions are given that have exponentially more concise OFDDs than OBDDs, and vice versa. In contrast to OBDDs, an exponential blow-up may occur in an AND-synthesis operation on two OFDDs. Finally, we demonstrate how the lower bound techniques for OBDDs can be adapted to OFDDs: We prove that the hidden weighted bit function and multiplication as well require OFDDs of exponential size independent of the ordering of the variables. Topics: Algorithms and data structures, complexity and computability, VLSI systems
Bibliographic Information:
ICSI Technical Report TR-94-005
Bibliographic Reference:
B. Becker, R. Drechsler, and R. Werchner. On the Relation Between BDDs and FDDs. ICSI Technical Report TR-94-005, January 1994
Author: B. Becker, R. Drechsler, and R. Werchner
Group: ICSI Technical Reports
Date: January 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-005.pdf
Overview:
Data structures for Boolean functions build an essential component of design automation tools, especially in the area of logic synthesis. The state of the art data-structure is the ordered binary decision diagram (OBDD), which results from general binary decision diagrams (BDDs), also called branching programs, by ordering restrictions. In the context of EXOR-based logic synthesis another type of decision diagram (DD), called (ordered) functional decision diagram ((O)FDD) becomes increasingly important. BDDs (FDDs) are directed acyclic graphs, where a Shannon decomposition (Reed-Muller decomposition) is carried out in each node. We study the relation between BDDs and FDDs. Both, BDDs and FDDs, result from DDs by defining the represented function in differing ways. If the underlying DD is complete, the relation between both types of interpretation can be described by a well-known Boolean transformation tau. This allows us to relate the OFDD-size of f and the OBDD-size of tau(f). We use this property to derive several results on the computational power of OFDDs and OBDDs. Symmetric functions are shown to have efficient representations as OBDDs and OFDDs as well. Classes of functions are given that have exponentially more concise OFDDs than OBDDs, and vice versa. In contrast to OBDDs, an exponential blow-up may occur in an AND-synthesis operation on two OFDDs. Finally, we demonstrate how the lower bound techniques for OBDDs can be adapted to OFDDs: We prove that the hidden weighted bit function and multiplication as well require OFDDs of exponential size independent of the ordering of the variables. Topics: Algorithms and data structures, complexity and computability, VLSI systems
Bibliographic Information:
ICSI Technical Report TR-94-005
Bibliographic Reference:
B. Becker, R. Drechsler, and R. Werchner. On the Relation Between BDDs and FDDs. ICSI Technical Report TR-94-005, January 1994