AN ALGORITHM FOR COMPUTING MIXED RADIX FAST FOURIER TRANSFORM

This paper presents an algorithm for computing the fast Fourier transform, based on a method proposed by Cooley and Tukey. As in their algorithm, the dimension n of the transform is factored (if possible), and n/p elementary transforms of dimension p are computed for each factor pof n. An improved method of computing a transform step corresponding to an odd factor of n is given; with this method, the number of complex multiplications for an elementary transform of dimension p is reduced from (p—1)2 to (p—1)2 for odd p. The fast Fourier transform, when computed in place, requires a final permutation step to arrange the results in normal order. This algorithm includes an efficient method for permuting the results in place. The algorithm is described mathematically and illustrated by a FORTRAN subroutine. Copyright © 1969 by The Institute of Electrical and Electronics Engineers, Inc.