Area-Time Complexity for VLSI

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 1/2 ) or T = θ (log N). A more general lower bound is also derived: AT x = Ω(N 1+x/2 ), for 0≤×≤2.

Authors

• Clark D. Thompson

Keywords

No keywords are indexed for this paper.