Fourier transform for dummies
-
- KVRian
- 1349 posts since 12 Jan, 2003 from Paris
It's very well explained in this book which is freely available in PDF version :
http://www.dspguide.com/pdfbook.htm
Chapter 8 and following...
Xavier
http://www.dspguide.com/pdfbook.htm
Chapter 8 and following...
Xavier
-
- KVRist
- Topic Starter
- 132 posts since 23 Jul, 2004 from Sweden
Yeah, thanks a lot, i've already had a look at that book, but i was looking for a more concrete explanation without so much details (if that's possible?). I mean, just the essential basics and some examples.
-
- KVRist
- 42 posts since 23 Nov, 2002
Maybe http://www.dspdimension.com/html/tutorials.html will help!
Henke wrote:Could anyone please explain the Fourier transform in an understandlable way to a dsp-newbie?
(I know complex maths)
- u-he
- 28065 posts since 8 Aug, 2002 from Berlin
The fourier transform converts a time representation ( samples ) into a frequency representation ( i.e. the frequency spectrum of these samples ) and vice versa.
Commonly it splits a number of audio samples, say 2048, into a corresponding number of sine waves of different frequencies, so that you know the volumes and the phase for each sine.
The principle is very simple:
If you multiply a set of samples with another set of reference samples and add each result, like this:
result = sample[ 0 ] * reference[ 0 ] + sample[ 1 ] * reference[ 1 ] + ... + sample[ n ] * reference[ n ]
... the result is an indicator for the similarity of both sets of samples.
And now with sines
Now, if you want to know the volume and the phase of a sine at a certain frequency inside an audio sample, you have to calculate 2 of these similarity values:
FC = 2 * PI * frequency / samplerate; // "frequency constant"
result_i = sample[ 0 ] * sin( FC * 0.f ) + sample[ 1 ] * sin( FC * 1.f )+ ... + sample[ n ] * sin( FC * n.f )
result_r = sample[ 0 ] * cos( FC * 0.f ) + sample[ 1 ] * cos( FC * 1.f )+ ... + sample[ n ] * cos( FC * n.f )
To get the actual phase and magnitude, you use simple pythagoras to get length and trigonometry to get the angle:
magnitude = sqrt( result_i * result_i + result_r * result_r);
phase = atan2( result_i, result_r) // I think...
This way you can determine how much of a frequency is present in an audio file etc., and which phase it has relative to the beginning.
Complex Numbers?
In Fourier Transform lingo, the sine part is oftenly called "imaginary" while the cosine part is called "rational". They pretend to be complex numbers, but that's more or less only a convention. The phase/magnitude representation IMHO feels more like complex numbers.
Getting the whole spectrum
Now, the idea behind fourier transforms is, if you start with a "fundamental" frequency of exactly 1 cycle over the whole length of the analysed set of samples (call it n samples) and do this with every multiple up to n/2 of the fundamental, you get a representation that thoroughly reflects the spectrum of the original sample. - If you transform it back (create a new bunch of n samples out of adding sines and cosines), it will perfectly fit the original samples!
Each "frequency slot" or multiple of the fundamental (1, 2, 3, ..., n/2) is called a "bin". (Note, there's also a zero-bin, I'll explain that later)
Fast Fourier Transform - FFT
This would be a very time consuming technique, if there wasn't the Fast Fourier Transform, or FFT. The FFT is a simple, yet highly difficult to understand algorithm. It takes advantage of the fact, that if you draw all those sines in a graph, you have many lines that cross each other at certain points. And because they cross each other pretty often, you need only 1 multiply to gather information for many results needed. Hence, what FFT does is recursively reordering ("prepacking", "butterfly") the samples in a tricky way so that only a fraction of calculations are needed to create the spectrum for a given range of audio samples. The drawback is, FFT requires certain lengths (or "ns") of samples, which are a power of 2: like 16, 32, 1024, 4096 samples etc.
DC offset and Nyquist in FFTs
Typically, a FFT outputs the spectrum in sines and cosines, but it also output 2 special values: A cosine representing the DC (offset of powers above zero and below zero), which is bin 0, or the fundamental frequency * 0 and a sine representing Nyquist (because at Nyquist, there can't be a cosine!). Hence some algorithms require N/2+1 bins, others "pack" the Nyquist bin into the sine field of the DC bin.
Hope this helps, or maybe it's a start...
Cheers,
Urs
Commonly it splits a number of audio samples, say 2048, into a corresponding number of sine waves of different frequencies, so that you know the volumes and the phase for each sine.
The principle is very simple:
If you multiply a set of samples with another set of reference samples and add each result, like this:
result = sample[ 0 ] * reference[ 0 ] + sample[ 1 ] * reference[ 1 ] + ... + sample[ n ] * reference[ n ]
... the result is an indicator for the similarity of both sets of samples.
And now with sines
Now, if you want to know the volume and the phase of a sine at a certain frequency inside an audio sample, you have to calculate 2 of these similarity values:
FC = 2 * PI * frequency / samplerate; // "frequency constant"
result_i = sample[ 0 ] * sin( FC * 0.f ) + sample[ 1 ] * sin( FC * 1.f )+ ... + sample[ n ] * sin( FC * n.f )
result_r = sample[ 0 ] * cos( FC * 0.f ) + sample[ 1 ] * cos( FC * 1.f )+ ... + sample[ n ] * cos( FC * n.f )
To get the actual phase and magnitude, you use simple pythagoras to get length and trigonometry to get the angle:
magnitude = sqrt( result_i * result_i + result_r * result_r);
phase = atan2( result_i, result_r) // I think...
This way you can determine how much of a frequency is present in an audio file etc., and which phase it has relative to the beginning.
Complex Numbers?
In Fourier Transform lingo, the sine part is oftenly called "imaginary" while the cosine part is called "rational". They pretend to be complex numbers, but that's more or less only a convention. The phase/magnitude representation IMHO feels more like complex numbers.
Getting the whole spectrum
Now, the idea behind fourier transforms is, if you start with a "fundamental" frequency of exactly 1 cycle over the whole length of the analysed set of samples (call it n samples) and do this with every multiple up to n/2 of the fundamental, you get a representation that thoroughly reflects the spectrum of the original sample. - If you transform it back (create a new bunch of n samples out of adding sines and cosines), it will perfectly fit the original samples!
Each "frequency slot" or multiple of the fundamental (1, 2, 3, ..., n/2) is called a "bin". (Note, there's also a zero-bin, I'll explain that later)
Fast Fourier Transform - FFT
This would be a very time consuming technique, if there wasn't the Fast Fourier Transform, or FFT. The FFT is a simple, yet highly difficult to understand algorithm. It takes advantage of the fact, that if you draw all those sines in a graph, you have many lines that cross each other at certain points. And because they cross each other pretty often, you need only 1 multiply to gather information for many results needed. Hence, what FFT does is recursively reordering ("prepacking", "butterfly") the samples in a tricky way so that only a fraction of calculations are needed to create the spectrum for a given range of audio samples. The drawback is, FFT requires certain lengths (or "ns") of samples, which are a power of 2: like 16, 32, 1024, 4096 samples etc.
DC offset and Nyquist in FFTs
Typically, a FFT outputs the spectrum in sines and cosines, but it also output 2 special values: A cosine representing the DC (offset of powers above zero and below zero), which is bin 0, or the fundamental frequency * 0 and a sine representing Nyquist (because at Nyquist, there can't be a cosine!). Hence some algorithms require N/2+1 bins, others "pack" the Nyquist bin into the sine field of the DC bin.
Hope this helps, or maybe it's a start...
Cheers,
Urs
Last edited by Urs on Wed Feb 23, 2005 7:13 pm, edited 1 time in total.
-
- KVRAF
- 8388 posts since 11 Apr, 2003 from back on the hillside again - but now with a garden!
-
- KVRist
- Topic Starter
- 132 posts since 23 Jul, 2004 from Sweden
Awesome! Thanks a lot for that explanation Urs! I'll have a deeper look into what you said, and try to understand it...
rfreeze: Great link! Thanks mate.
rfreeze: Great link! Thanks mate.
-
- KVRist
- 201 posts since 26 Jan, 2004 from Southside Copenhagen
Damn.. Sounds like you need to be very good at math to make synths.. Im currently learning about matrixes and vectorspaes and it's hard enough..
I admire you developers who understand this kindof math, and also have the ability to program it
I admire you developers who understand this kindof math, and also have the ability to program it
- u-he
- 28065 posts since 8 Aug, 2002 from Berlin
Well, no developer would ever program his own FFT. That's just plain too much voodoo - especially if you want to get a *very* fast implementation.Orbitutle wrote:Damn.. Sounds like you need to be very good at math to make synths.. Im currently learning about matrixes and vectorspaes and it's hard enough..
I admire you developers who understand this kindof math, and also have the ability to program it
Typically, you link to a library, i.e. veclib on MacOS X and just *use* that FFT for your needs.
That veclib was available as source code from Apple once. I looked at it only briefly, and I decided not to look at it again. I'd either get a serious mental disorder or some sort of inferiority complex
Cheers,
Urs
- u-he
- 28065 posts since 8 Aug, 2002 from Berlin
Actually, I've given up that matrixes stuff. I've learned to create rotation matrixes for 3D stuff, but I've never managed to create a serious perspective matrix. The dsp domain is much easier... you only have to deal with modulation matricesOrbitutle wrote:Im currently learning about matrixes and vectorspaes and it's hard enough..
Cheers,
Urs
-
- KVRist
- 32 posts since 23 Feb, 2005
Link to a series of recorded lectures by Strang @ theOrbitutle wrote:Damn.. Sounds like you need to be very good at math to make synths.. Im currently learning about matrixes and vectorspaes and it's hard enough..
I admire you developers who understand this kindof math, and also have the ability to program it
MIT, starting at the basics and moving onto the FFT
Wavlets etc.
http://ocw.mit.edu/OcwWeb/Mathematics/1 ... oLectures/
-
- KVRAF
- 1743 posts since 3 Dec, 2004
the key there is fast implementation,Urs wrote:Well, no developer would ever program his own FFT. That's just plain too much voodoo - especially if you want to get a *very* fast implementation.
The DFT (basis for FFT) algo is a snap & I daresay most people here could write it in just a few lines of code,
its getting a very fast Fast Fourier Transform thats the trick.
-
- KVRAF
- 2279 posts since 20 Dec, 2002 from The Benighted States of Trumpistan
Heh. I felt like that when I looked at your explanation of the FFT process... But hey, my degrees are in English!My spies inform me that Urs wrote:That veclib was available as source code from Apple once. I looked at it only briefly, and I decided not to look at it again. I'd either get a serious mental disorder or some sort of inferiority complex
Wait... loot _then_ burn? D'oh!
- u-he
- 28065 posts since 8 Aug, 2002 from Berlin
hehehe, I never said I could speak English...Jafo wrote:Heh. I felt like that when I looked at your explanation of the FFT process... But hey, my degrees are in English!My spies inform me that Urs wrote:That veclib was available as source code from Apple once. I looked at it only briefly, and I decided not to look at it again. I'd either get a serious mental disorder or some sort of inferiority complex
Anyway, maybe I should slice it in sections so that it feels clearer...
Cheers,
Urs