1 Introduction

 

Fast Fourier transforms (FFT) are speedy implementations of the discrete Fourier transform (DFT) that rely on mathematical simplification and classification of the input sequence to achieve their performance gain. As is the case with the Cooley-Tukey algorithms developed in this paper, the FFT typically reqiures O(N log₂ N) operations to complete in comparison to the straight DFT requiring O(N²) operations. Presented here are simplifications referred to as radix-2 and radix-4, specifically designed for input sequences of length 2^m and 4^m, respectively. The algorithm developed is a decimation-in-frequency type with in-place computation; and, owing to the employment of recursion, is quite simple and elegant.

Section 2 explores briefly the mathematical development in the Cooley-Tukey class of algorithms. Section 3 describes issues related to this specific implementation of radix-2 and radix-4. Section 4 presents results obtained around the WPI Electrical Engineering department's computer resources, for several input sequence lengths. Section 5 closes this paper with conclusions. As an addendum, section 6 is a presentation of the source code.