3

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/used in the code?? Please guide me.

Thanks, Psbk

Psbk
  • 33
  • 1
  • 1
  • 3
  • Perhaps this question is better asked at http://programmers.stackexchange.com/tags/algorithms –  Jan 09 '15 at 05:36
  • 2
    At the risk of sounding a bit too 20th Century, go find a copy of the book The Fast Fourier Transform and its Applications by E. Brigham. I have yet to find a better explanation and after reading it, all will become clear. It's a bit pricey to buy, so your local library may be a better place to start. – andand Jan 09 '15 at 06:08
  • 1
    @andand: I second that recommendation - it's a superb book and is a rarity in that it spends a lot of time looking at practical applications of the FFT rather than just the theory. – Paul R Jan 09 '15 at 06:26

1 Answers1

0

I strongly recommend to read this: https://stackoverflow.com/a/26355569/2521214

Now from the first look the offset and delta is used to:

  • make the butterfly shuffle permutation
  • you start with step 1 and half of the interval
  • and by recursion you will get to log2(N) step and interval of 1 item ...
  • +/- one recursion level
  • I usually do the butterfly in reverse order

The XX array

  • is a buffer to store the subresult or input data
  • you can not perform FFT inplace easily (if at all)
  • so you compute to/from the temp buffer instead
  • and on each recursion just swap the data and temp buffers (physically or their meaning)
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thanks a lot for the detailed explanation on my question. It is useful to me very much. I will go through the code again with the information given by you and ask for any other information if I get stuck somewhere. I am going through the link that you have mentioned and feel it is very good. Thanks a lot again. – Psbk Jan 09 '15 at 11:22