Fast-Fourier-Transform-Algorithm

Fast Fourier Transform (aka. FFT) is an algorithm that computes Discrete Fourier Transform (DFT). We’re not going to go much into the relatively complex mathematics around Fourier transform, but one important principle here is that any signal (even non-periodic ones) can be quite accurately reconstructed by adding sinusoidal signals together with different frequencies and amplitudes. The more sinusoidal signals we add together, the more our reconstructed signal will look like the original one. Theoretically speaking, with an infinite amount of sinusoidal signals we get an identical signal as the original. The FFT-algorithm uses this principle and essentially enables you to see which frequencies are present in any analog signal and also see which of those frequencies that are the most dominating. This is very helpful in a huge amount of applications. The Nyquist-Shannon Sampling Theorem tells us that to be able to sample a signal, the sampling frequency needs to be at least twice the frequency of the signal we’re trying to sample. In other words, the FFT will only be able to detect frequencies up to half the sampling frequency. On a common Arduino, the sampling frequency is quite limited, though. An ADC operation (using analogRead()) takes about 100 μs, and other operations are relatively slow due to the 8 or 16 MHz clock frequency. The FFT-algorithm works with a finite number of samples. This number needs to be 2n where n is an integer (resulting in 32, 64, 128, etc). The larger this number is, the slower the algorithm will be. However, with many samples you will get a larger resolution for the results. The term bins is related to the result of the FFT, where every element in the result array is a bin. One can say this is the “resolution” of the FFT. Every bin represent a frequency interval, just like a histogram. The number of bins you get is half the amount of samples spanning the frequency range from zero to half the sampling rate. There are of course several ways to implement FFT on an Arduino. You can implement it from scratch or you can use a pre-made library. The setup we’re going to use here is an Arduino Uno and a signal generator. The only wires are the two from the signal generator where one goes to A0 on the Arduino and the other goes to GND. Our signal has an amplitude and offset such that it almost spans the complete 0-5 V range, suiting our ADC’s properties well. We apply FFT to a proper analog signal. The example code generates a simulated sinusoidal signal and applies FFT to that.