A new parallel 2-D FFT architecture

An efficient parallel architecture has been developed that can perform a 2-D Fourier transform in O((√N)N log √N) time. The speedup is achieved through a decomposition of the of the 2-D Fourier transform into two smaller M ×M 2-D transforms and a parallel implementation of the smaller transform. Memory bandwidth is not a problem in this architecture with a new memory partitioning strategy that successfully divides the large memory into N smaller, independent memories. The flexibility and modularity of the new 2-D FFT algorithm allows for a variety of sizes for the parallel 2-D FFT units. The decomposition of the 2-D FFT can be applied as many times as necessary until the right tradeoff between size and speed is obtained. The architecture offers an attractive tradeoff between size and speedup with an improvement of processor performance/size by over a factor of five