On the derivation of the fast Fourier transform
Sidney Bertram · IEEE Transactions on Audio and Electroacoustics · 1970
The fast Fourier transform (FFT) provides an effective tool for the calculation of Fourier transforms involving a large number of data points. The paper presents new and simple derivations for the two basic FFT algorithms that provide an intuitive basis for the manipulations involved. The derivation for the "decimation in time" algorithm begins with a crude analysis for the zero frequency and fundamental components using only two data samples, one at the beginning and the second at the midpoint of the period of interest. Successive interpolations of data points midway between those previously used result in a refinement of the amplitudes already determined and a first value for the next higher order coefficients. The derivation of the "decimation in frequency" algorithm begins by resolving the original data set into two new data sets, one whose transform includes only even harmonic terms and a second whose transform includes only odd harmonic terms. Since the first of the two new data sets repeats after the midpoint, it can be transformed using only the first half of the data points. The second of the new data sets is multiplied by the negative fundamental function, thereby reducing its order by one and converting it into a data set that transforms into even harmonics only; in this form it can also be transformed using only the first half of the data set. Successive applications of this procedure result finally in reducing the operation to the calculation of a large number of simple two-data-point transforms.