The Fast Fourier Transform is literally just a faster version of the Discrete Fourier Transform. In its naive form, the Discrete Fourier Transform is quite costly to compute, especially if you are interested in computing it in real-time. The FFT is an algorithmic optimization of the DFT which makes fast, real-time computation of the DFT possible on consumer grade hardware. I don’t want to go into the details of the FFT, but I feel obliged to share some quirks and gotchas you might encounter when using FFT libraries to develop software.

When you start developing software which incorporates an FFT library, the first eccentricity you’ll probably notice is that not all libraries output their data in the same format. All good libraries will give you a set of complex numbers, but the layout and ordering of these complex numbers may differ depending upon the library that you use.¹ My suggestion is to familiarize yourself with the open-source package Octave, and use Octave’s implementation of the FFT as your ground-truth when comparing different FFT implementations.²

You can compute the FFT of an 8-sample sine wave in Octave using the following commands,


The first command declares a discrete signal called eight_sample_sine_wave. The second command runs the FFT on this signal and will produce the following list of complex numbers as a result. You can compare this output to the results given earlier in our walk-through of the transform,

I consider this to be "normal" output. Some high-performance libraries will output the result with a different layout in order to optimize the memory and speed characteristics of their FFT routines. For example, some libraries will omit the imaginary parts of the DC and Nyquist bins since these are always known to be zero for real-valued inputs.³ Omitting these two components, the library might choose to output the data in a format like this,

Since the bins after the Nyquist bin are complex-conjugate mirrors of the bins before the Nyquist bin, some libraries will omit these bins from the output altogether. For example, you might receive your results in a format like this,



This page gives a pretty nice overview of the different formats you might encounter when trying to interpret the output of your FFT library. Note too, that the output layout may vary depending upon platform. Good Luck!

The second eccentricity you’ll encounter is that different FFT libraries apply the scaling factor at different points in the FFT⇄IFFT roundtrip. The scaling factor may be applied during the forward transform, during the inverse transform, or partly in the forward transform and partly in the inverse transform. The scaling factor is used to ensure that when performing an FFT and IFFT (Inverse Fast Fourier Transform) the IFFT will produce the original signal. For example, try the following in Octave,⁴

Note that the maximum bin magnitude after performing the FFT is related to the length of the input signal. For a four sample sine wave, the maximum is 2, and for an eight sample sine wave the maximum is 4. We need to account for the length of the input signal, and this is where the scaling factor comes in. We must divide our signal by N/2 at some point during the FFT/IFFT round trip if we want to get the original signal back when performing the IFFT.

Some libraries don't perform this scaling. FFTW will return a scaled output and force you to apply the scaling factor yourself. They have good reasons for this, which you can read about here. Other packages like Octave will apply the scaling factor during the IFFT. Some libraries will perform a little bit of the scaling during both the forward and inverse transform by dividing by SQRT(N/2) in both the inverse and forward transform.

Long Story Short
Read the documentation of your library before becoming frustrated and confused by its output. If your output doesn't look like you would expect it to, you should check the output layout and understand how the scaling factor is applied in your library of choice. This stuff is not standardized.