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/sup 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.