Implementation of the discrete Fourier transform on 2-dimensional systolic processors

A scheme for computing the discrete Fourier transform (DFT) of a 2-dimensional systolic array processor is presented. The DFT algorithm is rewritten as a matrix based algorithm and mapped onto a 2-dimensional systolic array processor. The significance of this approach is that the total time required to complete an N-point DFT is 3¿(N) + N time units (assuming that it takes one time unit to operate data in a processor element (PE)); the architecture features nearest neighbour interconnections (as opposed to spatially global interconnections); all PEs in the 2-dimensional systolic array processor are busy (as opposed to some processor arrays in which half of the PEs are idle while the other half are busy); results of DFT computations are pipelined out directly in the correct order (as opposed to some processors which require bit-reversal operation or data commutation during the computational process); and the matrix-matrix multiplication and the diagonal elements of the matrix-matrix-matrix product can be computed systolically on the 2-dimensional processor.