Title :
D.F.T. computation by fast polynomial transform algorithms
Author :
Nussbaumer, H.J.
Author_Institution :
IBM CER, La Gaude, France
Abstract :
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.
Keywords :
fast Fourier transforms; polynomials; DFT; auxiliary calculations; fast polynomial transform algorithms; multidimensional discrete Fourier transforms computation;
Journal_Title :
Electronics Letters
DOI :
10.1049/el:19790498