What is the Fourier transform?

At a high level the Fourier transform is a mathematical function which transforms a signal from the time domain to the frequency domain. This is a very powerful transformation which gives us the ability to understand the frequencies inside a signal. For example you can take an audio signal and detect sounds or tones inside it using the Fourier transform.

As an example of what the Fourier transform does, look at the two graphs below:

Awesome XKCD-style graph generated by http://matplotlib.org/users/whats_new.html#xkcd-style-sketch-plotting

The graph on the left represents a complex signal in the time domain, like what a microphone might produce. This signal is actually the sum of two sine waves. You can see a low frequency sine wave with high intensity gives the signal its overall up and down shape. However a higher frequency sine wave with a lower intensity is added to the signal so it has small rough edges that protrude out as it rises and falls.

The graph on the right is the result of running a Fourier transform on the signal at the left. You can see the Fourier transform output as a histogram, or bar graph, of the intensity of each frequency. It's immediately apparent that two frequencies, the two spikes in the graph, have much stronger intensities than the others. These frequencies actually represent the frequencies of the two sine waves which generated the signal. The output of the Fourier transform is nothing more than a frequency domain view of the original time domain signal.

For more information and background on the Fourier transform, take a look at this link. This is a great resource because it doesn't dwell on the mathematics and instead focuses on building an intuition of the Fourier transform.

Why should I care about the Fourier transform?

Complex signals made from the sum of sine waves are all around you! In fact, all signals in the real world can be represented as the sum of sine waves. The Fourier transform gives us insight into what sine wave frequencies make up a signal.

You can apply knowledge of the frequency domain from the Fourier transform in very useful ways, such as:

• Audio processing, detecting specific tones or frequencies and even altering them to produce a new signal.
• Compression, how representing a signal in the frequency domain can lead to more compact representations in memory.
• Radar, detecting how a shift in frequency of reflected electromagnetic signals relates to the distance traveled and speed of an object.
• And many more applications!

How do I use the Fourier transform?

Libraries exist today to make running a Fourier transform on a modern microcontroller relatively simple. In practice you will see applications use the Fast Fourier Transform or FFT--the FFT is an algorithm that implements a quick Fourier transform of discrete, or real world, data. This guide will use the Teensy 3.0 and its built in library of DSP functions, including the FFT, to apply the Fourier transform to audio signals.

You can find more information on the FFT functions used in the reference here, but at a high level the FFT takes as input a number of samples from a signal (the time domain representation) and produces as output the intensity at corresponding frequencies (the frequency domain representation).

There are two important parameters to keep in mind with the FFT:

• Sample rate, i.e. the amount of time between each value in the input. Sample rate has an impact on the frequencies which can be measured by the FFT. Nyquist's sampling theorem dictates that for a given sample rate only frequencies up to half the sample rate can be accurately measured. Keep this in mind as sample rate will directly impact what frequencies you can measure with the FFT.
• FFT size, the number of output frequency bins of the FFT. The FFT size dictates both how many input samples are necessary to run the FFT, and the number of frequency bins which are returned by running the FFT. In practice I found an FFT size of 256 was most usable on the Teensy 3.0. You can go higher to 1024, but a significant amount of the Teensy's memory is consumed to hold the input and output of the FFT.

One other important thing to keep in mind when applying the FFT is that the input and output is typically in the complex number plane. You might need to transform input and output data between real and complex numbers to use the FFT. For our purposes we're only dealing with real data so the complex coefficients in the input and output are zero.

Finally, the output of the FFT on real data has a few interesting properties:

• The very first bin (bin zero) of the FFT output represents the average power of the signal. Be careful not to try interpreting this bin as an actual frequency value!
  
• Only the first half of the output bins represent usable frequency values. This means the range of the output frequencies detected by the FFT is half of the sample rate. Don't try to interpret bins beyond the first half in the FFT output as they won't represent real frequency values!
  

Continue on to learn about the hardware setup for this guide.