A Caltech Library Service

Area-Time Complexity for VLSI

Thompson, C. D. (1979) Area-Time Complexity for VLSI. In: Proceedings of the Caltech Conference On Very Large Scale Integration. California Institute of Technology , Pasadena, CA, pp. 495-508.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT^2 > N^2/16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T = Θ(N^(l/2)) or T = Θ(log N).

Item Type:Book Section
Additional Information:This research is supported '" part by the NatiOnal Science Foundation under Grant MCS 75-222-55 and the Office of Naval Research under Contract N00014-76-C-03701 NR 044-422. C. D. Thompson is an NSF fellow. James B. Saxe formulated and proved equation 1. Leo J. Guibas and the XEROX Palo Alto Research Center gave guidance 1nd generous support during the early phases of the research that led to this paper.
Funding AgencyGrant Number
NSFMCS 75-222-55
Office of Naval ResearchN00014-76-C-0370
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Computer Science Technical Report3340
Record Number:CaltechCONF:20120504-143038397
Persistent URL:
Related URLs:
URLURL TypeDescription
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:180
Deposited By: Kristin Buxton
Deposited On:08 Aug 2012 21:49
Last Modified:03 Oct 2019 22:50

Repository Staff Only: item control page