An algorithm for computing the mixed radix fast Fourier transform

Author

Singleton, Richard C.

Author_Institution

Stanford Research Institute, Menlo Park, CA, USA

Volume

17

Issue

2

fYear

1969

fDate

6/1/1969 12:00:00 AM

Firstpage

93

Lastpage

103

Abstract

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 $p$ of $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}/4$ 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.

Keywords

Fast Fourier transforms; Fourier transforms; Matrix decomposition; Organizing; Partitioning algorithms; Research and development; Spectral analysis; Speech analysis;

fLanguage

English

Journal_Title

Audio and Electroacoustics, IEEE Transactions on

Publisher

ieee

ISSN

0018-9278

Type

jour

DOI

10.1109/TAU.1969.1162042

Filename

1162042