FFT COMPUTATION WITH SYSTOLIC ARRAYS, A NEW ARCHITECTURE

The use of the Cooley-Tukey algorithm for computing the 1-d FFT lends itself to a particular matrix factorization which suggests direct impl ementation by linearly-connected systolic arrays. Here we present a ne w systolic architecture that embodies this algorithm. This implementat ion requires a smaller number of processors and a smaller number of me mory cells than other recent implementations, as well as having all th e advantages of systolic arrays. For the implementation of the decimat ion-in-frequency case, word-serial data input allows continuous real-t ime operation without the need of a serial-to-parallel conversion devi ce. No control or data stream switching is necessary. Computer simulat ion of this architecture was done in the context of a 1024 point DFT w ith a fixed point processor, and CMOS processor implementation has sta rted.