Share Email Print

Proceedings Paper

An efficient structural technique for Boolean decomposition
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 30 June 2005
PDF: 6 pages
Proc. SPIE 5837, VLSI Circuits and Systems II, (30 June 2005); doi: 10.1117/12.608720
Show Author Affiliations
Andres Martinelli, Royal Institute of Technology (Sweden)
Elena Dubrova, Royal Institute of Technology (Sweden)

Published in SPIE Proceedings Vol. 5837:
VLSI Circuits and Systems II
Jose Fco. Lopez; Francisco V. Fernandez; Jose Maria Lopez-Villegas; Jose M. de la Rosa, Editor(s)

© SPIE. Terms of Use
Back to Top