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. https://resolver.caltech.edu/CaltechCONF:20120504-143038397
![[img]](https://caltechconf.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 2MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechCONF:20120504-143038397
Abstract
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. | ||||||
| Funders: |
| ||||||
| Other Numbering System: |
| ||||||
| Record Number: | CaltechCONF:20120504-143038397 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechCONF:20120504-143038397 | ||||||
| Related URLs: |
| ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 180 | ||||||
| Collection: | CaltechCONF | ||||||
| Deposited By: | Kristin Buxton | ||||||
| Deposited On: | 08 Aug 2012 21:49 | ||||||
| Last Modified: | 03 Oct 2019 22:50 |
Repository Staff Only: item control page
