Hello everyone,

I'm trying to make a sketch for Arduino to do the FFT of an 8 sample signal. I looked up on the internet on how to do FFT and came across dozens of webpages explaining what a "butterfly" is. I tried to code up a sketch to do FFT, but I'm not quite sure if it is working or not. When I put certain sinewaves directly in the input[] value, FFT returns expected results, sometimes...

It took me a while just to grasp the basic concept of FFT over DFT, so I don't even know if my math here is right! But here is my code:

`#define FFTSIZE 8`

float input[FFTSIZE];

float output[FFTSIZE];

const float sina[FFTSIZE] = {0, 0.71, 1, 0.71, 0, -0.71, -1, -0.71};

const float cosa[FFTSIZE] = {1, 0.71, 0, -0.71, -1, -0.71, 0, 0.71};

void setup() {

Serial.begin(9600);

for(int counter = 0; counter < FFTSIZE; counter++) {

input[counter] = sin(2 * PI * 1 * counter / FFTSIZE);

Serial.println(input[counter]);

}

Serial.println("FFT Values Return:");

}

void loop() {

FFT();

Serial.println();

for(int counter = 0; counter < FFTSIZE; counter++) {

Serial.println(output[counter]);

}

while(1);

}

void FFT() {

float X[FFTSIZE];

float Y[FFTSIZE];

float Z[FFTSIZE];

// buterfly 2

X[0] = input[0] + input[4];

X[1] = input[0] - input[4];

X[2] = input[1] + input[5];

X[3] = input[1] - input[5];

X[4] = input[2] + input[6];

X[5] = input[2] - input[6];

X[6] = input[3] + input[7];

X[7] = input[3] - input[7];

// butterfly 4

Y[0] = X[0] + X[2];

Y[1] = X[1] + X[3];

Y[2] = X[0] - X[2];

Y[3] = X[1] - X[3];

Y[4] = X[4] + X[6];

Y[5] = X[5] + X[7];

Y[6] = X[4] - X[6];

Y[7] = X[5] - X[7];

// final butterfly 8

Z[0] = Y[0] + Y[4];

Z[1] = Y[1] + (Y[5] * (sina[1] + cosa[1]));

Z[2] = Y[2] + Y[6];

Z[3] = Y[3];

Z[4] = Y[0] - Y[4];

Z[5] = Y[1] - (Y[5] * (sina[1] + cosa[1]));

Z[6] = Y[2] - Y[6];

Z[7] = Y[3];

for(int counter = 0; counter < FFTSIZE; counter++) {

if(Z[counter] < 0) Z[counter] = 0;

output[counter] = Z[counter];

}

}

Any help would be great, thanks.

Judd