FFT bin meaning

Started by hyeewang February 10, 2009
This means that the frequencies of all sinusoids we measure will be a
multiple of the inverse of the analysis window length - so if our
�nails� are N samples away, our STFT bins will have a
spacing of
sampleRate/N Hertz. As a result, this concept imposes an artificial
frequency grid on our analysis by requiring the reference frequencies
to be an integer multiple of our signal window in period to make them
seamlessly fit into our analysis frame.

I often see DFT bin in some DFT/stft literature,What does the term
"bin" mean exactly?
Does it refer to a specific single frequency or a frequency range?
If we do N points DFT,then have N DFT bins, where do the 0-bin and N-1
bin refer to?
If N = 256,then where does 112.5 bin refer to?

Thanks.
Hyee
On Feb 10, 10:39&#2013266080;pm, hyeewang <hyeew...@gmail.com> wrote:
> Does it refer to a specific single frequency or a frequency range?
It refers to a frequency range centered at each of the N output points. Coincidentally, the width of the bin is also sample rate/2, and it extends from: center frequency -(sample rate/N)/2 to center frequency +(sample rate/N)/2. In other words, half of the bin extends below each of the N output points, and half above it. So the N output bins from an N point DFT/FFT extend from 0 to N - 1, and each of those bins has a center frequency of n*(sample rate/N), n = 0 to N/2, and (negative frequencies) N/2 + 1 to N - 1. Each bin also extends 1/2 bin width on either side of the center frequency. One thing about DFT/FFT is that if you window your data (Gaussian, etc.,), you are in effect creating N Gaussian filters in the frequency domain, where each one is centered at one of the N outputs. If you're using a different window, or the implied rectangular window on the input, your filter shapes in the frequency domain will be different.
>If we do N points DFT, then have N DFT bins, where do the 0-bin and N-1 >bin refer to?
The bin at 0 is centered at f = 0 and extends from 1 /2 of a bin width in the 'negative' frequency range to 1/2 bin in the positive. The bin at #1 goes from 1/2 to 1 1/2 (center f = 1 in bin numbers). The N - 1 bin, since it represents a negative frequency (-1f), is located exactly to the left of the 0 bin into the negative frequency range. Perhaps the easiest way to see things is to code an example of a simple sinusoid, do a DFT/FFT, then do it again and again with small increases in the frequency of the sinusoid. You&#2013266066;ll see how the output kind of snaps into place when the sinusoid is bin centered, and how two adjacent bins will have equal outputs when the sinusoid is exactly halfway between bins. Someone here has a Java based web site that will do the above, and perhaps they&#2013266066;ll post the link. Kevin
I meant to say: the width of the bin is sample rate/N, not sample rate/
2 in that first paragraph.

And, actually, the bin isn't really a 'brick wall' band pass filter,
but rather, it has a shape that depends on the type of window used
(e.g.: implicit rectangular one, Gaussian, Hann, etc.).

Kevin
hyeewang wrote:
>> I often see DFT bin in some DFT/stft literature,What does the term > "bin" mean exactly?
It probably isn't very *exact* :-) It's a slang term that derives from histogram terminology. If the number falls between 0 and 1 then it goes in "bin" 1, between 1 and 2 then "bin" 2, etc. and, in the end, each such ordered bin has so many counts. In a DFT, there are discrete frequency samples which look like such "bins" in that there's a value at each of the ordered samples. It's how those values end up affecting each sample that's probably more interesting and others have already touched on that part: windows and their Fourier Transforms affect what the values at the samples represent. The simple-minded view (useful for visualization nonetheless) is that frequency components straddling each sample frequency "fall into" that one "bin" value. Fred
On Feb 11, 2:56&#2013266080;pm, kevinjmc...@netscape.net wrote:
> I meant to say: the width of the bin is sample rate/N, not sample rate/ > 2 in that first paragraph. > > And, actually, the bin isn't really a 'brick wall' band pass filter, > but rather, it has a shape that depends on the type of window used > (e.g.: implicit rectangular one, Gaussian, Hann, etc.). > > Kevin
Thank you ... Kevin. You made a clear/great presentation.
Fred Marshall wrote:

> hyeewang wrote: >>>I often see DFT bin in some DFT/stft literature,What does the term >>"bin" mean exactly?
> It probably isn't very *exact* :-)
> It's a slang term that derives from histogram terminology. > If the number falls between 0 and 1 then it goes in "bin" 1, between 1 and 2 > then "bin" 2, etc. and, in the end, each such ordered bin has so many > counts.
> In a DFT, there are discrete frequency samples which look like such "bins" > in that there's a value at each of the ordered samples.
I believe it is worse than that. Some people use the DFT (or FFT) on a segment of non-periodic data. In that case, a range of frequencies will contribute to each DFT frequency. Not really a histogram, though, as the contributions aren't uniform. -- glen
Glen Herrmannsfeldt wrote:
> Fred Marshall wrote: > >> hyeewang wrote: >>>> I often see DFT bin in some DFT/stft literature,What does the term >>> "bin" mean exactly? > >> It probably isn't very *exact* :-) > >> It's a slang term that derives from histogram terminology. >> If the number falls between 0 and 1 then it goes in "bin" 1, between >> 1 and 2 then "bin" 2, etc. and, in the end, each such ordered bin >> has so many counts. > >> In a DFT, there are discrete frequency samples which look like such >> "bins" in that there's a value at each of the ordered samples. > > I believe it is worse than that. Some people use the DFT (or FFT) > on a segment of non-periodic data. In that case, a range of > frequencies will contribute to each DFT frequency. Not really a > histogram, though, as the contributions aren't uniform. > > -- glen
Glen, Indeed. That's why I said the snipped parts: "It's how those values end up affecting each sample that's probably more interesting and others have already touched on that part: windows and their Fourier Transforms affect what the values at the samples represent. The simple-minded view (useful for visualization nonetheless) is that frequency components straddling each sample frequency "fall into" that one "bin" value." Fred
On Feb 11, 1:56 am, kevinjmc...@netscape.net wrote:
> > And, actually, the bin isn't really a 'brick wall' band pass filter, > but rather, it has a shape that depends on the type of window used > (e.g.: implicit rectangular one, Gaussian, Hann, etc.).
On Feb 11, 6:16&#2013266080;am, Glen Herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Fred Marshall wrote: > > hyeewang wrote: > >>>I often see DFT bin in some DFT/stft literature,What does the term > >>"bin" mean exactly? > > It probably isn't very *exact* :-) > > It's a slang term that derives from histogram terminology. > > If the number falls between 0 and 1 then it goes in "bin" 1, between 1 and 2 > > then "bin" 2, etc. and, in the end, each such ordered bin has so many > > counts. > > In a DFT, there are discrete frequency samples which look like such "bins" > > in that there's a value at each of the ordered samples. > > I believe it is worse than that. &#2013266080;Some people use the DFT (or FFT) > on a segment of non-periodic data. &#2013266080;In that case, a range of > frequencies will contribute to each DFT frequency. &#2013266080;Not really a
histogram,
> though, as the contributions aren't uniform.
i'm not sure, but wouldn't it be the case that if you started with an infinitely-long continuous-time input, x(t), and multiplied it by a "window" that's the right sorta sinc() function w(t) = sinc( (Fs/N)*t ) (sinc(u) = sin(pi*u)/(pi*u)) now we have x(t)*w(t). then it gets sampled and time-aliased to get a discrete, periodic function: x[n] = SUM{ x((n-m*N)/Fs) * w((n-m*N)/Fs) } m and run a single period (N samples) of that x[n] into the DFT (note the less common scaling convention). N-1 X[k] = (1/N) * SUM{ x[n] * exp(-j*2*pi*n*k/N) } n=0 wouldn't the value in bin #k, X[k] be a brick-wall filter of the sum of amplitudes would not the bin #k contain only frequency components of x(t) that live strictly between (k-1/2)*Fs/N and (k+1/2)*Fs/N ? wouldn't that be the case? r b-j
On Feb 11, 7:51&#2013266080;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Feb 11, 1:56 am, kevinjmc...@netscape.net wrote: > > > > > And, actually, the bin isn't really a 'brick wall' band pass filter, > > but rather, it has a shape that depends on the type of window used > > (e.g.: implicit rectangular one, Gaussian, Hann, etc.). > > On Feb 11, 6:16&#2013266080;am, Glen Herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
> > > > > > > Fred Marshall wrote: > > > hyeewang wrote: > > >>>I often see DFT bin in some DFT/stft literature,What does the term > > >>"bin" mean exactly? > > > It probably isn't very *exact* :-) > > > It's a slang term that derives from histogram terminology. > > > If the number falls between 0 and 1 then it goes in "bin" 1, between 1 and 2 > > > then "bin" 2, etc. and, in the end, each such ordered bin has so many > > > counts. > > > In a DFT, there are discrete frequency samples which look like such "bins" > > > in that there's a value at each of the ordered samples. > > > I believe it is worse than that. &#2013266080;Some people use the DFT (or FFT) > > on a segment of non-periodic data. &#2013266080;In that case, a range of > > frequencies will contribute to each DFT frequency. &#2013266080;Not really a
histogram,
> > though, as the contributions aren't uniform. > > i'm not sure, but wouldn't it be the case that if you started with an > infinitely-long continuous-time input, x(t), and multiplied it by a > "window" that's the right sorta sinc() function > > &#2013266080; &#2013266080; w(t) = sinc( (Fs/N)*t ) &#2013266080;
&#2013266080;(sinc(u) = sin(pi*u)/(pi*u))
> > now we have x(t)*w(t). &#2013266080;then it gets sampled and time-aliased to get
a
> discrete, periodic function: > > &#2013266080; &#2013266080; x[n] = SUM{ x((n-m*N)/Fs) * w((n-m*N)/Fs) } > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;
&#2013266080; m
> > and run a single period (N samples) of that x[n] into the DFT (note > the less common scaling convention). > > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;
&#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;N-1
> &#2013266080; &#2013266080; X[k] = (1/N) * SUM{ x[n] * exp(-j*2*pi*n*k/N) } > &#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;
&#2013266080; &#2013266080; &#2013266080; &#2013266080; &#2013266080;n=0
> > wouldn't the value in bin #k, X[k] be a brick-wall filter of the sum > of amplitudes > > would not the bin #k contain only frequency components of x(t) that > live strictly between &#2013266080; (k-1/2)*Fs/N &#2013266080;and
&#2013266080;(k+1/2)*Fs/N ? &#2013266080;wouldn't
> that be the case? > > r b-j- Hide quoted text - > > - Show quoted text -
Hi robert, Let me say first to Fred and Glen: yes, you're right - the 'bin' idea is certainly a heuristic, albeit a useful one for interpreting things. I wasn't sure of the OP's knowledge of windows/convolution so I tried to give a simpler answer. As for robert - I think I undestand what you're tryng to get at, but I've always interpreted spectral leakage as explained in the well known Harris paper (you probably have a copy, but here's a link): http://web.mit.edu/xiphmont/Public/windows.pdf As shown, he explains spectral leakage in terms of the discontinuities at the ends of the data record. He also says that the easiest way to diminish them is to match as many orders of the derivatives of the weighted data to zero. I think that if you use a very large data record, and the right type of window, you can come close to gettting a 'brick wall' filter. But I think that to get an actual brick wall would imply that there would be no spectral leakage whatsoever. So if you have a single frequency that is swept from one 'bin' to the next, then the output shows up in the first bin when the frquency is closer to it that the next one, and immediately disappears from the first 'bin' and instantly appears in the next when the frequency of the input is closerr to that one than the first. I think that in order to do that, you'd have to match all the derivatives to zero, and I've never seen a window that does that. Al Nuttal's 1981 paper also used the derivative approach when describing a bunch of sum of cosine type windows, and I don't believe he ever matched more that a few of them to zero. Kevin
kevinjmcgee@netscape.net wrote:
(snip on FFT and bins)

> Let me say first to Fred and Glen: yes, you're right - the 'bin' idea > is certainly a heuristic, albeit a useful one for interpreting > things. I wasn't sure of the OP's knowledge of windows/convolution so > I tried to give a simpler answer.
> As for robert - I think I undestand what you're tryng to get at, but > I've always interpreted spectral leakage as explained in the well > known Harris paper (you probably have a copy, but here's a link):
Well, that is there, too. If you make the interval long enough, such that the end is a small fraction of the points, that should reduce that effect. Even better, multiply the whole series by a gaussian such that it falls off smoothly at the ends. If the underlying sine is between two 'bins' then you should see energy in both, and nearby bins as well.
> http://web.mit.edu/xiphmont/Public/windows.pdf
> As shown, he explains spectral leakage in terms of the discontinuities > at the ends of the data record. He also says that the easiest way to > diminish them is to match as many orders of the derivatives of the > weighted data to zero. > > I think that if you use a very large data record, and the right type > of window, you can come close to gettting a 'brick wall' filter. But > I think that to get an actual brick wall would imply that there would > be no spectral leakage whatsoever. So if you have a single frequency > that is swept from one 'bin' to the next, then the output shows up in > the first bin when the frquency is closer to it that the next one, and > immediately disappears from the first 'bin' and instantly appears in > the next when the frequency of the input is closerr to that one than > the first.
Remember that the FFT has periodic boundary conditions. If you really have a sine then it can only have frequencies matching bits. Physics likes the term 'wave packet', which is pretty close to a sine multiplied by a Gaussian. The (continuous) transform is then a Gaussian around the sine frequency, the width depending on the length (time, or Gaussian width) of the wave packet. Gaussian being the shape that minimizes the product of its width and its transform width. That also comes out in the Heisenberg uncertainty principle, with position and momentum as transform pairs.
> I think that in order to do that, you'd have to match all > the derivatives to zero, and I've never seen a window that does that. > Al Nuttal's 1981 paper also used the derivative approach when > describing a bunch of sum of cosine type windows, and I don't believe > he ever matched more that a few of them to zero.
-- glen