Multidimensional Fourier transforms by systolic architectures

A method of formal transformation of a multidimensional DFT (discrete Fourier transform) algorithm to a form suitable for implementation with a systolic macropipeline is discussed. The suggested transformation of the original form of the DFT algorithm consists of one or several rotationlike transforms applied to the index set. The resulting `completely systolized´ form of the algorithm makes it possible to implement the N^M-point (m-dimensional) DFT with a macropipeline containing M or (M-1) cascaded systolic/semisystolic arrays. Each array is an M-dimensional hypercube of the processing elements (PEs) of the multiply-add type; the internal structure of PEs in different arrays is slightly different. For given values of N and M, several design options exist, with hardware complexity of about the same value. The proposed systolic architecture makes it possible to obtain the throughput of N (one set of spectrum values every N array clocks) for any number of dimensions M