Multidimensional systolic arrays for multidimensional DFTs

This paper presents a multidimensional systolic array for performing the multidimensional discrete Fourier transform (DFT). Extensions of the multidimensional systolic array are widely searched for the prime-factor computation or the 2ⁿ-point decomposed computation of one-dimensional (1-D) DFT. The essence of the proposed multidimensional systolic array is to combine different types of semi-systolic arrays into one array so that the resulting array becomes truly systolic. This 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.