Forums

proper terminology for one bin of an fft/dft?

Started by Ron N. March 13, 2006
What is the proper or most common term for computing or
describing only one bin of an fft or dft?  I think this is the
same thing as the correlation against quadrature sinusoids
of a frequency which happens to be an exact multiple of the
reciprocal of the fft length.  One bin can also be calculated
by an implementation of the Goertzel algorithm, which I've
seen described as a second order filter followed by averaging.

Is there a standard technical term that covers all of the above?
Or is "one bin" acceptable?

Would calculating one bin of a non-rectangular windowed
(say Hamming) fft be called something different?

Is there a standard term for frequencies which are at the
center of fft bins, versus those which are between bins?
(e.g. not exact multiples of fs/n)

I'm writing up some frequency estimation algorithms, and
want to make sure my terminology is clear and standard.


Thanks.
-- 
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:

> What is the proper or most common term for computing or > describing only one bin of an fft or dft? I think this is the > same thing as the correlation against quadrature sinusoids > of a frequency which happens to be an exact multiple of the > reciprocal of the fft length. One bin can also be calculated > by an implementation of the Goertzel algorithm, which I've > seen described as a second order filter followed by averaging. > > Is there a standard technical term that covers all of the above? > Or is "one bin" acceptable?
Works for me.
> > Would calculating one bin of a non-rectangular windowed > (say Hamming) fft be called something different?
"Convolved bin" or "averaged bin" perhaps?
> > Is there a standard term for frequencies which are at the > center of fft bins, versus those which are between bins? > (e.g. not exact multiples of fs/n)
I think they are called "coherent frequencies" (vs. "non-coherent" frequencies). At least they are called that in the FFT software that I use (Hp Works).
> > I'm writing up some frequency estimation algorithms, and > want to make sure my terminology is clear and standard.
Can't go wrong if you follow some classic literature (O&S?). Often, a colloquial term such as "bin" is not well defined (for example, what do you call the outputs of a constant Q filterbank? Technically, the only difference to the DFT is that the length of the correlation vectors differ). Just make sure that everybody knows what you refer to - simply define a "bin" to be a coordinate of the DFT of a vector, and you're done. Regards, Andor

Ron N. wrote:
> What is the proper or most common term for computing or > describing only one bin of an fft or dft?
I wish there were. Bin intimates that some kind of collection is occurring there when it is really a sample of the underlying continuous frequency domain function evaluated at one specific frequency. It is exactly analogous to a time domain point being a sample of an underlying time domain function evaluated at a specific point in time. Windowing the time domain function replaces each frequency domain sample with a linear combination of other samples via convolution. Since the values between the samples, in the bandlimited or timelimited cases, are also linear combinations of those samples, the windowing also factors into each samlple values between the samples transformed from the unwindowed time domain sequence. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
On 13 Mar 2006 12:44:34 -0800, "Ron N." <rhnlogic@yahoo.com> wrote:

>What is the proper or most common term for computing or >describing only one bin of an fft or dft? I think this is the >same thing as the correlation against quadrature sinusoids >of a frequency which happens to be an exact multiple of the >reciprocal of the fft length. One bin can also be calculated >by an implementation of the Goertzel algorithm, which I've >seen described as a second order filter followed by averaging. > >Is there a standard technical term that covers all of the above? >Or is "one bin" acceptable?
Hi Ron, ah,... terminology is the source of so much heartache and confusion. The words "DFT bin" is a short-n-sweet phrase that does have technical validity. If we compute a 16-pt DFT, the result is: X(0), X(1), X(2), ... X(15) --- sixteen complex-valued samples. If you're talking about the X(2) sample you can call it the "third DFT sample value" or you could just call it the "third bin value". The word "bin", to me, means a small container sitting side-by-side with other small containers. (Like the bins of nuts & bolts in the hardware store.) You can think of the X(2) DFT sample value as the output of a bandpass filter whose center frequency is 2*Fs/N for an N-pt DFT. (Fs is the sample rate in Hz.) Likewise, the X(3) DFT sample value as the output of a bandpass filter whose center frequency is 3*Fs/N for an N-pt DFT. This bandpass filter's center freq is sitting just to the right of the X(2) filter's center freq. (That's the side-by-side "bin" idea.)
>Would calculating one bin of a non-rectangular windowed >(say Hamming) fft be called something different?
Nope, I sure don't think so.
> >Is there a standard term for frequencies which are at the >center of fft bins, versus those which are between bins? >(e.g. not exact multiples of fs/n)
It's my experience that DSP engineers refer to the frequencies that are integer multiples of Fs/N as "bin centers".
>I'm writing up some frequency estimation algorithms, and >want to make sure my terminology is clear and standard.
It's a good thing that you want to use the "right" terminology. The way to avoid confusion is to very carefully define (avoiding all ambiguity) all terms or phrases used in your writing that might be misunderstood by your readers. For example, you might write something like: "The DFT's second and third bins centers (2*Fs/N and 3*Fs/N respectively) are separated by 100 Hz." Good Luck Ron, [-Rick-]
On 13 Mar 2006 12:44:34 -0800, "Ron N." <rhnlogic@yahoo.com> wrote:

>What is the proper or most common term for computing or >describing only one bin of an fft or dft? I think this is the >same thing as the correlation against quadrature sinusoids >of a frequency which happens to be an exact multiple of the >reciprocal of the fft length. One bin can also be calculated >by an implementation of the Goertzel algorithm, which I've >seen described as a second order filter followed by averaging. > >Is there a standard technical term that covers all of the above? >Or is "one bin" acceptable?
Hi Ron, ah,... terminology is the source of so much heartache and confusion. The words "DFT bin" is a short-n-sweet phrase that does have technical validity. If we compute a 16-pt DFT, the result is: X(0), X(1), X(2), ... X(15) --- sixteen complex-valued samples. If you're talking about the X(2) sample you can call it the "third DFT sample value" or you could just call it the "third bin value". The word "bin", to me, means a small container sitting side-by-side with other small containers. (Like the bins of nuts & bolts in the hardware store.) You can think of the X(2) DFT sample value as the output of a bandpass filter whose center frequency is 2*Fs/N for an N-pt DFT. (Fs is the sample rate in Hz.) Likewise, the X(3) DFT sample value as the output of a bandpass filter whose center frequency is 3*Fs/N for an N-pt DFT. This bandpass filter's center freq is sitting just to the right of the X(2) filter's center freq. (That's the side-by-side "bin" idea.)
>Would calculating one bin of a non-rectangular windowed >(say Hamming) fft be called something different?
Nope, I sure don't think so.
> >Is there a standard term for frequencies which are at the >center of fft bins, versus those which are between bins? >(e.g. not exact multiples of fs/n)
It's my experience that DSP engineers refer to the frequencies that are integer multiples of Fs/N as "bin centers".
>I'm writing up some frequency estimation algorithms, and >want to make sure my terminology is clear and standard.
It's a good thing that you want to use the "right" terminology. The way to avoid confusion is to very carefully define (avoiding all ambiguity) all terms or phrases used in your writing that might be misunderstood by your readers. For example, you might write something like: "The DFT's second and third bins centers (2*Fs/N and 3*Fs/N respectively) are separated by 100 Hz." Good Luck Ron, [-Rick-]
On 13 Mar 2006 12:44:34 -0800, "Ron N." <rhnlogic@yahoo.com> wrote:

>What is the proper or most common term for computing or >describing only one bin of an fft or dft? I think this is the >same thing as the correlation against quadrature sinusoids >of a frequency which happens to be an exact multiple of the >reciprocal of the fft length. One bin can also be calculated >by an implementation of the Goertzel algorithm, which I've >seen described as a second order filter followed by averaging. > >Is there a standard technical term that covers all of the above? >Or is "one bin" acceptable?
Hi Ron, ah,... terminology is the source of so much heartache and confusion. The words "DFT bin" is a short-n-sweet phrase that does have technical validity. If we compute a 16-pt DFT, the result is: X(0), X(1), X(2), ... X(15) --- sixteen complex-valued samples. If you're talking about the X(2) sample you can call it the "third DFT sample value" or you could just call it the "third bin value". The word "bin", to me, means a small container sitting side-by-side with other small containers. (Like the bins of nuts & bolts in the hardware store.) You can think of the X(2) DFT sample value as the output of a bandpass filter whose center frequency is 2*Fs/N for an N-pt DFT. (Fs is the sample rate in Hz.) Likewise, the X(3) DFT sample value as the output of a bandpass filter whose center frequency is 3*Fs/N for an N-pt DFT. This bandpass filter's center freq is sitting just to the right of the X(2) filter's center freq. (That's the side-by-side "bin" idea.)
>Would calculating one bin of a non-rectangular windowed >(say Hamming) fft be called something different?
Nope, I sure don't think so.
> >Is there a standard term for frequencies which are at the >center of fft bins, versus those which are between bins? >(e.g. not exact multiples of fs/n)
It's my experience that DSP engineers refer to the frequencies that are integer multiples of Fs/N as "bin centers".
>I'm writing up some frequency estimation algorithms, and >want to make sure my terminology is clear and standard.
It's a good thing that you want to use the "right" terminology. The way to avoid confusion is to very carefully define (avoiding all ambiguity) all terms or phrases used in your writing that might be misunderstood by your readers. For example, you might write something like: "The DFT's second and third bins centers (2*Fs/N and 3*Fs/N respectively) are separated by 100 Hz." Good Luck Ron, [-Rick-]
Bob Cain wrote:
> > Ron N. wrote: > >>What is the proper or most common term for computing or >>describing only one bin of an fft or dft? > > > I wish there were. Bin intimates that some kind of collection is > occurring there when it is really a sample of the underlying continuous > frequency domain function evaluated at one specific frequency.
Consider a set of bins lined up as water balloon targets at a carnival. Each bin is just barely wide enough to accept a balloon. So if you throw the balloon absolutely perfectly into one of the bins, all the water goes into that bin (you win a prize). If you don't throw perfectly; the balloon explodes and splashes water everywhere. Naturally, most of the water will end up in the bins adjoining the wall that was hit. What do you think? Does this analogy hold water? The underlying assumption of the DFT rarely (never) matches reality. The signal is assumed to be periodic at the DFT length. i.e. there are no frequencies other than those at multiples of fs/N (the "bins"). In the real world, the DFT is used to detect the frequencies of a signal that is not periodic. This mismatch causes a convolution in the frequency domain: the convolution of sin(x)/x and the "actual" frequency spectrum. A sinusoid with a frequency that is a multiple of fs/N will have all of its energy placed into one bin. Any other sinusoid will spread its energy across all the bins. -- Mark Borgerding

Mark Borgerding wrote:
> Bob Cain wrote: >> Ron N. wrote: >> >>> What is the proper or most common term for computing or >>> describing only one bin of an fft or dft? >> >> I wish there were. Bin intimates that some kind of collection is >> occurring there when it is really a sample of the underlying continuous >> frequency domain function evaluated at one specific frequency. > > Consider a set of bins lined up as water balloon targets at a carnival. > Each bin is just barely wide enough to accept a balloon. So if you > throw the balloon absolutely perfectly into one of the bins, all the > water goes into that bin (you win a prize). If you don't throw > perfectly; the balloon explodes and splashes water everywhere. > Naturally, most of the water will end up in the bins adjoining the wall > that was hit. > > > What do you think? Does this analogy hold water? > > > > The underlying assumption of the DFT rarely (never) matches reality. The > signal is assumed to be periodic at the DFT length. i.e. there are no > frequencies other than those at multiples of fs/N (the "bins"). In the > real world, the DFT is used to detect the frequencies of a signal that > is not periodic. > > This mismatch causes a convolution in the frequency domain: the > convolution of sin(x)/x and the "actual" frequency spectrum. > > A sinusoid with a frequency that is a multiple of fs/N will have all of > its energy placed into one bin. > > Any other sinusoid will spread its energy across all the bins. > > -- Mark Borgerding
Consider the transform of an FIR. There is a smooth frequency domain function describing it. If you process a sweep with it, the continuous nature becomes clear. It obviously has values at places other than at the "bins" of any FFT long enough to encompass it and if you look at the continuous function, which the sweep discloses, at the "bin" frequencies of the transform it will equal what the transform says it is at those frequencies. The DFT samples the continuous frequency domain function that actually describes what the FIR will do. No water splashed anywhere that I can see. :-) Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
Bob Cain wrote:

> > Consider the transform of an FIR. There is a smooth frequency domain > function describing it.
Perhaps there is continuous function that describes any given sequence of length N, but there is also a sum-of-sinusoids function that describes it. As soon as you perform a DFT of a length N, the latter is what you get. Any continuous behavior is gone. -- Mark B
Rick Lyons wrote:
(snip)
> > "The DFT's second and third bins centers > (2*Fs/N and 3*Fs/N respectively) are separated > by 100 Hz." >
Rick, Shouldn't that be "... (Fs/N and 2*Fs/N respectively)..."? Regards, John