A combinatorial limit to the computing power of V.L.S.I. circuits
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 294-300
- https://doi.org/10.1109/sfcs.1980.1
Abstract
We introduce a property of boolean functions, called transitivity which holds 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 bit/second. This result provides a precise analytic expression of an area-time tradeoff for a wide class of V.L.S.I. circuits. Furthermore, (as shown elsewhere), this tradeoff is achievable. Thus we have matching (to within a constant multiplicative factor) upper and lower complexity bounds for the three above products, in the V.L.S.I. circuits computational model.Keywords
This publication has 5 references indexed in Scilit:
- Area—time tradeoffs for matrix multiplication and related problems in VLSI modelsJournal of Computer and System Sciences, 1981
- 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 arithmeticPublished by Association for Computing Machinery (ACM) ,1980
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979