FFT Algorithm C Code Explaination

Projects Programming
1

http://www.tech.dmu.ac.uk/~eg/tensiometer/fft/fft.c

http://www.tech.dmu.ac.uk/~eg/tensiometer/fft/fft_test.c

I have found a good working C Code for FFT Algorithm for converting Time Domain to Frequency Domain and vice versa in the above links. But I wanted to know the flowchart or step by step process of how this code works. I am trying to analyze the code with butterfly method of decimation in time for FFT but i am facing difficulties in understanding the code. The code is working very well and giving me the correct results but it would be very helpful to me if someone could give a brief or detailed explaination on how this code works.

I am confused with the array and the pointers used in the fft.c code. Also I am not getting what are the variables offset and delta mean in the code. How the rectangular matrix of real and imaginary terms are considered in the code?? Please guide me.

Thanks,
Psbk

fft.C (4.18 KB)

fft_test.c (4.94 KB)

2

This might be a good place to start

3

or - An Interactive Guide To The Fourier Transform – BetterExplained -

4

I don't know anything about fft itself, but here are some hints as to weird C syntax:

  • x: pointer to N time-domain samples given in rectangular form (Re x, Im x)

So your input array x, looks like:

     Real, *j
0:    1,   1
1:    2,   2
2:    3,   3
3:    4,   4

In C, arrays are passed by refererence: a pointer to the memory location of the first element in the array. Normally, you'd declare your functions as having an array as parameters, and pointer handling would happen behind the scenes, something like:

//define a datatype for complex numbers
typedef struct { double realpart; double imaginarypart; } Complex_t;

// our data is an array of complex numbers
Complex_t data_array[100];

 // our function has arrays of complex numbers as arguments.
void my_fft (int N, Complex_t x[], Complex_t X[]);

this code doesn't do that. Instead, it has the very C-like:

void fft(int N, double(*x)[2], double(*X)[2]);

"double(*x)[2]" reads as "x is a pointer to a a touple of doubles."
Which is the same as "a pointer to a complex number"

Which is ALSO the same as "a point to an array of complex numbers", or just
"an array of complex numbers."

You can call the function recursively with sub-arrays of your original data,
JUST by manipulating the pointers (no data copying or anything.) "x+n"
(where n is an integer) is a pointer to the sub-array of x that starts at
the nth element.

Does that help some?

5

Real, *j

Bloody sparkies, thinking they can subvert mathematics {mumble. mumble}