loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication
February 1991 (vol. 40 no. 2)
pp. 205-213
ASCII Text
x 
 
R.E. Bryant, "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication," IEEE Transactions on Computers, vol. 40, no. 2, pp. 205-213, February, 1991.
 
 
BibTex
x
 
@article{ 10.1109/12.73590,
author = {R.E. Bryant},
title = {On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication},
journal ={IEEE Transactions on Computers},
volume = {40},
number = {2},
issn = {0018-9340},
year = {1991},
pages = {205-213},
doi = {http://doi.ieeecomputersociety.org/10.1109/12.73590},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication
IS - 2
SN - 0018-9340
SP205
EP213
EPD - 205-213
A1 - R.E. Bryant,
PY - 1991
KW - lower bounds; complexity; VLSI implementations; graph representations; Boolean functions; integer multiplication; abstraction; chip area; speed; ordered binary decision diagram; data structure; symbolically representing; area-time complexity; integer multiplier; Boolean functions; computational complexity; data structures; digital arithmetic; VLSI.
VL - 40
JA - IEEE Transactions on Computers
ER -
 

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 1>or=i>or=n, the following lower bounds are proved: any VLSI implementation must have AT/sup 2/= Omega (i/sup 2/) and any OBDD representation must have Omega (1.09/sup i/) vertices.

[1] H. Abelson and P. Andreae, "Information transfer and area-time trade-offs for VLSI multiplication,"Commun. ACM, vol. 23, no. 1, pp. 20-23, Jan. 1980.[2] S. B. Akers, "Binary decision diagrams,"IEEE Trans. Comput., vol. C-27, no. 6, pp. 509-516, Aug. 1978.[3] R. P. Brent and H. T. Kung, "The area-time complexity of binary multiplication,"J. ACM, vol. 28, no. 3, pp. 521-534, 1981.[4] R. E. Bryant, "Graph-based algorithms for Boolean function manipulation,"IEEE Trans. Comput., vol. C-35, no. 8, pp. 677-691, Aug. 1986.[5] M. Fujita, H. Fujisawa, and N. Kawato, "Evaluations and improvements of a Boolean comparison program based on binary decision diagrams," inProc. Int. Conf. Comput.-Aided Design, 1988, pp. 2-5.[6] D. E. Knuth,The Art of Computer Programming, Vol. 1. Reading, MA: Addison-Wesley, 1973.[7] R. J. Lipton and R. Sedgewick, "Lower bounds for VLSI," inProc. Thirteenth Annu. ACM Symp. Theory Comput., 1981, pp. 300-307.[8] S. Malik, A. Wang, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Logic verification using binary decision diagrams in a logic synthesis environment," inProc. Int. Conf. Comput.-Aided Design, 1988, pp. 6-9.[9] J. E. Savage, "Planar circuit complexity and the performance of VLSI algorithms," inVLSI Systems and Computation, Kung, Sproull, and Steele, Eds. Rockville, MD: Computer Science Press, 1981, pp. 61-68.[10] C. E. Shannon, "The synthesis of two-terminal switching circuits,"Bell Syst. Tech. J., vol. 28, pp. 59-98, Jan. 1949.[11] C. D. Thompson, "Area-time complexity for VLSI," inProc. Eleventh Annu. ACM Symp. Theory Comput., 1979, pp. 81-88.[12] J. D. Ullman,Computational Aspects of VLSI. Rockville, MD: Computer Science Press, 1983.[13] I. Wegener, "On the complexity of branching programs and decision trees for clique functions,"J. ACM, vol. 35. no. 2, pp. 461-471, Apr. 1988.[14] A. C. Yao, "Some complexity questions related to distributive computing," inProc. Eleventh Annu. ACM Symp. Theory Comput., 1979, pp. 209-213.

Index Terms:
lower bounds; complexity; VLSI implementations; graph representations; Boolean functions; integer multiplication; abstraction; chip area; speed; ordered binary decision diagram; data structure; symbolically representing; area-time complexity; integer multiplier; Boolean functions; computational complexity; data structures; digital arithmetic; VLSI.
Citation:
R.E. Bryant, "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication," IEEE Transactions on Computers, vol. 40, no. 2, pp. 205-213, Feb. 1991, doi:10.1109/12.73590
Usage of this product signifies your acceptance of the Terms of Use.