A Combinatorial Limit to the Computing Power of VLSI Circuits
Author:
- 1 March 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (3) , 294-300
Abstract
We introduce a property of Boolean functions, called transitivity which consists of integer, polynomial, and matrix products as well as of many interesting related computational problems. We show that the area of any circuit computing a transitive function grows quadratically with the circuit's maximum data rate, expressed in bits/S. This result provides a precise analytic expression of an area-time tradeoff for a wide class of VLSI circuits. Furthermore (as shown elsewhere), this tradeoff is achievable. We have thus matching (to within a constant multiplicative factor) upper and lower complexity bounds for the three above products, in the VLSI circuits computational model.Keywords
This publication has 5 references indexed in Scilit:
- Area-time optimal VLSI networks for multiplying matricesInformation Processing Letters, 1980
- Information transfer and area-time tradeoffs for VLSI multiplicationCommunications of the ACM, 1980
- The chip complexity of binary arithmetic1980
- Area-time complexity for VLSI1979
- On recognizing graph properties from adjacency matricesTheoretical Computer Science, 1976