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
Nyquist frequency in FFTs
Started by ●September 24, 2004
Reply by ●September 24, 20042004-09-24
"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
Reply by ●September 25, 20042004-09-25
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 >
Reply by ●September 25, 20042004-09-25
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 >
Reply by ●September 25, 20042004-09-25
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
Reply by ●September 25, 20042004-09-25
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
>
Reply by ●September 25, 20042004-09-25
"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 >
Reply by ●September 25, 20042004-09-25
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
Reply by ●September 26, 20042004-09-26
"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
Reply by ●September 26, 20042004-09-26
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. > > FredOne 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. �����������������������������������������������������������������������
