Fourier Transform - Completely Flustered About Recursive FFT

In summary, Fourier Analysis is a difficult topic for a beginner computer engineer. The Recursive Fourier Transform algorithm is a difficult algorithm for a beginner computer engineer to understand.
  • #1
carlodelmundo
133
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
  • #2


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.
 
  • #3


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.
 

1. What is a Fourier transform?

A Fourier transform is a mathematical operation that decomposes a function or signal into its individual frequency components. It is commonly used in signal processing, image processing, and other fields to analyze and manipulate data.

2. What is the purpose of a Fourier transform?

The purpose of a Fourier transform is to convert a function or signal from its original domain (such as time or space) to a representation in the frequency domain. This allows for easier analysis and manipulation of the data, as well as the ability to filter out unwanted frequency components.

3. What is the difference between a discrete Fourier transform and a recursive FFT?

A discrete Fourier transform (DFT) is a method of calculating a Fourier transform for a discrete, finite set of data points. A recursive fast Fourier transform (FFT) is a more efficient algorithm for calculating the DFT, using a divide-and-conquer approach. Essentially, recursive FFT is a specific implementation of the DFT algorithm.

4. How is a recursive FFT calculated?

A recursive FFT algorithm breaks down the calculation of the DFT into smaller sub-problems, which are then recursively solved until the entire DFT is calculated. This can be visualized as a tree structure, with the original data points at the bottom and the final DFT values at the top. By dividing the problem into smaller sub-problems, the overall calculation time is significantly reduced.

5. What are the applications of recursive FFT?

Recursive FFT is commonly used in signal processing, image processing, audio processing, and other fields where Fourier transforms are necessary. It is also used in computer graphics and video compression algorithms. Essentially, any application that requires analyzing and manipulating data in the frequency domain can benefit from using recursive FFT.

Similar threads

  • Electrical Engineering
Replies
8
Views
849
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • General Math
Replies
12
Views
959
  • Electrical Engineering
Replies
1
Views
883
Replies
3
Views
4K
  • Electrical Engineering
Replies
3
Views
1K
  • Advanced Physics Homework Help
Replies
5
Views
1K
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
733
Replies
10
Views
329
Back
Top