An efficient structural technique for boolean decomposition
2005 (English)In: VLSI Circuits and Systems II, Pts 1 and 2 / [ed] Lopez, JF; Fernandez, FV; LopezVillegas, JM; DelaRosa, JM, BELLINGHAM: SPIE-INT SOC OPTICAL ENGINEERING , 2005, Vol. 5837, 913-918 p.Conference paper (Refereed)
Boolean decomposition techniques offer a powerful alternative to traditional algebraic methods when partitioning a circuit graph in the technology independent stage of the circuit design flow. These techniques usually require to transform the circuit from a structural representation to a representation based on Binary Decision Diagrams (BDDs). It is well known that BDDs can grow exponentially in some cases, so the power of Boolean decomposition comes at the expense of an exponential increase in the size of the circuit representation. The following stages in the design flow may suffer severely from the space penalty imposed on each partitioned block. To cope with this space explosion, each block of the partitioned circuit has to be re-synthesized before further processing. The extra re-synthesis, on the other hand, may impose a prohibitive time/space penalty on the design flow. This paper proposes an inexpensive technique to avoid re-synthesizing the BDD blocks obtained after Boolean decomposition. This technique works by structurally partitioning the original circuit representation, according to information provided by the partitioned BDD blocks. After all the blocks have been recovered, the BDDs are not needed and can be discarded. The resulting circuit will be proportional to the original circuit representation, and not to the intermediate BDD representation.
Place, publisher, year, edition, pages
BELLINGHAM: SPIE-INT SOC OPTICAL ENGINEERING , 2005. Vol. 5837, 913-918 p.
, PROCEEDINGS OF THE SOCIETY OF PHOTO-OPTICAL INSTRUMENTATION ENGINEERS (SPIE), ISSN 0277-786X ; 5837
boolean decomposition, logic synthesis, binary decision diagram, circuit partitioning
Atom and Molecular Physics and Optics
IdentifiersURN: urn:nbn:se:kth:diva-43007DOI: 10.1117/12.608720ISI: 000231723000093ScopusID: 2-s2.0-28344439816ISBN: 0-8194-5832-5OAI: oai:DiVA.org:kth-43007DiVA: diva2:447732
Conference on VLSI Circuits and Systems II. Seville, SPAIN. MAY 09-11, 2005
QC 201110132011-10-132011-10-132012-11-01Bibliographically approved