The Fast Fourier Transform Lomont（Lomont的快速傅里叶变换）.pdf

The Fast Fourier Transform Chris Lomont, Jan 2010, , updated Aug 2011 to include parameterized FFTs. This note derives the Fast Fourier Transform (FFT) algorithm and presents a small, free, public domain implementation with decent performance. A secondary goal is to derive and implement a real to complex FFT usable in most cases where engineers use complex to complex FFTs, which gives double the performance of the usual complex to complex FFT while retaining all the output information. A final goal is to show how to use the real to complex FFT as a basis for sound processing tasks such as creating frequency spectrograms. This work was necessitated by work on the HypnoCube, , which required a small, free, public domain, decently performing FFT implementation in C#. Since all the FFT implementations easily found failed on at least one aspect of this, this implementation was created and is released at the end of this document. The rest of this note details the real to complex FFT construction and how to apply this faster, lower resource using FFT for sound processing. Introduction The Fourier Transform converts signals f rom a time domain to a frequency domain and is the basis for many sound analysis and visualization algorithms. It converts a signal into magnitudes and phases of the various sine and cosine frequencies making up the signal. For example, take the signal shown in Figure 1 from the formula also shown in Figure 1, and sample it at the 32 equally spaced points shown. Figure 1: Figure 2 - The Fourier Transform of the samples √ √ Taking the Fourier Transform of these 32 real valued points results in 32 complex valued points. As shown later, these 32 points have a symmetry, so plotting only the magnitudes of the first 16 gives the result i