Fourier Transform - Completely Flustered About Recursive FFT

AI Thread Summary
The discussion centers on the challenges faced by a computer engineering student in understanding the Recursive Fast Fourier Transform (FFT) after successfully implementing the Discrete Fourier Transform (DFT). The student expresses frustration with the mathematical concepts and implementation details of the FFT as outlined in "Introduction to Algorithms" by Cormen. Responses emphasize the importance of thorough comprehension, suggesting that rereading the material and breaking it down into manageable parts can aid understanding. Additionally, exploring alternative resources, including layman articles and online examples, is recommended to reinforce learning. The conversation highlights the common struggles with recursion and the necessity of persistence in mastering complex topics.
carlodelmundo
Messages
133
Reaction score
0
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
 
Engineering news on Phys.org


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.
 


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.
 
Hey guys. I have a question related to electricity and alternating current. Say an alien fictional society developed electricity, and settled on a standard like 73V AC current at 46 Hz. How would appliances be designed, and what impact would the lower frequency and voltage have on transformers, wiring, TVs, computers, LEDs, motors, and heating, assuming the laws of physics and technology are the same as on Earth?
While I was rolling out a shielded cable, a though came to my mind - what happens to the current flow in the cable if there came a short between the wire and the shield in both ends of the cable? For simplicity, lets assume a 1-wire copper wire wrapped in an aluminum shield. The wire and the shield has the same cross section area. There are insulating material between them, and in both ends there is a short between them. My first thought, the total resistance of the cable would be reduced...
I used to be an HVAC technician. One time I had a service call in which there was no power to the thermostat. The thermostat did not have power because the fuse in the air handler was blown. The fuse in the air handler was blown because there was a low voltage short. The rubber coating on one of the thermostat wires was chewed off by a rodent. The exposed metal in the thermostat wire was touching the metal cabinet of the air handler. This was a low voltage short. This low voltage...
Back
Top