DocumentCode
1147626
Title
Fourier Transforms in VLSI
Author
Thompson, Clark D.
Author_Institution
Division of Computer Science, University of California
Issue
11
fYear
1983
Firstpage
1047
Lastpage
1057
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.1983.1676155
Filename
1676155
Link To Document