Fourier Transform - Completely Flustered About Recursive FFT

[carlodelmundo]

Fourier Transform -- Completely Flustered About Recursive FFT

Hi all.

I have been banging my head about this problem for the last week and a half-- Fourier Transform. Some background about me: I am a rising Junior at an accredited university majoring in Computer Engineering & Computer Science. I have not taken signals and systems yet (but will be taking next semester).

I have successfully and independently implemented the Discrete Fourier Transform (DFT-- running time O(n^2)). I am trying to learn the Recursive implementation of the FFT with little to no luck. I'm currently using "Introduction to Algorithms" by Cormen, and have been staring blankly at 30.2 -- the recursive-FFT algorithm.

I am in big trouble--- I have never crawled like this in my whole academic career ... I "sort of" understand what's going on on a high level, but implementation-wise I am just lost with the Math.

Can someone point me to the right direction on Fourier Analysis? Specifically, what should I read upon... what are pre-requisite knowledge, etc?

Thanks

 

[0xDEADBEEF]

Dear rising Junior,
welcome to the world of science where you learn quickly that you are less smart than you thought, and there are many more people that are even smarter -- especially the dead ones. Don't give up. This is normal. Reread the chapter and ask yourself on every sentence if you understand it and explain why. This will take hours, that is the idea of studying instead of just learning. If it didn't work, get other books. The FFT is so well known, that there are many layman articles and tons of reference implementations. Study those. Even wikipedia has a short example of an implementation: http://de.wikipedia.org/wiki/Schnel...on#Implementierung_als_rekursiver_Algorithmus

Recursion is one of those things that people struggle with, the same with pointers. These topics sort good programmers from the bad ones. When you really understand them most of the other programming techniques are fairly easy. Good luck.

 

[carlodelmundo]

Thanks DeadBeef. I think this is the response I needed to hear. I've been breaking the process down step-by-step and "sentence by sentence" as you say. The study of complex analysis (or the review...) gave me some insight on how some of these optimizations work.

Thanks! Will continue on breaking down this problem.