QuickFFT: High Speed FFT for Arduino

Typical Arduino has limited RAM and processing power, and FFT is a computationally-intensive process. For many real-time applications, the only requirement is to get frequency with maximum amplitude or required to detect frequency peaks.

In one of my instructable, I prepared a code for FFT that can be found over here: EasyFFT

This code was able to perform FFT of up to 128 samples on Arduino nano. A higher sample number than this is not possible due to the limited memory of Arduino. I have modified the function a little bit to improve speed and reduce memory consumption. This modification allows Arduino to perform FFT five times faster and consumes almost half memory. This Instructable does not cover Working of FFT, references for it can be found at EasyFFT.

The typical FFT function is modified to improve the speed with lesser accuracy. As shown in the image a test signal needs to be multiplied by sine or cosine waveforms. These values can be between 0 to 1, so making floating multiplication is a must. in Arduino, Floating multiplication is slow compared to integer operations.

In this function, the sine/cosine wave is replaced by a square wave. As we have to multiply a test signal with a square wave which may have value 0,1 or -1. Due to that, we can replace floating multiplication to simply integer addition or subtraction. For Arduino integer addition or subtraction is around 5 times faster. This makes solving around 5 times faster.

Due to this modification now frequency bin values can be stored as an integer (which was previously float) and we get another advantage of lower memory consumption. In Arduino Nano, int consumes 2 bytes of memory while float consumes 4 bytes of memory. Due to this advantage in the new code, we are able to perform FFT for almost 256 samples (previously 128 samples).

In Normal FFT we needed to store the sine value to make a solution faster. In new function, as we no more required sine/cosine values we can eliminate it and save some memory.

Implementation:

Implementing this function is straight forward. We can simply copy the function at the ens of code. This function can be executed using the below command:

float f= Q_FFT(data,256,100);In function Q_FFT,

data: this term is an array having signal values, the recommended sample size are 2, 4, 8, 32, 64, 128, 256, 512, ... onwards. if the sample size does not belong to these values it will be clipped to the nearest lower side of values. for example, if the sample size is 75 than FFT will be carried out for 64 numbers of samples. Max number of sample size is limited by available RAM on Arduino.

The second term specifies the number of samples in an array and the last term is sampling frequency in Hz.

This section explains the modification made in EasyFFT code that needs to be kept in mind while making modification in the code,

1. As explained before, here integers are used to do FFT. Int in Arduino is a 16-bit number and can contain values from -32768 to 32768. whenever the value of this int exceeds this range it causes the problem. to eliminate this problem after ever level calculation. if any of the value exceeds 15000 complete arrays will be divided by 100. this will prevent the int to overflow.

2. Amplitude calculation: To calculate amplitude, the real and imaginary part needs to be squared and the square root of the sum is required. squaring and the square root of the function is time taking. to make the process faster, this code will simply do some of the magnitudes of real and imaginary parts. This is surely less accurate and may lead to the wrong conclusion in some cases. you may choose to return to the Normal method for magnitude calculation but it will take more time and you also need to do some arrangement to store these numbers.

3. This code does not have a module for multiple peak detection. It will simply choose the value with max amplitude (excluding the first number which is DC offset). If you need multiple peaks you can refer EasyFFT code and do required modification over here. In that case, some array/variable also needs to be declared as a global variable.

4. The function contains the following line:

unsigned int Pow2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048};

declaring the above variables as a global variable (pasting it at the start of code) will save somewhere 1 milliseconds time at every execution.

5. Unlike the EasyFFT function, where the top 5 peaks were stored in the predefined array. This function will return a float value. this value represents the frequency with maximum amplitude in Hz. So the representation of code will look something like this.

float f= Q_FFT(data,256,100);

6. Peak Detection: Once frequency with max amplitude is found this function uses an amplitude of frequency just before and after it to calculate the accurate results. Amplitude used in this calculation is also the sum of modulus (not the square root of the sum of squares)

if Fn is the frequency with max amplitude then the frequency can be calculated from below formula.

Actual F= (An-1 *Fn-1 + An-1 *Fn-1 + An-1 *Fn-1 ) / (An-1+An+An+1)

where An is amplitude of n the frequency and Fn-1 is frequency value.

Solving time is shown in the above image comparison with EasyFFT. Speed of it shown with the comparison.

For sample data having 3 sinusoidal waves with different frequencies is shown. The result from QuickFFT is compared with Scilab output. As we can see in the image 3 peaks with max amplitude is matching with Scilab output. However, the output consists of lots of noise, which may be misleading for some applications. So it is advised to check code properly before applying to your application.

I hope you found this code useful for your project. In case of any query or suggestion please do comment.