Sign in

Not a member? | Forgot your Password?

Search compdsp

Search tips


Discussion Groups

FFT Spectral Analysis Software

Free Online Books

See Also

Embedded SystemsFPGA

Discussion Groups | Comp.DSP | FFT Interpolation of complex numbers

There are 7 messages in this thread.

You are currently looking at messages 1 to .


Is this discussion worth a thumbs up?

0

FFT Interpolation of complex numbers - Lightbulb85 - 2012-04-23 11:31:00

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.


Re: FFT Interpolation of complex numbers - Tim Wescott - 2012-04-23 12:17:00

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


Re: FFT Interpolation of complex numbers - dbd - 2012-04-23 12:40:00

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/0
0558515.pdf

Dale B. Dalrymple


Re: FFT Interpolation of complex numbers - dbd - 2012-04-23 12:50:00

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


Re: FFT Interpolation of complex numbers - Tim Wescott - 2012-04-23 13:19:00

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


Re: FFT Interpolation of complex numbers - Eric Jacobsen - 2012-04-23 13:55:00

On Mon, 23 Apr 2012 10:31:44 -0500, "Lightbulb85"
<d...@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


Re: FFT Interpolation of complex numbers - Lightbulb85 - 2012-04-24 04:07:00

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
>