FFT Algorithm and Time

I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
 What I am a little confused about is how do I determine what is the
frequency scale of the X axis?

thanks
Don

"d1camero" <a8723@cameronsoftware.com> writes:

> I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>  What I am a little confused about is how do I determine what is the
> frequency scale of the X axis?

n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
of the data. When you get to n = N/2 and above, you've covered the positive
frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
n > N/2.
-- 
%  Randy Yates                  % "I met someone who looks alot like you,
%% Fuquay-Varina, NC            %             she does the things you do, 
%%% 919-577-9882                %                     but she is an IBM."
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO   
http://home.earthlink.net/~yatescr

> what is the frequency scale of the X axis?

A simple fact to bear in mind is that the number of the bin *is* the
actual frequency. The dimensions for these numbers are not in the familiar
Hz (cycles/second) but rather in cycles/frame. To convert this to Hz, just
multiply by the number of input frames/second, or divide by the duration
of your input frame (in seconds).

It is interesting to note that the number of the bin in which you get a
significant spectral response gives a clue as to how many cycles was
contained in your input frame (+/- 0.5 cycles). For a 1024 point FFT, say,
if you had a significant response in bin 211, then there would be between
210.5 and 211.5 cycles of that frequency in your original input frame.

Jeff 

Thanks Randy, this worked out quite well.

Don

Randy Yates wrote:
> "d1camero" <a8723@cameronsoftware.com> writes:
>
> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
> >  What I am a little confused about is how do I determine what is the
> > frequency scale of the X axis?
>
> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
> of the data. When you get to n = N/2 and above, you've covered the positive
> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
> n > N/2.

unless, of course if you're using MATLAB, then "n" is off by one from
the relationship above for which DSP engineers are thankful to TMW for.

(the other think is that the bin at Nyquist (n=N/2 for the regular
world or n=N/2+1 for MATLAB) that it is just as plausible that it's
negative or positive.  i usually like to say half of the value of the
Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
other half of the bin amplitude is at the negative frequency -N/2 *
Fs/N = -Fs/2 

r b-j

"robert bristow-johnson" <rbj@audioimagination.com> writes:

> Randy Yates wrote:
>> "d1camero" <a8723@cameronsoftware.com> writes:
>>
>> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>> >  What I am a little confused about is how do I determine what is the
>> > frequency scale of the X axis?
>>
>> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
>> of the data. When you get to n = N/2 and above, you've covered the positive
>> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
>> n > N/2.
>
> unless, of course if you're using MATLAB, then "n" is off by one from
> the relationship above for which DSP engineers are thankful to TMW for.

Robert, I think you may actually have this issue carved on your tombstone:

  Here lies a man who knew Matlab indexing was wrong.

> (the other think is that the bin at Nyquist (n=N/2 for the regular
> world or n=N/2+1 for MATLAB) that it is just as plausible that it's
> negative or positive.  i usually like to say half of the value of the
> Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
> other half of the bin amplitude is at the negative frequency -N/2 *
> Fs/N = -Fs/2 

I waffled in my head about this but my intuition told me it was
positive. Could just as well be negative. But I don't like the idea of
splitting it up - perhaps simply duplicating it would be better. Yeah,
I know - the energy wouldn't add up right then - but from a GUI
perspective it would seem better.
-- 
%  Randy Yates                  % "She has an IQ of 1001, she has a jumpsuit
%% Fuquay-Varina, NC            %            on, and she's also a telephone."
%%% 919-577-9882                % 
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO   
http://home.earthlink.net/~yatescr

Randy Yates wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> writes:
>
> > Randy Yates wrote:
> >> "d1camero" <a8723@cameronsoftware.com> writes:
> >>
> >> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
> >> >  What I am a little confused about is how do I determine what is the
> >> > frequency scale of the X axis?
> >>
> >> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
> >> of the data. When you get to n = N/2 and above, you've covered the positive
> >> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
> >> n > N/2.
> >
> > unless, of course if you're using MATLAB, then "n" is off by one from
> > the relationship above for which DSP engineers are thankful to TMW for.
>
> Robert, I think you may actually have this issue carved on your tombstone:
>
>   Here lies a man who knew Matlab indexing was wrong.

yeah, i fought the good fight.  even though i lost.

we could just put a big "L" for "loser" on my tombstone.

r b-j

"robert bristow-johnson" <rbj@audioimagination.com> writes:

> Randy Yates wrote:
>> "robert bristow-johnson" <rbj@audioimagination.com> writes:
>>
>> > Randy Yates wrote:
>> >> "d1camero" <a8723@cameronsoftware.com> writes:
>> >>
>> >> > I am new to DSP and FFT.  I have implememented the FFT in Smith's book.
>> >> >  What I am a little confused about is how do I determine what is the
>> >> > frequency scale of the X axis?
>> >>
>> >> n*Fs/N, 0 < n < N-1, N being the FFT size and Fs being the sample rate
>> >> of the data. When you get to n = N/2 and above, you've covered the positive
>> >> frequencies and begin the negative frequencies, i.e., n*Fs/N == (n-N)*Fs/N,
>> >> n > N/2.
>> >
>> > unless, of course if you're using MATLAB, then "n" is off by one from
>> > the relationship above for which DSP engineers are thankful to TMW for.
>>
>> Robert, I think you may actually have this issue carved on your tombstone:
>>
>>   Here lies a man who knew Matlab indexing was wrong.
>
> yeah, i fought the good fight.  even though i lost.
>
> we could just put a big "L" for "loser" on my tombstone.

We're all losers. Some ya' win, some ya' lose. That's partly what makes
these words from my favorite ELO album so true and poignant:

  "...the answer lies within your soul, 'cause no one knows which side
  the coin will fall."
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr

Randy Yates wrote:
> "robert bristow-johnson" <rbj@audioimagination.com> writes:
> > (the other think is that the bin at Nyquist (n=N/2 for the regular
> > world or n=N/2+1 for MATLAB) that it is just as plausible that it's
> > negative or positive.  i usually like to say half of the value of the
> > Nyquist bin is at the positive frequency N/2 * Fs/N = Fs/2 and the
> > other half of the bin amplitude is at the negative frequency -N/2 *
> > Fs/N = -Fs/2
>
> I waffled in my head about this but my intuition told me it was
> positive. Could just as well be negative. But I don't like the idea of
> splitting it up - perhaps simply duplicating it would be better. Yeah,
> I know - the energy wouldn't add up right then - but from a GUI
> perspective it would seem better.

>From the perspective of trigonometric interpolation (i.e. taking the
DFT formula and using it to interpolate between the samples), splitting
up the Nyquist amplitude half-and-half between positive and negative
frequencies is in some sense the optimal choice.  It leads to a minimal
rms slope interpolation, and also interpolates real data to real data.

On the other hand, if your Nyquist amplitude is not very small then you
probably have more serious problems with aliasing.  If it is small,
then it doesn't matter much what you do with it.

Steven

stevenj@alum.mit.edu wrote:
>
> From the perspective of trigonometric interpolation (i.e. taking the
> DFT formula and using it to interpolate between the samples), splitting
> up the Nyquist amplitude half-and-half between positive and negative
> frequencies is in some sense the optimal choice.  It leads to a minimal
> rms slope interpolation, and also interpolates real data to real data.

this is what was motivating this question i've been having about
bandlimited interpolation of periodic discrete signals.  letting
x[n]=x[n+N] for all n, when the period N is odd, there is no Nyquist
component and the reconstruction formula is the Dirichlet thingie:

            N-1
    x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*sin(pi*(t-n))) }
           n=0

    x(t+N) = x(t)

but for the case of N even, there is a (potential) component at
Nyquist, for real x[n] this component has to be real, and if you split
it half and half and reconstruct, you get


            N-1
    x(t) = SUM{ x[n] * sin(N*pi*(t-n))/(N*tan(pi*(t-n))) }
           n=0

    x(t+N) = x(t)

it's the same for interpolating spectra coming out of the DFT when N is
odd, but not for N even.

Steven (or anyone else), do you know the reason why this is so?

r b-j