Efficient systolic arrays for fft algorithms

A new approach for the systolic implementation of FFT algorithms is presented. The proposed approach is based on the fundamental principle that a 1-dimensional DFT can be decomposed to a 2-dimensional DFT (with or without twiddle factors) and the 2-dimensional DFT can be computed efficiently on a 2-dimensional systolic array. The essence of the proposed systolic array is to combine different types of semi-systolic arrays into one array so that the resulting array becomes truly systolic. The proposed systolic array does not require any preloading of input data and it produces output data at boundary PEs. No networks for intermediate spectrum transposition between constituent 1-dimensional transforms are required; therefore the entire processing is fully pipelined. This approach also has significant advantages over existing architectures in reduced throughput and latency for large transforms.