Understanding FFT's

Well if you're really interested, you might start with just understanding regular analog Fourier Transforms before you try to jump into the FFT.

I don't know how complete or easy to understand this will be, but it might be worth a look:
MIT Open Courseware: Signals and Systems

or possibly this one is more relevant, but higher level course:

MIT Open Courseware: Discrete Time Signal Processing

Might be too hard to understand for someone without an engineering background though, so just see if it works for you.

I don't know if you can get to understanding FFTs on your own, but here's a plan: The first thing to do is to try to understand Fourier series (writing periodic functions in terms of an orthogonal base). Next step is continuous Fourier transform, then the discrete Fourier transform. FFT is just a trick to compute the discrete Fourier transform fast. It can also be viewed as evaluating a polynomial at the N-th roots of unity using an arithmetic trick to speed up the computation. Then you have to jump to 2D transforms.

The college course to start with ought to be Differential Equations.

Quote:

Original post by LessBread The college course to start with ought to be Differential Equations.

I completely disagree. FFTs arise much more naturally in signal processing.

Thanks very much for the suggestions, guys. Before I embark on Differential Equations, are there any prerequisites that I should know about? As I mentioned, my calculus is quite weak. Should I spend a couple of months studying calculus and nail that down first?

I didn't think I needed much DiffEq to learn Fourier transforms. Maybe some of the tough ones you need DE to do the proofs or something, but I think as long as you just understand integrations you should be able to get through it. Most of the transforms can be done using transform tables (i.e. cheat sheets), and you just have to do some algebra acrobatics to get stuff into the right form.

I think this would be plenty sufficient for the hobbyist FFT user.

Fourier Transform Table

Don't look at this until you've learned some though or your head will explode :)

Quote:

Original post by alvaro Quote: Original post by LessBread The college course to start with ought to be Differential Equations. I completely disagree. FFTs arise much more naturally in signal processing.

Then you completely disagree with the professors at MIT too.

"The prerequisite for 6.003 is 6.002. Note also that the prerequisites for 6.002 are 18.03 or 18.06."

The prerequisites for 6.002 are 8.02, 8.022, and 18.03. [1]

18.03 Differential Equations

---

CDProp

Unfortunately, you will need some calculus too.

"18.02 or 18.022 or 18.023 or 18.024 (corequisite), 18.01 or 18.014 (prerequisite)." [2]

18.01 Single Variable Calculus

18.02 Multivariable Calculus

Quote:

Then you completely disagree with the professors at MIT too. "The prerequisite for 6.003 is 6.002. Note also that the prerequisites for 6.002 are 18.03 or 18.06 (Linear Algebra)."

Sure it might be helpful to know, but what's started out as learning about FFT has now transformed into an entire year's worth of MIT coursework :P

If you're writing a doctoral thesis about FFT algorithms you might need DiffEq, for the hobbyist dabbler it seems like overkill. I know I originally linked these courses but I'm getting skeptical that you'll be able to pull enough from just lecture notes to understand what's going on without a book or professor. But anyway just jump in at whatever level you want and see what you can make sense of.

Best of luck :)

Quote:

Original post by karwosts Quote: Then you completely disagree with the professors at MIT too. "The prerequisite for 6.003 is 6.002. Note also that the prerequisites for 6.002 are 18.03 or 18.06 (Linear Algebra)." Sure it might be helpful to know, but what's started out as learning about FFT has now transformed into an entire year's worth of MIT coursework :P If you're writing a doctoral thesis about FFT algorithms you might need DiffEq, for the hobbyist dabbler it seems like overkill. I know I originally linked these courses but I'm getting skeptical that you'll be able to pull enough from just lecture notes to understand what's going on without a book or professor. But anyway just jump in at whatever level you want and see what you can make sense of. Best of luck :)

I agree. In fact, we (not MIT) learned about FT before DEQ:s. Not FFT, but AFAIK that's just numerical evaluation (sorry for the fishy terms) of FT.
As I recall, it was the opposite: some types of DEQ:s require FT for the solution (again, not FFT). FT itself is a pretty easy and straightforward stuff.

Quote:

Original post by karwosts Quote: Then you completely disagree with the professors at MIT too. "The prerequisite for 6.003 is 6.002. Note also that the prerequisites for 6.002 are 18.03 or 18.06 (Linear Algebra)." Sure it might be helpful to know, but what's started out as learning about FFT has now transformed into an entire year's worth of MIT coursework :P

It really depends on how well he wants to know the subject. You pointed him to a table of equations containing various integrals and said that should be sufficient for the hobbyist, but if the hobbyist doesn't know what an integral is those equations will be useless.

Quote:

Original post by karwosts If you're writing a doctoral thesis about FFT algorithms you might need DiffEq, for the hobbyist dabbler it seems like overkill. I know I originally linked these courses but I'm getting skeptical that you'll be able to pull enough from just lecture notes to understand what's going on without a book or professor. But anyway just jump in at whatever level you want and see what you can make sense of.

I agree that a professor is necessary, or at least helpful, but I disagree with your doctoral thesis remark. Ultimately it depends on how much you want to know about the black box and if you don't want to know anything, then use an FFT that someone else has already rolled.

---

Coda:

"FFTs arise much more naturally in signal processing."

I don't disagree with this. I would point out that while signals are real, signal processing is largely an adaptation of very abstract mathematical formulas and operations. Digitized oscillations, repeatable, reproduceable vibrations... sampling, complex numbers, trigonometry, roots of unity, matrix transforms... Start with the signals course. See how far you get. If you get lost, start along on the requisite path with the goal of catching up to the subject matter you're working with. Otherwise, have fun whatever you do.



[Edited by - LessBread on June 2, 2010 5:29:20 PM]

The way to understand Fourier transforms is to understand changes of basis in a Hilbert space. And the way to understand that is to start with finite-dimensional vector spaces. That's plain old linear algebra.

Sure, Fourier transforms come up in a course about differential equations, but frankly in that context they're just a stepping stone to the Laplace transform, which is itself not so much "understood" as "used" in most courses. There's no geometric intuition; there it's just the manipulation of polynomials.

The Fourier transform also comes up in a course on PDEs, but again, the fact that the Fourier basis happens to be the eigenvectors of the Laplacian operator is just incidental. Moreover, this itself is best understood by starting with the finite-dimensional case: eigenvectors and eigenvalues of a matrix.

In the end, it's just a change of basis.

This said, the choice of basis has a few special properties which should be understood:
1 - The convolution theorem. (A BIG DEAL!)
2 - Fourier translation, dilation, and modulation theorems.
2 - The relationship between the DFT, the FT, sampling, and aliasing.
For these, the standard text in ECE curriculums is Oppenheim & Schafer.

I gave a short presentation on fast Fourier transforms and their applications in image processing in my math senior seminar class, and if you're only interested in discrete Fourier transforms and doing them quickly it's really NOT necessary to understand differential equations. Granted I was first exposed to Euler's formula and Fourier series in a differential equations class, but when it comes right down to it you don't even need Fourier Series to understand discrete Fourier transforms.

The basic idea of discrete Fourier transforms is to use the nice properties of exponents along with Euler's formula to apply those nice properties to finding a frequency domain representation (which is good for processing certain types of stuff). If you apply Euler's formula to the definition you can get a feel for what the numbers in the result actually represent. The problem arises in that calculating the transform with the definition is really really slow O(n^2), and that's where the fast Fourier transform comes in. There may be multiple FFT algorithms so I'd like to clarify when I say FFT I'm referring to the Cooley-Tukey algorithm (good search term).

It's been a while, but as I recall the main trick is realizing that there is a relationship between the transforms of the even and odd elements and the full sequence. So to calculate an FFT you first calculate the FFT of the even and odd sequence and then recombining them into the final FFT resulting in an O(n log n) time. As it turns out exponential terms (aka Twiddle Factors) that come up in this recursive FFTing are very redundant, and they can be calculated in advance (or as you go) and stored reducing the main loop to additions and multiplications of complex numbers(as opposed to trig functions needed to handle imaginary exponents). If you're working on multidimensional data (like I worked on images) all of the dimensions can be handled separately, and that's pretty easy to show by just rearranging the DFT definition. You don't necessarily need to understand the deep meaning of everything to understand why and how DFTs work and the FFT is basically just some clever observations about the redundancy present in the definition of the DFT.

www.alrecenk.com/stuff/fourierpresentation.ppt

I put my old presentation online, but unfortunately I did a lot of blackboard work and I don't have scans of my notes. It may not be all that helpful without the accompanying lecture. I can also help you out with code if you'd like to take a look at some as I'm one of the few people crazy enough to write fully optimized FFT code from scratch.....Which begs the question "Do you really need to understand how FFTs work to accomplish what you're trying to do?". Most people I know just use matlab or get an implementation off the internet. I mostly did it as an academic exercise.

There is no need to learn differential equations to understand fourier transforms. The connection between the two subjects is that the fourier transform diagonalizes certain differential operators. The MIT system probably has a series of courses of increasing difficulty, planned to be taken in succession, and they put Diff eq as a prerequisite just to make sure that student entering the course have sufficient mathematical maturity.