Hi, I have been using a relatively small (256 point) FFT and some interpolation to estimate the actual input frequency when I do not have a bin at exactly that frequency. However I was wondering if any such method exists for estimating the phase at that frequency? Is it possible to interpolate the real and complex numbers of adjacent bins? If I zero pad and use a large FFT (say 2048 points) I have all the information I need, but to reduce computational requirements I would like to compute a smaller FFT and interpolate. Kind Regards, David Graham.

# FFT Interpolation of complex numbers

Started by ●April 23, 2012

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote:> Hi, > I have been using a relatively small (256 point) FFT and some > interpolation to estimate the actual input frequency when I do not have > a bin at exactly that frequency. > > However I was wondering if any such method exists for estimating the > phase at that frequency? Is it possible to interpolate the real and > complex numbers of adjacent bins? > > If I zero pad and use a large FFT (say 2048 points) I have all the > information I need, but to reduce computational requirements I would > like to compute a smaller FFT and interpolate.Phase, as a universal measure, is meaningless. Phase compared to what? If your answer is phase compared to <some time>, and <some time> cannot be traced back to the timing of the samples that are getting Fourier transformed, then you're out of luck. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com

Posted by ●April 23, 2012

On Monday, April 23, 2012 8:31:44 AM UTC-7, Lightbulb85 wrote:> Hi, > I have been using a relatively small (256 point) FFT and some interpolation > to estimate the actual input frequency when I do not have a bin at exactly > that frequency. > > However I was wondering if any such method exists for estimating the phase > at that frequency? Is it possible to interpolate the real and complex > numbers of adjacent bins? > > If I zero pad and use a large FFT (say 2048 points) I have all the > information I need, but to reduce computational requirements I would like > to compute a smaller FFT and interpolate. > > Kind Regards, > David Graham.There is a summary of techniques in pages 11-44 of a recent thesis: Phase and Frequency Estimation: High-Accuracy and Low-Complexity Techniques by Yizheng Liao http://www.wpi.edu/Pubs/ETD/Available/etd-042511-144644/unrestricted/YLiao.pdf Here is one of the source papers: Estimation of Frequency, Amplitude, and Phase from the DFT of a Time Series Barry G. Quinn IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 45, NO. 3, MARCH 1997 http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/AnalisisFrecuencial/00558515.pdf Dale B. Dalrymple

Posted by ●April 23, 2012

On Monday, April 23, 2012 9:17:57 AM UTC-7, Tim Wescott wrote:> On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote: > > > Hi, > > I have been using a relatively small (256 point) FFT and some > > interpolation to estimate the actual input frequency when I do not have > > a bin at exactly that frequency. > > > > However I was wondering if any such method exists for estimating the > > phase at that frequency? Is it possible to interpolate the real and > > complex numbers of adjacent bins? > > > > If I zero pad and use a large FFT (say 2048 points) I have all the > > information I need, but to reduce computational requirements I would > > like to compute a smaller FFT and interpolate. > > Phase, as a universal measure, is meaningless. > > Phase compared to what? If your answer is phase compared to <some time>,> and <some time> cannot be traced back to the timing of the samples that > are getting Fourier transformed, then you're out of luck. >FFT based phase estimates are referenced to the time position of the window that selected the set of points to be transformed. Dale B. Dalrymple

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 09:50:22 -0700, dbd wrote:> On Monday, April 23, 2012 9:17:57 AM UTC-7, Tim Wescott wrote: >> On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote: >> >> > Hi, >> > I have been using a relatively small (256 point) FFT and some >> > interpolation to estimate the actual input frequency when I do not >> > have a bin at exactly that frequency. >> > >> > However I was wondering if any such method exists for estimating the >> > phase at that frequency? Is it possible to interpolate the real and >> > complex numbers of adjacent bins? >> > >> > If I zero pad and use a large FFT (say 2048 points) I have all the >> > information I need, but to reduce computational requirements I would >> > like to compute a smaller FFT and interpolate. >> >> Phase, as a universal measure, is meaningless. >> >> Phase compared to what? If your answer is phase compared to <some >> time>, and <some time> cannot be traced back to the timing of the >> samples that are getting Fourier transformed, then you're out of luck. >> >> > FFT based phase estimates are referenced to the time position of the > window that selected the set of points to be transformed.Exactly. And many questioners who ask about FFT's at the level that this guy is asking don't seem to understand this. Hence my attempt at elucidation. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 10:31:44 -0500, "Lightbulb85" <david.graham.1985@n_o_s_p_a_m.hotmail.co.uk> wrote:>Hi, >I have been using a relatively small (256 point) FFT and some interpolation >to estimate the actual input frequency when I do not have a bin at exactly >that frequency. > >However I was wondering if any such method exists for estimating the phase >at that frequency? Is it possible to interpolate the real and complex >numbers of adjacent bins? > >If I zero pad and use a large FFT (say 2048 points) I have all the >information I need, but to reduce computational requirements I would like >to compute a smaller FFT and interpolate. > >Kind Regards, >David Graham. > >The second part of this paper: http://ericjacobsen.org/FTinterp.pdf shows a method where the complex coefficients that you would get by zero-padding from N to M can be individually interpolated with, for example, a four-point complex-arithmetic dot product of a deterministic vector against the four samples near the peak. Each interpolated sample requires a four-point complex dot product, but in practice you can do a binary (or other) search and home in on the peak pretty quickly. This avoids having to do long FFTs, but I don't know whether it's computationally simple enough for your application. Eric Jacobsen Anchor Hill Communications www.anchorhill.com

Posted by ●April 24, 2012

My thanks to Dale B. Dalrympk and Eric Jacobsen, your responses were very helpful.> >The second part of this paper: > >http://ericjacobsen.org/FTinterp.pdf > >shows a method where the complex coefficients that you would get by >zero-padding from N to M can be individually interpolated with, for >example, a four-point complex-arithmetic dot product of a >deterministic vector against the four samples near the peak. Each >interpolated sample requires a four-point complex dot product, but in >practice you can do a binary (or other) search and home in on the peak >pretty quickly. > >This avoids having to do long FFTs, but I don't know whether it's >computationally simple enough for your application. > > >Eric Jacobsen >Anchor Hill Communications >www.anchorhill.com >

Posted by ●April 24, 2012

My thanks to Dale B. Dalrympk and Eric Jacobsen, your responses were very helpful.> >The second part of this paper: > >http://ericjacobsen.org/FTinterp.pdf > >shows a method where the complex coefficients that you would get by >zero-padding from N to M can be individually interpolated with, for >example, a four-point complex-arithmetic dot product of a >deterministic vector against the four samples near the peak. Each >interpolated sample requires a four-point complex dot product, but in >practice you can do a binary (or other) search and home in on the peak >pretty quickly. > >This avoids having to do long FFTs, but I don't know whether it's >computationally simple enough for your application. > > >Eric Jacobsen >Anchor Hill Communications >www.anchorhill.com >

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 10:31:44 -0500, "Lightbulb85" <david.graham.1985@n_o_s_p_a_m.hotmail.co.uk> wrote:>Hi, >I have been using a relatively small (256 point) FFT and some interpolation >to estimate the actual input frequency when I do not have a bin at exactly >that frequency. > >However I was wondering if any such method exists for estimating the phase >at that frequency? Is it possible to interpolate the real and complex >numbers of adjacent bins? > >If I zero pad and use a large FFT (say 2048 points) I have all the >information I need, but to reduce computational requirements I would like >to compute a smaller FFT and interpolate. > >Kind Regards, >David Graham. > >The second part of this paper: http://ericjacobsen.org/FTinterp.pdf shows a method where the complex coefficients that you would get by zero-padding from N to M can be individually interpolated with, for example, a four-point complex-arithmetic dot product of a deterministic vector against the four samples near the peak. Each interpolated sample requires a four-point complex dot product, but in practice you can do a binary (or other) search and home in on the peak pretty quickly. This avoids having to do long FFTs, but I don't know whether it's computationally simple enough for your application. Eric Jacobsen Anchor Hill Communications www.anchorhill.com

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 09:50:22 -0700, dbd wrote:> On Monday, April 23, 2012 9:17:57 AM UTC-7, Tim Wescott wrote: >> On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote: >> >> > Hi, >> > I have been using a relatively small (256 point) FFT and some >> > interpolation to estimate the actual input frequency when I do not >> > have a bin at exactly that frequency. >> > >> > However I was wondering if any such method exists for estimating the >> > phase at that frequency? Is it possible to interpolate the real and >> > complex numbers of adjacent bins? >> > >> > If I zero pad and use a large FFT (say 2048 points) I have all the >> > information I need, but to reduce computational requirements I would >> > like to compute a smaller FFT and interpolate. >> >> Phase, as a universal measure, is meaningless. >> >> Phase compared to what? If your answer is phase compared to <some >> time>, and <some time> cannot be traced back to the timing of the >> samples that are getting Fourier transformed, then you're out of luck. >> >> > FFT based phase estimates are referenced to the time position of the > window that selected the set of points to be transformed.Exactly. And many questioners who ask about FFT's at the level that this guy is asking don't seem to understand this. Hence my attempt at elucidation. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com

Posted by ●April 23, 2012

On Monday, April 23, 2012 9:17:57 AM UTC-7, Tim Wescott wrote:> On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote: > > > Hi, > > I have been using a relatively small (256 point) FFT and some > > interpolation to estimate the actual input frequency when I do not have > > a bin at exactly that frequency. > > > > However I was wondering if any such method exists for estimating the > > phase at that frequency? Is it possible to interpolate the real and > > complex numbers of adjacent bins? > > > > If I zero pad and use a large FFT (say 2048 points) I have all the > > information I need, but to reduce computational requirements I would > > like to compute a smaller FFT and interpolate. > > Phase, as a universal measure, is meaningless. > > Phase compared to what? If your answer is phase compared to <some time>,> and <some time> cannot be traced back to the timing of the samples that > are getting Fourier transformed, then you're out of luck. >FFT based phase estimates are referenced to the time position of the window that selected the set of points to be transformed. Dale B. Dalrymple

Posted by ●April 23, 2012

On Monday, April 23, 2012 8:31:44 AM UTC-7, Lightbulb85 wrote:> Hi, > I have been using a relatively small (256 point) FFT and some interpolation > to estimate the actual input frequency when I do not have a bin at exactly > that frequency. > > However I was wondering if any such method exists for estimating the phase > at that frequency? Is it possible to interpolate the real and complex > numbers of adjacent bins? > > If I zero pad and use a large FFT (say 2048 points) I have all the > information I need, but to reduce computational requirements I would like > to compute a smaller FFT and interpolate. > > Kind Regards, > David Graham.There is a summary of techniques in pages 11-44 of a recent thesis: Phase and Frequency Estimation: High-Accuracy and Low-Complexity Techniques by Yizheng Liao http://www.wpi.edu/Pubs/ETD/Available/etd-042511-144644/unrestricted/YLiao.pdf Here is one of the source papers: Estimation of Frequency, Amplitude, and Phase from the DFT of a Time Series Barry G. Quinn IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 45, NO. 3, MARCH 1997 http://www.ingelec.uns.edu.ar/pds2803/Materiales/Articulos/AnalisisFrecuencial/00558515.pdf Dale B. Dalrymple

Posted by ●April 23, 2012

On Mon, 23 Apr 2012 10:31:44 -0500, Lightbulb85 wrote:> Hi, > I have been using a relatively small (256 point) FFT and some > interpolation to estimate the actual input frequency when I do not have > a bin at exactly that frequency. > > However I was wondering if any such method exists for estimating the > phase at that frequency? Is it possible to interpolate the real and > complex numbers of adjacent bins? > > If I zero pad and use a large FFT (say 2048 points) I have all the > information I need, but to reduce computational requirements I would > like to compute a smaller FFT and interpolate.Phase, as a universal measure, is meaningless. Phase compared to what? If your answer is phase compared to <some time>, and <some time> cannot be traced back to the timing of the samples that are getting Fourier transformed, then you're out of luck. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com

Posted by ●April 23, 2012

Hi, I have been using a relatively small (256 point) FFT and some interpolation to estimate the actual input frequency when I do not have a bin at exactly that frequency. However I was wondering if any such method exists for estimating the phase at that frequency? Is it possible to interpolate the real and complex numbers of adjacent bins? If I zero pad and use a large FFT (say 2048 points) I have all the information I need, but to reduce computational requirements I would like to compute a smaller FFT and interpolate. Kind Regards, David Graham.