# Implementing The Fast Fourier Transform On Arduino

By Sam Proctor, Smart Solutions Research & Development

## Introduction

So now we have a data capture board and an excellent way of programming it, we can focus on data analysis software.

We have already mentioned the use of vibration data as a prime source of information to help us in our EHM goals. As such this article shows the steps to getting a Fast Fourier Transform (FFT) up and running on our Arduino board.

## What is the Fast Fourier Transform?

For those not familiar with the FFT, presented here is a brief introduction. The Fast Fourier Transform is rather un-suprinsingly derived from the Fourier Transform. The Fourier Transform is a process by which a signal measured as a function of time can be decomposed into the frequencies that make the signal. The animation below shows how this might be described.

Fourier Transform Animation

What this animation shows is a complex signal built up from several different sine & cos waves at different frequencies and amplitudes. The Fourier Transform is the method that allows us to get access to these different components. However the Fourier Transform is computationally expensive, therefore the Fast Fourier Transform was created to allow its deployment to many applications that would otherwise not be able to utilize it. For a more detailed explanation please see the most excellent Wikipedia Article.

## FFT Algorithm

The most common FFT algorithm is the Cooley-Tukey Algorithm, which is what we are going to implement on the Arduino. The Algorithm in C from University of Texas is below:

```//--------------------------------------------
//Name: FFT
//Desc: Cooley-Tukey based FFT Function
//--------------------------------------------
void FFT(double data[], int nn, int isign)
{
int n, mmax, m, j, istep, i;
double wtemp, wr, wpr, wpi, wi, theta;
double tempr, tempi;

n = nn << 1;
j = 1;
for (i = 1; i < n; i += 2)
{
if (j > i)
{
tempr = data[j];
data[j] = data[i];
data[i] = tempr;
tempr = data[j+1];
data[j+1] = data[i+1];
data[i+1] = tempr;
}

m = n >> 1;
while (m >= 2 && j > m)
{
j -= m;
m >>= 1;
}
j += m;
}
mmax = 2;
while (n > mmax)
{
istep = 2*mmax;
theta = TWOPI/(isign*mmax);
wtemp = sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi = sin(theta);
wr = 1.0;
wi = 0.0;
for (m = 1; m < mmax; m += 2)
{
for (i = m; i <= n; i += istep)
{
j =i + mmax;
tempr = wr*data[j]   - wi*data[j+1];
tempi = wr*data[j+1] + wi*data[j];
data[j]   = data[i]   - tempr;
data[j+1] = data[i+1] - tempi;
data[i] += tempr;
data[i+1] += tempi;
}
wr = (wtemp = wr)*wpr - wi*wpi + wr;
wi = wi*wpr + wtemp*wpi + wi;
}
mmax = istep;
}
}

```

The function takes three inputs:

• data – array, double spaced to allow for complex numbers, gets overwritten with the results
• nn – Length of the FFT to the next highest power of 2
• isign – Flag to compute either the FFT or its inverse

This function is placed in the main program file, it will be placed in the Smart Solutions data analysis library in the future.

## Putting It All Together

In order to obtain something useful from the Arduino we need to have a complete program to sample, process and store. For starting we will use a 64 sample array on which to carry out the FFT. As such the program will sample the accelerometer & log the measurements to SD card. The SD card persistence step is required at this stage as it will allow us to verify the FFT results. Once 64 samples have been collected we carry out the FFT and log the results also to SD Card.

```//--------------------------------------------
//Name: loop
//Desc: Continually on the Arduino
//--------------------------------------------
void loop()
{
sensors_event_t accel_event;
sensors_event_t rate_event;
sensors_event_t mag_event;
sensors_event_t bmp_event;
sensors_vec_t   orientation;
File dataFile;
String dataString;
float sampleRate = 0.0f;

digitalWrite(myLED, HIGH);
accel.getEvent(&accel_event);

if(sampleCount > NFFT)
{
//When we have received enough samples to do a calculation
String displayString = "Buffer ";
displayString += fileNumber;
displayString += " full with ";
displayString += sampleCount;
displayString += " samples";
Serial.println(displayString);

//How long did it take to record these samples
delta = millis() - timer;
//What is the average sample rate
sampleRate = ((float)sampleCount / delta)*1000.0f;
//Set the timer to the current time
timer = millis();
sampleCount = 0;
dataLog.closeLogFile(); //Close the current log file
//Carry out the FFT
FFT(vibXData, NFFT, 1);
//Now record the results to the SDCard

initNextFFTFile();

for(int i=0; i<NFFT; i++)
{
double val1 = vibXData[i*2];
double val2 = vibXData[(i*2)+1];
dataString = "";
dataString += val1;
dataString += ",";
dataString += val2;
dataLog.logDataString(dataString);
}

//We have finished logging the FFT results so close the file and continue
dataLog.closeLogFile(); //Close the current log file
initNextBufferFile(); //Get the next data log ready to use
}
else
{
sampleCount++;
//Record vibration X data to carry out FFT
vibXData[sampleCount*2] = accel_event.acceleration.x;
vibXData[(sampleCount*2)+1] = 0.0f;

//Create the data string
dataString = "";
dataString += millis();
dataString += ",";
dataString += accel_event.acceleration.x;
dataString += ",";
dataString += accel_event.acceleration.y;
dataString += ",";
dataString += accel_event.acceleration.z;
//Now log this to the SD card
dataLog.logDataString(dataString);
//Serial.println(dataString);
}

digitalWrite(myLED, LOW);
}
```

To test the program we used an iPhone app designed to turn on the phones vibrator at a preset interval.

## Initial Results

In order to determine if the code was working correctly, a simple test was devised, the test was run in the following manner:

• Place vibration sensor unit onto iPhone
• Ensure SD Card is plugged into Arduino Board
• Turn on Arduino
• Start Vibration App

The device was left to capture for around 15 seconds after the vibration app was started. After this time the Arduino was turned off by removing the power.

In order to view the captured data an Octave script was created to read, parse  and display the captured data. The image below shows the raw vibration signal for the test.

Captured Vibration Data (time domain)

The same octave script also processed the raw FFT results to produce a ‘spectrogram’ chart to show the FFT results over time.

FFT Results (Frequency Domain)

## Conclusion

During this article we have showed how we implemented an Arduino program to capture vibration and perform an FFT before storing it to SD Card. These key results as shown by plotting the data show that we are ready to start capturing data from a more real world source and perform more in-depth analysis of the results.