# FFT bin meaning

Started by 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
&#2013266067;nails&#2013266068; 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

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.
```
```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

```