A two dimensional fast fourier transform processor suitable for wafer scale integration
Gregory F. Taylor · 1985
A description of an architecture capable of computing two dimensional Fast Fourier transforms on a 256 by 256 pixel image is presented. The architecture consists of a small number of basic building blocks which may be repeated to yield any desired performance. To achieve video rate performance sixteen butterfly processors, arranged as four loosely coupled clusters of four processors each, and nine working memories are required. A constant geometry algorithm is employed, allowing conflict free memory sharing. The portion of an image assigned to any particular processor changes during the course of the transform without time penalty, because I/O and computation are overlapped. Two sets of building blocks have been designed, using two different CMOS gate array families. These may be interconnected using discretionary wiring Wafer Scale Integration to complete the core of the system, a fast one dimensional FFT processor. The performance of this processor is equivalent to more than 63 million 16 bit fixed point multiplications per second.