2D GRID ARCHITECTURES FOR THE DFT AND THE 2D DFT

New algorithms for the DFT and the 2-dimensional DFT are presented. The DFT and the 2-dimensional DFT matrices can be expressed as the Kronecker product of DFT matrices of smaller dimension. These algorithms are synthesis by combining the efficient factorization of the Kronecker product of matrices with the highly hardware efficient recursive implementation of the smaller DFT matrices, to yield these algorithms. The architectures of the processors implementing these algorithms consist of 2-dimensional grid of processing elements, have temporal and spatial locality of connections. For computing the DFT of size N or for the 2D DFT of size N = N1 by N1, these algorithms require 2N multipliers and adders, take approximately 2 square-root N computational steps for computing a transform vector, and take approximately square-root N computation steps between the computation of two successive transform vectors.