DFT COMPUTATION BY FAST POLYNOMIAL TRANSFORM ALGORITHMS

A new method is introduced for the fast computation of multidimensional discrete Fourier transforms (d.f.t.). We show that some multidimensional d.f.t.s are mapped efficiently into one-dimensional d.f.t.s by using a single polynomial transform and some auxiliary calculations. Since polynomial transforms can be computed without multiplications, this approach reduces significantly the number of operations over the conventional fast Fourier transform (f.f.t.) and is therefore attractive for image-processing applications. © 1979, The Institution of Electrical Engineers. All rights reserved.