# FFT Interpolation of complex numbers

Started 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

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 <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
```
```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
>
> 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 <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
```
```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
```
```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
>
>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
>
>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
>
```