A Mesh-Connected Area-Time Optimal VLSI Multiplier of Large Integers
- 1 February 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (2) , 194-198
- https://doi.org/10.1109/tc.1983.1676203
Abstract
This paper describes a VLSI network for the multiplication of two N-bit integers, for very large N. The network, with its area 0(N) and operation time 0(√N), matches, within a constant factor, the known theoretical Ω(N2) lower bound to the area × (time)2measure of complexity in the VLSI model of computation. The network, which is based on the discrete Fourier transform, has an extremely regular mesh structure, and thus all wires have approximately the same length.Keywords
This publication has 7 references indexed in Scilit:
- The Area-Time Complexity of Binary MultiplicationJournal of the ACM, 1981
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- A combinatorial limit to the computing power of V.L.S.I. circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Information transfer and area-time tradeoffs for VLSI multiplicationCommunications of the ACM, 1980
- Greatest of the least primes in arithmetic progressions having a given modulusMathematics of Computation, 1979
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Schnelle Multiplikation großer ZahlenComputing, 1971