Area-efficient architecture for Fast Fourier transform

Abstract

We present an area-efficient parallel architecture that implements the constant-geometry, in-place Fast Fourier transform. It consists of a specific purpose processor array interconnected by means of a perfect unshuffle network. For a radix r transform of N=r/sup n/ data of size D and a column of P=r/sup p/ processors, each processor has only one local memory of N/rP words of size rD, with only one read port and one write port that, nevertheless, make it possible to read the r inputs of a butterfly and write r intermediate results in each memory cycle. The address generating circuit that permits the in-place implementation is simple and the same for all the local memories. The data how has been designed to efficiently exploit the pipelining of the processing section with no cycle loss. This architecture reduces the area by almost 50% of other designs with a similar performance.