Hi everyone. Im starting to study the fast fourier transform. i´ve seen the patches in the examples that come in PD. I have two quesions: I see and understand what the Hanning window does. But why is ti necesary? and how is it related with the samplerate?
thanks
mami music wrote:
Hi everyone. Im starting to study the fast fourier transform. iŽve seen the patches in the examples that come in PD. I have two quesions: I see and understand what the Hanning window does. But why is ti necesary?
The DFT (and FFT implementation thereof) assumes each block is a periodic waveform with period=blocksize that continues forever in both directions.
In general the signal will contain components that don't fit that period exactly, so when they repeat you get glitches (unwanted frequencies).
So, you window to make the signal go to zero at both ends of the block so that it loops without glitches, but that loses information from the ends of the block, so you then overlap blocks to spread the losses between blocks, so on average you lose no information.
Has anyone made an example patch that explains this? Something like a simple FFT filter with switchable windows, so you can hear the difference?
Claude
Has anyone made an example patch that explains this? Something like a simple FFT filter with switchable windows, so you can hear the difference?
Actually anything (links, explanations, etc) that explains or details FFT as it relates to Pd would be great... the example patches are a bit cryptic, or sometimes jump a bit too quickly, at least for me. I want to eventually generate visuals based on obtaining frequency data from sound, but I just couldn't get my mind around fft~, rfft~ etc. so I am going cheap using bandpass filters now which is not really what I wanted. (Sidenote - does anyone know how other artists are accomplishing this? I assumed they were using FFT)
I know this is a fairly advanced topic but I'd really love to figure out how to make it work.
Glad this came up!! Kevin
On 9/4/06, Kevin McCoy km.takewithyou@gmail.com wrote:
Has anyone made an example patch that explains this? Something like a simple FFT filter with switchable windows, so you can hear the difference?
Actually anything (links, explanations, etc) that explains or details FFT as it relates to Pd would be great... the example patches are a bit cryptic, or sometimes jump a bit too quickly, at least for me. I want to eventually generate visuals based on obtaining frequency data from sound, but I just couldn't get my mind around fft~, rfft~ etc. so I am going cheap using bandpass filters now which is not really what I wanted. (Sidenote - does anyone know how other artists are accomplishing this? I assumed they were using FFT)
I know this is a fairly advanced topic but I'd really love to figure out how to make it work.
The explanation that did it best for me is in R.W. Hamming's 'Digital Filters', a pretty dense book (not for beginners like me, but cross referencing this book with Miller Puckette's- http://www-crca.ucsd.edu/~msp/techniques.htm - helped me make sense of some of it). Hamming explains that, if you take any two harmonically related sines or cosines, or one of each, or one of them and a zero-frequency component, then multiply the two functions over a full period, it will integrate to zero; meaning that the sums of all the positive values minus the sums of the negative values is zero. His explanation is more accurate, but confusing nonetheless. The only time the result isn't zero is if you are multiplying a sine or cosine or a zero-frequency part by itself at the same frequency.
This means that, since any function is theoretically the sum of an infinite number of sines and cosines, if you multiply either a sine or a cosine of a certain frequency by any function, the integral of the result will be exactly zero for every harmonically related frequency except the one you multiplied by, so the integral of this product tells you how strong the particular sine or cosine is in the total.
I'm probably leaving out a lot, and I might be downright wrong about something. But having some sort of intuitive understanding seems to be the only way I can use any tool without feeling like it's magic.
If you did a FFT with a block size larger than an entire audio file, as I understand it, you wouldn't need a window. Looping Martin Luther King's "I Have a Dream" speech (or the audio from the second season of CHIPS, or a recording of penguins in their natural habitat) over and over with a 30-minute pause between each round would technically be a "periodic function", so analyzing it this way would create an accurate representation; unfortunately, you would have exactly one value for each frequency, which tells you nothing about the frequency content at any point. To analyze changing frequency content, you have to take smaller blocks. Repeating these to make them "periodic functions" means the beginning and end of any one block of sound will run together. If this happens to create a continuous function, great, but the chances of that happening with every block are pretty low (if a block is 64 samples, at 44100 samples per second, and the second season of CHIPS is 23 episodes, that's a lot of blocks). Windowing the input simply forces that part of the function to be continuous, by forcing beginning and end to the same value and direction. To prevent the data from that part of the function from being completely lost, alternating FFTs can be taken with windows in opposite phase.
I don't exactly understand what happens with the result, though. Whether the frequency values are averaged, or whether resynthesis is done with the same overlapping. I also don't understand upsampling/downsampling with the block~ object, but I'm not sure that's related.
-Chuckk
Glad this came up!! Kevin
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
This is a good explanation.
~Kyle
On 9/4/06, Chuckk Hubbard badmuthahubbard@gmail.com wrote:
If you did a FFT with a block size larger than an entire audio file, as I understand it, you wouldn't need a window. Looping Martin Luther King's "I Have a Dream" speech (or the audio from the second season of CHIPS, or a recording of penguins in their natural habitat) over and over with a 30-minute pause between each round would technically be a "periodic function", so analyzing it this way would create an accurate representation; unfortunately, you would have exactly one value for each frequency, which tells you nothing about the frequency content at any point. To analyze changing frequency content, you have to take smaller blocks. Repeating these to make them "periodic functions" means the beginning and end of any one block of sound will run together. If this happens to create a continuous function, great, but the chances of that happening with every block are pretty low (if a block is 64 samples, at 44100 samples per second, and the second season of CHIPS is 23 episodes, that's a lot of blocks). Windowing the input simply forces that part of the function to be continuous, by forcing beginning and end to the same value and direction. To prevent the data from that part of the function from being completely lost, alternating FFTs can be taken with windows in opposite phase.
I don't exactly understand what happens with the result, though. Whether the frequency values are averaged, or whether resynthesis is done with the same overlapping. I also don't understand upsampling/downsampling with the block~ object, but I'm not sure that's related.
-Chuckk
Glad this came up!! Kevin
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-- "Far and away the best prize that life has to offer is the chance to work hard at work worth doing." -Theodore Roosevelt
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On Mon, 4 Sep 2006, Chuckk Hubbard wrote:
His explanation is more accurate, but confusing nonetheless. The only time the result isn't zero is if you are multiplying a sine or cosine or a zero-frequency part by itself at the same frequency.
The explanation that works for me is that in the complex plane a sine or cosine wave is the average of two points spinning around the origin, one counterclockwise (positive speed) and one clockwise (negative speed). When multiplying two sines or cosines, you are averaging all products of their components, a component being something that travels in a perfect circle around the origin. The product of two components is a component and it spins at a speed which is the sum of the two speeds.
I believe that some things about waves are easier to understand using trajectories in the complex plane than by ordinary graphs of real numbers.
Here's an example of multiplying two cosines algebraically. While you read it you may imagine trajectories and average positions and stuff.
cos(at) = (exp(+ait) + exp(-bit))/2 cos(bt) = (exp(+bit) + exp(-bit))/2 cos(at)cos(bt) = ( exp((+a+b)it) + exp((+a-b)it) + exp((-a+b)it) + exp((-a-b)it)) /4 = ( cos((a+b)t) + cos((a-b)t)) /2
Then what can make the integral non-zero is that it contains a zero-frequency which is because the result contains a frequency a-b but a=b.
Another neat trick for visualizing is that the integral is proportional to the average position of a point over some time.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju | Freelance Digital Arts Engineer, Montréal QC Canada
-
Chuckk Hubbard -
Claude Heiland-Allen -
Kevin McCoy -
Kyle Klipowicz -
mami music -
Mathieu Bouchard