in article 1143224421.387295.239780@u72g2000cwu.googlegroups.com, Ron N. at rhnlogic@yahoo.com wrote on 03/24/2006 13:20:>>> which is why a sample 0 reference seems to work, but only when >>> assuming only bin center frequencies exist. >> >> so when the sinusoid is just a teeny milli-smidgen off of the center >> frequency, there is some kind of step function that makes this work totally >> differently? > > Not a step function. The phase offset between sample 0 and > sample N/2 will vary continuously with how much the signal sinusoid > is between bin center frequencies.i guess that is true, but i don't see it as supporting your original claim that the phase of the DFT bin is relative to bin N/2 instead of bin 0.>> now it is *true* (but i don't think the definition) that the DFT is equal to >> the N equally spaced samples of the DTFT of the same sequence of x[n] that >> is ZERO-extended (not periodically extended). ask yourself what the DTFT of >> that zero-extended sequence is for the case that the frequency is not an >> integer multiple of 1/N. use a complex sinusoid: >> >> x[n] = exp(j*(2*pi*f0*n + theta)) where f0 is not M/N. >> >> find the peak (it will be the middle of the sinc() function), and evaluate >> the phase of the DTFT at that peak. i'll bet you that it is theta. now, for >> the discrete samples in the freq domain that are adjacent to that peak (at >> indices floor(N*f0) and floor(N*f0)+1) the phase will be different, but not >> that much different. > > If you interpolate phase as well as frequency,i interpolate phase *with* (or maybe i should say "against") frequency. actually, i would interpolate the real and imaginary parts of the DFT values against frequency and get the continuous magnitude and phase from that.> then the interpolated phase will be referenced to bin 0. I agree with > the above; and I understand your point. You are looking at DFT results > as samples of a continuous frequency response.actually, more fundamentally, i look at the DFT as a mapping of one infinite and periodic discrete sequence of numbers with period N to another infinite and periodic discrete sequence of numbers with period N. it happens to be also true that the DFT equals the values of the DTFT of exactly one period (N samples) of that previously cited sequence and zero extended where the DTFT is sample at N equally spaced points. but there are an infinite number of finite sequences that when you DTFT and then sample N equally spaced values of that will be the very same DFT values. so i do not consider that fact particularly special and not the definition of the DFT. other people here *do* consider it definitive.> However, the continuous > frequency response can only be represented or reconstructed by > DFT sample points under certain constraints, which are often > not met in actual use of FFT analysis. The continuous representation > also can only be reconstructed if one calculates the full FFT/DFT.what is that? what is a "full FFT/DFT"?> However, if you don't interpolate, but interpret the FFT/DFT results > as correlations against template sinusoids or a matched filter bank,i *do* do that.> then any average phase offset for a least squared fit of a sinusoid > at one of the bin frequencies to the unknown signal is from the center > (N/2) of that particular (FIR equivalent) bin filter.no. that won't be true for the odd indices of X[k]. maybe true for the even indices but what you say here is off by an amount of pi radians for odd k.> > This is useful when calculating only one bin (or maybe a few) of > a DFT, where interpolation or reconstruction is impossible.interpolation in the frequency domain?> One bin is useful if you have a good but approximate guess as > to the frequency content of a signal.what are we talking about here? Goertzel? evaluating a few X[k] for values of interest? how does this relate to the phase of a sinusoidal component as indicated by the DFT (relative to what reference phase)?> Parseval's theorem can be used to safely validate a one bin guess.i dunno what this is about (i know what Parseval's theorem is, i don't get how it's germane).> Then phase vocoder analysis, using DFT bins offset in time rather than > frequency, can sometimes help gain more knowledge about a signal,this is about getting a more accurate estimate for the frequency if it is not in the center of the bin?> and sometimes at a lower computational cost than a full FFT (if you don't > need to reconstruct or examine other frequencies of course).okay, i think i know what you mean by "full FFT" now. as opposed to computing the DFT for just a few bins (and tracking the frequency of some component). i s'pose that's okay if you are always confident that there is only a few components, but any phase vocoder i'm aware of is meant to work (do pitch shifting or time scaling or analysis/resynthesis of some sort) on full bandwidth (or a "complete mix") audio that potentially has an extremely large number of sinusoidal components, some that are harmonically related and some that are not.> So you were talking about phase reconstruction in a full DFT, and > I was talking about how to gain phase knowledge from a single bin. > Sorry for the confusion. That's why I was asking about how to > talk about single bin DFT's earlier in this group.i still don't get how the phase relative to x[N/2] has anything to do with anything here. is it because you're windowing with a Hann window or similar and most of the energy is in the middle (around n = N/2)? you'll still be off by pi for X[k] where k is odd. Laroche or Puckette said something about this, and i've never had to worry about it because i would just use fftshift() in MATLAB or the equivalent in whatever other language to line up the middle of the windowed audio to bin 0 where it should be. so the latter half of the input data corresponds to negative time indices which is conceptually no problem since the DFT inherently periodically extends your data anyway. x[-1] is the same thing as x[N-1]. is this what the issue is about? because, if not, i still have absolutely no idea, whether it's a "full FFT" or just a few bins, how you can say that the phase is referenced to bin N/2. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Phase of FFT compared to phase of Sinusoid
Started by ●March 21, 2006
Reply by ●March 24, 20062006-03-24
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 24, 20062006-03-24
in article e01aos$bbh$1@newslocal.mitre.org, Stan Pawlukiewicz at stanp@spam.mitre.org wrote on 03/24/2006 12:37:> robert bristow-johnson wrote: >> in article 1143184207.713932.128110@j33g2000cwa.googlegroups.com, Ron N. at >> rhnlogic@yahoo.com wrote on 03/24/2006 02:10: >> >>> So I think the in general case, the DFT/FFT phase is really >>> referenced to sample N/2, >> >> no. since the DFT is an operation that literally imposes periodicity or >> circularity on the input data, there is no qualitative difference between >> boundaries between N/2-1 and N/2 or between N-1 and N (or 0). > > > You really need to post a disclaimer.about what, Stan? do i need a disclaimer or a qualifier to say that the difference in relationship between exp(j*2*pi*(N/2-1)/N) and exp(j*2*pi*(N/2)/N) is the same as the difference in relationship between exp(j*2*pi*(N-1)/N) and exp(j*2*pi*(0)/N) ? how do the relationship between those two pairs of numbers differ? what disclaimer would you have me post, Stan? (i know i'm opening myself up to satire here, but i'll chance it.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 25, 20062006-03-25
robert bristow-johnson wrote:> what is a "full FFT/DFT"?N complex bins (or N/2 complex bins plus a 1-bit flag saying that the original samples were all real) for a sample vector of length N. As opposed to a (much) smaller number of DFT result bins, such as only one.> interpolation in the frequency domain?is how you would reconstruct the continuous frequency response from a full set of FFT results, given that the proper conditions are met to do that (bandlimited, periodicity, no missing samples, etc.)>> One bin is useful if you have a good but approximate guess as >> to the frequency content of a signal. > what are we talking about here? Goertzel? evaluating a few X[k] for values > of interest? how does this relate to the phase of a sinusoidal component as > indicated by the DFT (relative to what reference phase)?Using the integer k Goertzel algorithm is one way to implement a DFT. Phase output should be with respect to the center of a Goertzel filter (any symmetric or antisymmetric FIR filter I think, minus the reference phase offset in the odd filter kernels.)>> Parseval's theorem can be used to safely validate a one bin guess. >i dunno what this is about (i know what Parseval's theorem is, i don't get >how it's germane).If the vast majority of your signal energy ends up in the first DFT bin you compute, you may not need to compute the rest of the bins (depending, of course, on what you need out of the DFT/FFT results). Parseval's theorem can be used to calculate just how much of the signal ended up in that first computed bin.> in article 1143224421.387295.239780@u72g2000cwu.googlegroups.com, Ron N. at > rhnlogic@yahoo.com wrote on 03/24/2006 13:20: > > However, if you don't interpolate, but interpret the FFT/DFT results > > as correlations against template sinusoids or a matched filter bank, > > i *do* do that. > > > then any average phase offset for a least squared fit of a sinusoid > > at one of the bin frequencies to the unknown signal is from the center > > (N/2) of that particular (FIR equivalent) bin filter. > > no. that won't be true for the odd indices of X[k]. maybe true for the even > indices but what you say here is off by an amount of pi radians for odd k.Yes. You have to reference the phase on the odd indices as negative with respect to the phase of the even indices when referencing phases to the center (N/2) of the sample vector. But interpreting FFT phase in this manner, and referencing that phase to sample n/2, gives the smallest squared error between any single bin to any arbitrary sinusoid of bin or non-bin frequency in the input sample vector. Referencing to sample 0 (without the odd rotation) only gives the smallest error for sample sinusoids of an exact bin frequency. So referencing to sample 0 will give wrong results when any waveform which is not periodic in N is fed to an FFT/DFT and you want the best phase correlation from any single FFT result bin. I think the premise that using an FFT somehow "makes" the data periodic is why the standard interpretation of phase as referenced to bin 0 doesn't work for most actual non-periodic data. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Reply by ●March 25, 20062006-03-25
Ron N. wrote:> robert bristow-johnson wrote: > > Ron N. wrote:...> > > then any average phase offset for a least squared fit of a sinusoid > > > at one of the bin frequencies to the unknown signal is from the center > > > (N/2) of that particular (FIR equivalent) bin filter. > > > > no. that won't be true for the odd indices of X[k]. maybe true for the even > > indices but what you say here is off by an amount of pi radians for odd k. > > Yes. You have to reference the phase on the odd indices as negative > with respect to the phase of the even indices when referencing > phases to the center (N/2) of the sample vector.the *polarity* of the odd indices are negative with respect to the *polarity* of the even indices. the *phase* is off by +/- pi radians or +/- 180 degrees. but i think this is sorta sematic and believe that here we have some common ground. at least up to this point.> But interpreting FFT phase in this manner, and referencing that > phase to sample N/2, gives the smallest squared error between > any single bin to any arbitrary sinusoid of bin or non-bin frequency > in the input sample vector.i don't see that and i see no mathematical reason to believe such is true. is this about applying a Hann window or similar so the data in the middle of the window has "more effect" or more weight? if it is not, then i have to repeat that there is no qualitative difference between sample N/2 and sample 0 (except maybe that sample 0 is aligned with the origin which is why phase is measured relative to sample 0).> Referencing to sample 0 (without the odd rotation) only > gives the smallest error for sample sinusoids of an exact bin > frequency.i don't know what this is about. could you elaborate more about the basis of this assertion you are making?> So referencing to sample 0 will give wrong results when > any waveform which is not periodic in N is fed to an FFT/DFT and > you want the best phase correlation from any single FFT result bin.i see no justification to this statement. me still suspects this has something to do with the fact that the Hann window or whatever other window used might be maximum around sample N/2.> I think the premise that using an FFT somehow "makes" the > data periodic ...well, what you're doing when you apply an FFT (let's say "DFT" since the fast algorithm isn't at issue) to "most actual non-periodic data" is *first*, before the DFT ever sees the data, you are yanking N samples out of a longer (possibly arbitrarily long) sequence of sampled data. that is an act of windowing and the DFT is not doing it. if your window is a Hann or some other decent non-rectangular window, the samples in the middle will have more weight (i still do not know if this is the source of your assertion that this "gives the smallest squared error between any single bin to any arbitrary sinusoid of bin or non-bin frequency in the input sample vector". so i'm guessing. i'm trying to put what i would call rigorous language to what seems to me an unjustified mathematical assertion. now, once you've yanked N samples out of the stream using a rectangular window or Hann window or whatever window, that act of windowing will have consequences in the frequency domain (the smearing) and this is happening before the DFT sees it. once you pass it to the DFT, the DFT effectively periodically extends that set of N samples to a periodic sequences which is identical for samples x[0] to x[N-1] and repeats those samples forever in both directions (period is N) and then the DFT gives you the complex Fourier series coefficients for that periodic function and since the input periodic function is also discrete, then the Fourier coefficients are also periodic. (discrete sampling in one domain means periodic transform data in the other domain.) so X[k] is also periodic.> ... is why the standard interpretation of phase as referenced to > bin 0 doesn't work for most actual non-periodic data.and this also i have not seen explicitly spelled out nor mathematically justified. i think i disagree with it, but am not confident that i understand the meaning so i am still hedging until i get some clearer, more explicitly mathematical expression of the statement. but my hunch is still, whatever it is you're saying here is not true and not justified. if you want, i'll think about this a little and try to express in unambiguous mathematical terms what i think you might be saying. i'd rather you do it because there is less likelihood of you misinterpreting your position than of me doing it. r b-j
