Multidimensional Fourier transforms by systolic architectures

摘要

A method of formal transformation of a multidimensional DFTn(discrete Fourier transform) algorithm to a form suitable fornimplementation with a systolic macropipeline is discussed. The suggestedntransformation of the original form of the DFT algorithm consists of onenor several rotationlike transforms applied to the index set. Thenresulting `completely systolized' form of the algorithm makes itnpossible to implement the N^M-pointn(m-dimensional) DFT with a macropipeline containing Mnor (M-1) cascaded systolic/semisystolic arrays. Each array isnan M-dimensional hypercube of the processing elements (PEs) ofnthe multiply-add type; the internal structure of PEs in different arraysnis slightly different. For given values of N and M,nseveral design options exist, with hardware complexity of about the samenvalue. The proposed systolic architecture makes it possible to obtainnthe throughput of N (one set of spectrum values everynN array clocks) for any number of dimensions M