Title :
Fourier Transforms in VLSI
Author :
Thompson, Clark D.
Author_Institution :
Division of Computer Science, University of California
Abstract :
This paper surveys nine designs for VLSI circuits that compute N-element Fourier transforms. The largest of the designs requires O(N2 log N) units of silicon area; it can start a new Fourier transform every O(log N) time units. The smallest designs have about 1/Nth of this throughput, but they require only 1/Nth as much area.
Keywords :
Algorithms implemented in hardware; FFT; Fourier transform; VLSI; area-time complexity; computational complexity; mesh-connected computers; parallel algorithms; shuffle-exchange network; Arithmetic; Delay; Flexible printed circuits; Fourier transforms; Integrated circuit interconnections; Parallel processing; Pins; Silicon; Throughput; Very large scale integration; Algorithms implemented in hardware; FFT; Fourier transform; VLSI; area-time complexity; computational complexity; mesh-connected computers; parallel algorithms; shuffle-exchange network;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1983.1676155
