FFT Interpolation of complex numbers

Started by Lightbulb85 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.


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 , and 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
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
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 , > and 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
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 > time>, and 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
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. > >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
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 >
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 >
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. > >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
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 > time>, and 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
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 , > and 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
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
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 , and 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
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.