Fast Fourier Transform Programs for the Digital Simulator and Computer (DISAC)

摘要

For processing signals in the spectral domain, it is often useful to program a digital computer to compute the forward or inverse Discrete Fourier Transform (DFT) of N sample values of a complex time or frequency function. This report describes a computer program which implements the Fast Fourier Transform algorithm to give a reduction in DFT computation time by a factor of 2N/log of N to the base 2 when N is a power of two. Other properties of the DFT are used to further reduce computation time and memory storage required when the time samples are real. Also described are an auxiliary program for generating the complex exponentials needed to compute the DFT, and a subroutine for converting the complex DFT coefficients to a magnitude-phase representation. (Author)