On the design of VLSI arrays for discrete Fourier transform
Authors:
- 1 January 1992
- journal article
- Published by Institution of Engineering and Technology (IET) in IEE Proceedings G Circuits, Devices and Systems
- Vol. 139 (4) , 541-552
Abstract
In this paper the design of VLSI arrays for discrete Fourier transform (DFT) is investigated through three topics: (i) algorithm exploitation, derivation and analysis, (ii) array realisation, and (iii) schemes to calculate arbitrarily long length DFT using a reasonable sized array. Four DFT systolic algorithms are examined and compared in terms of computing parallelism and computational complexity. Among the four algorithms, one is newly proposed. The new one exhibits much higher computing parallelism and lower computational complexity than the other three, but is applicable when the DFT length is prime. Based on the four algorithms, seven systolic arrays and seven two-level pipelined systolic arrays are devised. The outstanding features of these arrays are that the number of I/O channels is independent of the DFT length and the time overhead in manipulating consecutive data bundles are eliminated. Two schemes are presented to calculate long-length DFT using arrays with a reasonable number of processing elements. Performance of different algorithms, arrays and schemes is compared and summarised in six tables to serve as the selection criteria for different applications.Keywords
This publication has 3 references indexed in Scilit:
- Special-Purpose Devices For Signal And Image Processing: An Opportunity In Very Large Scale Integration (VLSI)1980
- On computing the Discrete Fourier TransformProceedings of the National Academy of Sciences, 1976
- Discrete Fourier transforms when the number of data samples is primeProceedings of the IEEE, 1968