Forums

Nyquist frequency in FFTs

Started by Shafik September 24, 2004
Hello all,

I noticed that all FFT routines transform a time array into a
frequency array of the following form:

F[0], F[n/2], real:F[1], imag:F[1], real:F[2], imag:F[2], etc..

Now the question is, why does "F[n/2]" (the nyquist freq) appear as the
second term, and more importantly, what is it's phase? Is it assumed to
be fully real?

Just extremely curious,
--Shafik

"Shafik" <shafik@u.arizona.edu> wrote in message 
news:1096065687.838753.305160@k17g2000odb.googlegroups.com...
> Hello all, > > I noticed that all FFT routines transform a time array into a > frequency array of the following form: > > F[0], F[n/2], real:F[1], imag:F[1], real:F[2], imag:F[2], etc.. > > Now the question is, why does "F[n/2]" (the nyquist freq) appear as the > second term, and more importantly, what is it's phase? Is it assumed to > be fully real?
"all" seems a bit presumptuous. Not any programs I know of store the data in the sequenc you've suggested. Also, since "routines" imply an implementation, you might also find a real array and an imaginary array with who knows what storage arrangment. So, having them alternate is a particular implementation - I think that's what you implied with your representation... Fred

Shafik wrote:
> Hello all, > > I noticed that all FFT routines transform a time array into a > frequency array of the following form:
All is too strong. How about "the few I have seen"?
> F[0], F[n/2], real:F[1], imag:F[1], real:F[2], imag:F[2], etc..
A space saving programmers hack for ( R0, 0 ), ( R1, I1 ), ( R2, I2 ), ..., ( Rn/2-1, In/2-1 ), ( Rn/2, 0 ), ( Rn/2+1, In/2+1 ), .... for the (common) special case of all real input. Saves storing the known zeros and the symetricaly know values. There are N/2 + 1 real values and N/2 - 1 imaginary values that might possibly be nonzero and nonredundent for even N. (Since the folks who take such shortcuts only deal with the limited case of N=2^k the evenness assumption is so automatic it is not mentioned.) The input has N real possible nonzero values and N known zeros so the "count" of data items is preserved.
> > Now the question is, why does "F[n/2]" (the nyquist freq) appear as the > second term, and more importantly, what is it's phase? Is it assumed to > be fully real?
Read The Fine Manual to notice that the routine you are looking at is for real data. Real data is so common that some of the authors of those Fine manuals forget to mention that any other possibility exists. For real input both F0 and Fn/2, when it exits, are purely real.
> Just extremely curious, > --Shafik >
Shafik,

This is a common memory-saving trick when performing an FFT on a real-valued 
sequence.  For a real time-domain sequence you are guaranteed to get a real 
term at 0 and N/2.  The rest of the terms can be complex.  Furthermore you 
will have complex conjugate symmetry in your remaining terms.  That is, 
F[n/2-1]=F*[n/2+1], F[n/2-2]=F*[n/2+2], etc.

So given that info you can put the two real terms first, and then have n/2-1 
complex terms.  The remaining n/2-1 terms can be derived by negating the 
imaginary parts.  So basically this allows you to store the result of an N 
sample real FFT into N memory locations.

Brad

"Shafik" <shafik@u.arizona.edu> wrote in message 
news:1096065687.838753.305160@k17g2000odb.googlegroups.com...
> Hello all, > > I noticed that all FFT routines transform a time array into a > frequency array of the following form: > > F[0], F[n/2], real:F[1], imag:F[1], real:F[2], imag:F[2], etc.. > > Now the question is, why does "F[n/2]" (the nyquist freq) appear as the > second term, and more importantly, what is it's phase? Is it assumed to > be fully real? > > Just extremely curious, > --Shafik >
How come F[n/2] must be real?

I can have a sequence -1, 1, -1, 1, -1, 1, -1, 1
or:                              1, -1, 1, -1, 1, -1, 1, -1

those are nyquist frequencies that are 180 degrees out of phase....or
am I wrong?

--Shafik

N point DFT definition:

X[k] = sum from n=0:N-1(x[n]*e^(-j*2*pi*k*n/N))

X[N/2] = sum from n=0:N-1(x[n]*e^(-j*2*pi*N/2*n/N))
    = sum from n=0:N-1(x[n] * (-1)^n)

As you can see from the definition of the DFT when you evaluate at N/2 you 
end up with the sum of x[n] time (-1)^n, so as long x is real X[N/2] will 
also be real.

Brad

"Shafik" <shafik@u.arizona.edu> wrote in message 
news:1096146865.755417.30390@k17g2000odb.googlegroups.com...
> How come F[n/2] must be real? > > I can have a sequence -1, 1, -1, 1, -1, 1, -1, 1 > or: 1, -1, 1, -1, 1, -1, 1, -1 > > those are nyquist frequencies that are 180 degrees out of phase....or > am I wrong? > > --Shafik >
"Shafik" <shafik@u.arizona.edu> wrote in message
news:1096146865.755417.30390@k17g2000odb.googlegroups.com...
> How come F[n/2] must be real? > > I can have a sequence -1, 1, -1, 1, -1, 1, -1, 1 > or: 1, -1, 1, -1, 1, -1, 1, -1 > > those are nyquist frequencies that are 180 degrees out of phase....or > am I wrong?
You're right that each element is 180 degrees out of phase with the element above it but they are all real.
>
> --Shafik >
You guys are right. The Nyquist frequency can ONLY be 0 or 180 degrees
out of phase, which is the real value or its negative (another real
value).

It can't really have any other phase.

--Shafik

"Shafik" <shafik@u.arizona.edu> wrote in message 
news:1096146865.755417.30390@k17g2000odb.googlegroups.com...
> How come F[n/2] must be real? > > I can have a sequence -1, 1, -1, 1, -1, 1, -1, 1 > or: 1, -1, 1, -1, 1, -1, 1, -1 > > those are nyquist frequencies that are 180 degrees out of phase....or > am I wrong?
I can't tell whether you mean the sequence is in time or frequency. **That's not too important because of duality.... I don't know what you mean by 180 degrees out of phase in the context of this sequence. **That *is* important. It's not possible to talk about phase at more than one frequency at a time without some sort of notation convention. One might imagine but that would be conjecture. I don't know what you mean by "these are Nyquist frequencies".. but the last comment implies the sequence is in frequency and that implies that the fifth element of the sequence is at fs/2 which is THE Nyquist frequency. The fifth element of the sequence is non-zero. So, that means the sequence represents one that is not of bandwidth limited to LESS THAN fs/2 - which is the Nyquist criterion. Further, the value at fs/2 isn't negligible. Accordingly, there can be problems with such a sequence in reconstruction. Fred
Fred Marshall wrote:

> "Shafik" <shafik@u.arizona.edu> wrote in message > news:1096146865.755417.30390@k17g2000odb.googlegroups.com... > >>How come F[n/2] must be real? >> >>I can have a sequence -1, 1, -1, 1, -1, 1, -1, 1 >>or: 1, -1, 1, -1, 1, -1, 1, -1 >> >>those are nyquist frequencies that are 180 degrees out of phase....or >>am I wrong?
I can't figure out what's meant either. Is the offset between the two lines significant? How?
> I can't tell whether you mean the sequence is in time or frequency. > **That's not too important because of duality.... > > I don't know what you mean by 180 degrees out of phase in the context of > this sequence. > **That *is* important. It's not possible to talk about phase at more than > one frequency at a time without some sort of notation convention. One might > imagine but that would be conjecture. > > I don't know what you mean by "these are Nyquist frequencies".. > but the last comment implies the sequence is in frequency and that implies > that the fifth element of the sequence is at fs/2 which is THE Nyquist > frequency. > > The fifth element of the sequence is non-zero. So, that means the sequence > represents one that is not of bandwidth limited to LESS THAN fs/2 - which is > the Nyquist criterion. Further, the value at fs/2 isn't negligible. > Accordingly, there can be problems with such a sequence in reconstruction. > > Fred
One can go overboard with LESS THAN. A frequency at fs/2 doesn't meet the Nyquist criterion because can't be accurately reconstructed, but neither does it invalidate the sample set, because it doesn't alias. Jerry -- ... they proceeded on the sound principle that the magnitude of a lie always contains a certain factor of credibility, ... and that therefor ... they more easily fall victim to a big lie than to a little one ... A. H. &#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;&#2013266071;