Forums

FFT Questions

Started by Raeldor July 25, 2010
Hi Guys,

I want to use FFT for an audio programming project I'm working on and
had some (what are probably quite simple questions).  I understand the
concept that FFT converts a time based array of data into a frequency
based array of data, and I found a nice library called FFTW which
looks like it will fit the bill.  My questions are...

(These questions are based on an input array of 16-bit integers
representing amplitude between -16,384 and 16,384, with a sample rate
of 22k).

1. I understand with a 22k sample rate, my highest frequency is 10k,
is that correct?

2. If I pass to the FFT routine a set of samples from this data with a
length of 2048, I will get back 2048 values.  a) Will the values still
be in the range -16,384 to 16,384, and will they still represent
amplitude?  If so, how can a frequency have a negative amplitude...
surely if the frequency is not present it should be zero.  b) What
frequency range will each returned sample represent and what are the
upper and lower bounds of the entire returned set of data?  Is this
based on the number of samples I pass into the FFT function?

Thanks
Ray
On 07/24/2010 09:57 PM, Raeldor wrote:
> Hi Guys, > > I want to use FFT for an audio programming project I'm working on and > had some (what are probably quite simple questions). I understand the > concept that FFT converts a time based array of data into a frequency > based array of data, and I found a nice library called FFTW which > looks like it will fit the bill. My questions are... > > (These questions are based on an input array of 16-bit integers > representing amplitude between -16,384 and 16,384, with a sample rate > of 22k). > > 1. I understand with a 22k sample rate, my highest frequency is 10k, > is that correct?
http://www.wescottdesign.com/articles/Sampling/sampling.html
> 2. If I pass to the FFT routine a set of samples from this data with a > length of 2048, I will get back 2048 values.
> a) Will the values still be in the range -16,384 to 16,384, Probably not, but it depends on exactly how FFTW scales its answers -- there's more than one 'standard' way.
> and will they still represent amplitude?
Kinda sorta. They'll be phasors (complex numbers) from which you can extract the amplitude and phase.
> If so, how can a frequency have a negative amplitude... > surely if the frequency is not present it should be zero.
You are confusing "frequency" with "signal content at a frequency". If the phase of the signal in that frequency bin is 180 degrees away from the reference phase for the FFT then the number in the bin will be purely negative.
> b) What frequency range will each returned sample represent
That's more complicated than you'd like to know. Roughly, each bin will be the result of passing your signal through a bandpass filter that's centered on the bin frequency, has a sin(f)/f (sinc(f)), and has a width that depends on the number of samples.
> and what are the upper and lower bounds of the entire returned set of data?
The bins range from f = 0 to f = 22kHz * (1 - 1/2048), or from f = -11kHz to f = 22kHz * (1/2 - 1/2048), or both of the above, depending on how you want to look at things.
> Is this based on the number of samples I pass into the FFT function?
The frequency range always loops through the sample frequency (i.e. FFT a signal taken at 22kHz and you'll get bins spanning 22kHz). The frequency resolution goes up as the length of the signal you take the FFT of increases. Yes, my responses sound like I'm jerking you around. That's a very little bit because it's late and I'm about to shut down for the night, so I'm not bothering to be diplomatic. But it's mostly because there's a whole lot of nit picky details that you get into when you try to apply the FFT and be 100% correct. Fortunately, for many applications you can get by with being 90% correct, and for that you can learn a lot by experimentation. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Raeldor <raeldor@gmail.com> wrote:
 
> I want to use FFT for an audio programming project I'm working on and > had some (what are probably quite simple questions). I understand the > concept that FFT converts a time based array of data into a frequency > based array of data, and I found a nice library called FFTW which > looks like it will fit the bill. My questions are...
Well, read Tim's answers, but in addition...
> (These questions are based on an input array of 16-bit integers > representing amplitude between -16,384 and 16,384, with a sample rate > of 22k).
You mean -16384 and +16383, right?
> 1. I understand with a 22k sample rate, my highest frequency is 10k, > is that correct?
With practical filters, that is probably about right.
> 2. If I pass to the FFT routine a set of samples from this data with a > length of 2048, I will get back 2048 values. a) Will the values still > be in the range -16,384 to 16,384, and will they still represent > amplitude?
Well they will, but there might have been some scaling along the way. The FFT could be done with additional bits for each bin, though, and a bin could be (but isn't likely to be) up to 2048*16384. (that is, -2048*-16384)
> If so, how can a frequency have a negative amplitude... > surely if the frequency is not present it should be zero. b) What > frequency range will each returned sample represent and what are the > upper and lower bounds of the entire returned set of data? Is this > based on the number of samples I pass into the FFT function?
If cos(x) has positive amplitude, then -cos(x) has negative amplitude, and sin(x) has imaginary amplitude. The way the math is supposed to work, the FFT has periodic boundary conditions. That is, the basis functions are all peridic in the length of the transform input. The 0th bin (1st bin for Fortran programmers) is the 0Hz or DC bin. The next one is one cycle over the tranform length. In the case of 2048 points it is 1/2048 of the sampling frequency. Successive bins represent successively higher frequencies, Fs*2/2048, Fs*3/2048, ... and again are periodic. The usual interpretation is that the high half of the transform represents negative frequencies, from -Fs/2 up to -Fs/2048, but, due to aliasing, they can also be considered as going from Fs/2 up to Fs*2047/2048. -- glen

Raeldor wrote:

> Hi Guys, > > I want to use FFT for an audio programming project I'm working on and > had some (what are probably quite simple questions). I understand the > concept that FFT converts a time based array of data into a frequency > based array of data, and I found a nice library called FFTW which > looks like it will fit the bill. My questions are... > > (These questions are based on an input array of 16-bit integers > representing amplitude between -16,384 and 16,384, with a sample rate > of 22k). > > 1. I understand with a 22k sample rate, my highest frequency is 10k, > is that correct? > > 2. If I pass to the FFT routine a set of samples from this data with a > length of 2048, I will get back 2048 values. a) Will the values still > be in the range -16,384 to 16,384, and will they still represent > amplitude? If so, how can a frequency have a negative amplitude... > surely if the frequency is not present it should be zero. b) What > frequency range will each returned sample represent and what are the > upper and lower bounds of the entire returned set of data? Is this > based on the number of samples I pass into the FFT function? > > Thanks > Ray

Troll:-

Subject: IMBECILE::Re: FFT Questions








> > > Raeldor wrote: > >> Hi Guys, >> >> I want to use FFT for an audio programming project I'm working on and >> had some (what are probably quite simple questions). I understand the >> concept that FFT converts a time based array of data into a frequency >> based array of data, and I found a nice library called FFTW which >> looks like it will fit the bill. My questions are... >> >> (These questions are based on an input array of 16-bit integers >> representing amplitude between -16,384 and 16,384, with a sample rate >> of 22k). >> >> 1. I understand with a 22k sample rate, my highest frequency is 10k, >> is that correct? >> >> 2. If I pass to the FFT routine a set of samples from this data with a >> length of 2048, I will get back 2048 values. a) Will the values still >> be in the range -16,384 to 16,384, and will they still represent >> amplitude? If so, how can a frequency have a negative amplitude... >> surely if the frequency is not present it should be zero. b) What >> frequency range will each returned sample represent and what are the >> upper and lower bounds of the entire returned set of data? Is this >> based on the number of samples I pass into the FFT function? >> >> Thanks >> Ray
On Jul 24, 10:29&#2013266080;pm, Tim Wescott <t...@seemywebsite.com> wrote:
> On 07/24/2010 09:57 PM, Raeldor wrote: > > > Hi Guys, > > > I want to use FFT for an audio programming project I'm working on and > > had some (what are probably quite simple questions). &#2013266080;I understand the > > concept that FFT converts a time based array of data into a frequency > > based array of data, and I found a nice library called FFTW which > > looks like it will fit the bill. &#2013266080;My questions are... > > > (These questions are based on an input array of 16-bit integers > > representing amplitude between -16,384 and 16,384, with a sample rate > > of 22k). > > > 1. I understand with a 22k sample rate, my highest frequency is 10k, > > is that correct? > > http://www.wescottdesign.com/articles/Sampling/sampling.html > > > 2. If I pass to the FFT routine a set of samples from this data with a > > length of 2048, I will get back 2048 values. > > &#2013266080;> a) Will the values still be in the range -16,384 to 16,384, > > Probably not, but it depends on exactly how FFTW scales its answers -- > there's more than one 'standard' way. > > > and will they still represent amplitude? > > Kinda sorta. &#2013266080;They'll be phasors (complex numbers) from which you can > extract the amplitude and phase. > > > If so, how can a frequency have a negative amplitude... > > surely if the frequency is not present it should be zero. > > You are confusing "frequency" with "signal content at a frequency". &#2013266080;If > the phase of the signal in that frequency bin is 180 degrees away from > the reference phase for the FFT then the number in the bin will be > purely negative. > > > b) What frequency range will each returned sample represent > > That's more complicated than you'd like to know. &#2013266080;Roughly, each bin will > be the result of passing your signal through a bandpass filter that's > centered on the bin frequency, has a sin(f)/f (sinc(f)), and has a width > that depends on the number of samples. > > > and what are the upper and lower bounds of the entire returned set of data? > > The bins range from f = 0 to f = 22kHz * (1 - 1/2048), or from f = > -11kHz to f = 22kHz * (1/2 - 1/2048), or both of the above, depending on > how you want to look at things. > > > Is this based on the number of samples I pass into the FFT function? > > The frequency range always loops through the sample frequency (i.e. FFT > a signal taken at 22kHz and you'll get bins spanning 22kHz). &#2013266080;The > frequency resolution goes up as the length of the signal you take the > FFT of increases. > > Yes, my responses sound like I'm jerking you around. &#2013266080;That's a very > little bit because it's late and I'm about to shut down for the night, > so I'm not bothering to be diplomatic. &#2013266080;But it's mostly because there's > a whole lot of nit picky details that you get into when you try to apply > the FFT and be 100% correct. > > Fortunately, for many applications you can get by with being 90% > correct, and for that you can learn a lot by experimentation. > > -- > > Tim Wescott > Wescott Design Serviceshttp://www.wescottdesign.com > > Do you need to implement control loops in software? > "Applied Control Theory for Embedded Systems" was written for you. > See details athttp://www.wescottdesign.com/actfes/actfes.html
Hi, Thank you both for your explanations. Looks like i have some more reading to do! :) Is there a standard formula to convert the returned values into decibels? All I'm really looking to get out of this is a pretty good approximation of 'loudness' of frequencies within each band returned. I was hoping it wouldn't be too difficult, but now I'm hearing about 'phasors' which I always thought was what captain kirk carried to shoot aliens. Thanks Ray
On 07/26/2010 01:07 PM, Raeldor wrote:
> On Jul 24, 10:29 pm, Tim Wescott<t...@seemywebsite.com> wrote: >> On 07/24/2010 09:57 PM, Raeldor wrote: >> >>> Hi Guys, >> >>> I want to use FFT for an audio programming project I'm working on and >>> had some (what are probably quite simple questions). I understand the >>> concept that FFT converts a time based array of data into a frequency >>> based array of data, and I found a nice library called FFTW which >>> looks like it will fit the bill. My questions are... >> >>> (These questions are based on an input array of 16-bit integers >>> representing amplitude between -16,384 and 16,384, with a sample rate >>> of 22k). >> >>> 1. I understand with a 22k sample rate, my highest frequency is 10k, >>> is that correct? >> >> http://www.wescottdesign.com/articles/Sampling/sampling.html >> >>> 2. If I pass to the FFT routine a set of samples from this data with a >>> length of 2048, I will get back 2048 values. >> >> > a) Will the values still be in the range -16,384 to 16,384, >> >> Probably not, but it depends on exactly how FFTW scales its answers -- >> there's more than one 'standard' way. >> >>> and will they still represent amplitude? >> >> Kinda sorta. They'll be phasors (complex numbers) from which you can >> extract the amplitude and phase. >> >>> If so, how can a frequency have a negative amplitude... >>> surely if the frequency is not present it should be zero. >> >> You are confusing "frequency" with "signal content at a frequency". If >> the phase of the signal in that frequency bin is 180 degrees away from >> the reference phase for the FFT then the number in the bin will be >> purely negative. >> >>> b) What frequency range will each returned sample represent >> >> That's more complicated than you'd like to know. Roughly, each bin will >> be the result of passing your signal through a bandpass filter that's >> centered on the bin frequency, has a sin(f)/f (sinc(f)), and has a width >> that depends on the number of samples. >> >>> and what are the upper and lower bounds of the entire returned set of data? >> >> The bins range from f = 0 to f = 22kHz * (1 - 1/2048), or from f = >> -11kHz to f = 22kHz * (1/2 - 1/2048), or both of the above, depending on >> how you want to look at things. >> >>> Is this based on the number of samples I pass into the FFT function? >> >> The frequency range always loops through the sample frequency (i.e. FFT >> a signal taken at 22kHz and you'll get bins spanning 22kHz). The >> frequency resolution goes up as the length of the signal you take the >> FFT of increases. >> >> Yes, my responses sound like I'm jerking you around. That's a very >> little bit because it's late and I'm about to shut down for the night, >> so I'm not bothering to be diplomatic. But it's mostly because there's >> a whole lot of nit picky details that you get into when you try to apply >> the FFT and be 100% correct. >> >> Fortunately, for many applications you can get by with being 90% >> correct, and for that you can learn a lot by experimentation. >> >> -- >> >> Tim Wescott >> Wescott Design Serviceshttp://www.wescottdesign.com >> >> Do you need to implement control loops in software? >> "Applied Control Theory for Embedded Systems" was written for you. >> See details athttp://www.wescottdesign.com/actfes/actfes.html > > Hi, > > Thank you both for your explanations. Looks like i have some more > reading to do! :) Is there a standard formula to convert the returned > values into decibels?
Yes. The FFT returns complex numbers (or phasors, depending on where you learned this stuff). For your purposes, they're a number pair (a, b), where the estimated signal for that particular frequency bin is a * cos(w*t) + b * sin(w*t), w = 2 * pi * frequency. The magnitude of the signal is sqrt(a^2 + b^2); to convert that to Decibels you need to take the logarithm to the base 10 of the magnitude, and multiply by 20, then add a constant to take the effect of all the gains in your system into account: mag(dB) = 20 * log(sqrt(a^2 + b^2)), or if you know your logarithms: mag(dB) = 10 * log(a^2 + b^2).
> All I'm really looking to get out of this is a > pretty good approximation of 'loudness' of frequencies within each > band returned. I was hoping it wouldn't be too difficult, but now I'm > hearing about 'phasors' which I always thought was what captain kirk > carried to shoot aliens.
-- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
On Jul 26, 1:07&#2013266080;pm, Raeldor <rael...@gmail.com> wrote:
> On Jul 24, 10:29&#2013266080;pm, Tim Wescott <t...@seemywebsite.com> wrote: > > > > > > > On 07/24/2010 09:57 PM, Raeldor wrote: > > > > Hi Guys, > > > > I want to use FFT for an audio programming project I'm working on and > > > had some (what are probably quite simple questions). &#2013266080;I understand the > > > concept that FFT converts a time based array of data into a frequency > > > based array of data, and I found a nice library called FFTW which > > > looks like it will fit the bill. &#2013266080;My questions are... > > > > (These questions are based on an input array of 16-bit integers > > > representing amplitude between -16,384 and 16,384, with a sample rate > > > of 22k). > > > > 1. I understand with a 22k sample rate, my highest frequency is 10k, > > > is that correct? > > >http://www.wescottdesign.com/articles/Sampling/sampling.html > > > > 2. If I pass to the FFT routine a set of samples from this data with a > > > length of 2048, I will get back 2048 values. > > > &#2013266080;> a) Will the values still be in the range -16,384 to 16,384, > > > Probably not, but it depends on exactly how FFTW scales its answers -- > > there's more than one 'standard' way. > > > > and will they still represent amplitude? > > > Kinda sorta. &#2013266080;They'll be phasors (complex numbers) from which you can > > extract the amplitude and phase. > > > > If so, how can a frequency have a negative amplitude... > > > surely if the frequency is not present it should be zero. > > > You are confusing "frequency" with "signal content at a frequency". &#2013266080;If > > the phase of the signal in that frequency bin is 180 degrees away from > > the reference phase for the FFT then the number in the bin will be > > purely negative. > > > > b) What frequency range will each returned sample represent > > > That's more complicated than you'd like to know. &#2013266080;Roughly, each bin will > > be the result of passing your signal through a bandpass filter that's > > centered on the bin frequency, has a sin(f)/f (sinc(f)), and has a width > > that depends on the number of samples. > > > > and what are the upper and lower bounds of the entire returned set of data? > > > The bins range from f = 0 to f = 22kHz * (1 - 1/2048), or from f = > > -11kHz to f = 22kHz * (1/2 - 1/2048), or both of the above, depending on > > how you want to look at things. > > > > Is this based on the number of samples I pass into the FFT function? > > > The frequency range always loops through the sample frequency (i.e. FFT > > a signal taken at 22kHz and you'll get bins spanning 22kHz). &#2013266080;The > > frequency resolution goes up as the length of the signal you take the > > FFT of increases. > > > Yes, my responses sound like I'm jerking you around. &#2013266080;That's a very > > little bit because it's late and I'm about to shut down for the night, > > so I'm not bothering to be diplomatic. &#2013266080;But it's mostly because there's > > a whole lot of nit picky details that you get into when you try to apply > > the FFT and be 100% correct. > > > Fortunately, for many applications you can get by with being 90% > > correct, and for that you can learn a lot by experimentation. > > > -- > > > Tim Wescott > > Wescott Design Serviceshttp://www.wescottdesign.com > > > Do you need to implement control loops in software? > > "Applied Control Theory for Embedded Systems" was written for you. > > See details athttp://www.wescottdesign.com/actfes/actfes.html > > Hi, > > Thank you both for your explanations. &#2013266080;Looks like i have some more > reading to do! :) &#2013266080;Is there a standard formula to convert the returned > values into decibels? &#2013266080;All I'm really looking to get out of this is a > pretty good approximation of 'loudness' of frequencies within each > band returned. &#2013266080;I was hoping it wouldn't be too difficult, but now I'm > hearing about 'phasors' which I always thought was what captain kirk > carried to shoot aliens. > > Thanks > Ray
In fact, to qualify further it doesn't even really need to be decibels. Any unit that represents the loudness of a frequency range against the others in the sample range is fine. Thanks Ray
On 7/26/2010 4:43 PM, Tim Wescott wrote:
> On 07/26/2010 01:07 PM, Raeldor wrote:
...
>> Thank you both for your explanations. Looks like i have some more >> reading to do! :) Is there a standard formula to convert the returned >> values into decibels? > > Yes. The FFT returns complex numbers (or phasors, depending on where you > learned this stuff). For your purposes, they're a number pair (a, b), > where the estimated signal for that particular frequency bin is a * > cos(w*t) + b * sin(w*t), w = 2 * pi * frequency. The magnitude of the > signal is sqrt(a^2 + b^2); to convert that to Decibels you need to take > the logarithm to the base 10 of the magnitude, and multiply by 20, then > add a constant to take the effect of all the gains in your system into > account: > > mag(dB) = 20 * log(sqrt(a^2 + b^2)), or if you know your logarithms: > mag(dB) = 10 * log(a^2 + b^2).
Plus an additive constant to set the scale. When the constant is zero, a^2 + b^2 = 1 becomes 0 dB. Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
On Jul 25, 4:09&#2013266080;am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Raeldor <rael...@gmail.com> wrote: > > I want to use FFT for an audio programming project I'm working on and > > had some (what are probably quite simple questions). &#2013266080;I understand the > > concept that FFT converts a time based array of data into a frequency > > based array of data, and I found a nice library called FFTW which > > looks like it will fit the bill. &#2013266080;My questions are... > > Well, read Tim's answers, but in addition... > > > (These questions are based on an input array of 16-bit integers > > representing amplitude between -16,384 and 16,384, with a sample rate > > of 22k). > > You mean -16384 and +16383, right? > > > 1. I understand with a 22k sample rate, my highest frequency is 10k, > > is that correct? > > With practical filters, that is probably about right. > > > 2. If I pass to the FFT routine a set of samples from this data with a > > length of 2048, I will get back 2048 values. &#2013266080;a) Will the values still > > be in the range -16,384 to 16,384, and will they still represent > > amplitude? &#2013266080; > > Well they will, but there might have been some scaling along > the way. &#2013266080;The FFT could be done with additional bits for each > bin, though, and a bin could be (but isn't likely to be) up > to 2048*16384. &#2013266080;(that is, -2048*-16384)
If you only added the 11 bits for the 2048, then 2048*16384 would overflow. You also need to be careful that when the real and imag parts fall in the representable range, the magnitude may not, and scaling may have to be put in to accomodate the problem. Dirk
> > > If so, how can a frequency have a negative amplitude... > > surely if the frequency is not present it should be zero. &#2013266080;b) What > > frequency range will each returned sample represent and what are the > > upper and lower bounds of the entire returned set of data? &#2013266080;Is this > > based on the number of samples I pass into the FFT function? > > If cos(x) has positive amplitude, then -cos(x) has negative > amplitude, and sin(x) has imaginary amplitude. > > The way the math is supposed to work, the FFT has periodic > boundary conditions. &#2013266080;That is, the basis functions are all > peridic in the length of the transform input. &#2013266080;The 0th bin > (1st bin for Fortran programmers) is the 0Hz or DC bin. > The next one is one cycle over the tranform length. &#2013266080;In the > case of 2048 points it is 1/2048 of the sampling frequency. > Successive bins represent successively higher frequencies, > Fs*2/2048, Fs*3/2048, ... &#2013266080;and again are periodic. &#2013266080; > The usual interpretation is that the high half of the > transform represents negative frequencies, from -Fs/2 up > to -Fs/2048, but, due to aliasing, they can also > be considered as going from Fs/2 up to Fs*2047/2048. > > -- glen