On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- 1 February 1991
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (2) , 205-213
- https://doi.org/10.1109/12.73590
Abstract
Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity AT/sup 2/= Omega (n/sup 2/) also proves that any OBDD representation of the function has Omega (c/sup n/) vertices for some c>1 but that the converse is not true. An integer multiplier for word size n with outputs numbered 0 (least significant) through 2n-1 (most significant) is described. For the Boolean function representing either output i-1 or output 2n-i-1, where 1Keywords
This publication has 11 references indexed in Scilit:
- Logic verification using binary decision diagrams in a logic synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the complexity of branching programs and decision trees for clique functionsJournal of the ACM, 1988
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- The Area-Time Complexity of Binary MultiplicationJournal of the ACM, 1981
- Lower bounds for VLSIPublished by Association for Computing Machinery (ACM) ,1981
- Information transfer and area-time tradeoffs for VLSI multiplicationCommunications of the ACM, 1980
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Binary Decision DiagramsIEEE Transactions on Computers, 1978
- The Synthesis of Two-Terminal Switching CircuitsBell System Technical Journal, 1949