time domain zero padding VS fft interpolation between bins

Hi,

Suppose I have N samples and I want to do one N point FFT and a 4N
point FFT with zeros padding. Can do get the 4N-FFT by interpolating
the N-FFT? Is there a formula? Is the interpolation fast than just do
a zero-padded 4N-FFT?

Thanks

On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:

>Hi,
>
>Suppose I have N samples and I want to do one N point FFT and a 4N
>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>the N-FFT? Is there a formula? Is the interpolation fast than just do
>a zero-padded 4N-FFT?
>
>Thanks

Hi,
  I'm not sure why no one has replied to 
your interesting questions.  In any case, 
here are my "two cents."

Off the top of my head: even when we account for 
the gain loss due to interpolation, I'm willing to 
bet a bottle of Pilsner Urquell that interpolating 
the N-point FFT results (by a factor 
of four) will NOT give the same results as a 
4N-point FFT performed on a zero padded 
time-domain sequence.

I say that for the following reason.  Say our 
N-point time sequence was a pure tone whose 
frequency was exactly at a N-point FFT's bin center.
The N-point FFT's positive-freq mag results would 
be a single non-zero sample (an impulse sample). 
Interpolating that would yield an interpolated 
sequence whose samples are proportional to the 
impulse response of the interpolation filter.

The 4N-point FFT magnitude results (of a zero-padded 
time sequence) will be a sin(x)/x sequence.
So there's no guarantee that the impulse response 
of the interpolation filter will be equal to a 
sin(x)/x sequence.

You should be able to model these two processes 
fairly quickly with some software (MathCAD, 
MATLAB, etc.).

Good Luck,
[-Rick-]

On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:

>Hi,
>
>Suppose I have N samples and I want to do one N point FFT and a 4N
>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>the N-FFT? Is there a formula? Is the interpolation fast than just do
>a zero-padded 4N-FFT?
>
>Thanks

Hi (again),

   Thinking more about this, perhaps 
an interpolation filter of the proper shape and 
duration can be used to make this "interpolate a 
N-point FFT" process work in an acceptable manner.
And maybe we can be clever in performing the convolutional 
filtering to minimize its computational workload. 

Humm, ... I need to put some additional thought into 
this idea.

[-Rick-]

On Oct 1, 11:17&#4294967295;am, SYL <sya...@gmail.com> wrote:
> Hi,
>
> Suppose I have N samples and I want to do one N point FFT and a 4N
> point FFT with zeros padding. Can do get the 4N-FFT by interpolating
> the N-FFT? Is there a formula? Is the interpolation fast than just do
> a zero-padded 4N-FFT?

A zero-padded FFT is the same as a rectangular window in the
frequency domain which is identical to sin(x)/x or Sinc (actually
Dirichlet kernel for finite length FFTs) interpolation in the time
domain. However, most interpolation is done with much shorter
kernels, which results in a loss of filter quality.  If you need the
quality and a rectangular filter response, a zero-padded FFT might
be a faster way to get the interpolated results than a sufficiently
wide interpolation kernel (windowed Sinc, or similar).  Or a shorter
interpolation kernel (or other interpolation method, such as
bidirectional IIR filtering) may fit your quality requirements.

.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Ron N wrote:

> On Oct 1, 11:17 am, SYL <sya...@gmail.com> wrote:

>>Suppose I have N samples and I want to do one N point FFT and a 4N
>>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>>the N-FFT? Is there a formula? Is the interpolation fast than just do
>>a zero-padded 4N-FFT?

A 4N point FFT should take about 4*log2(4)=8 times as
long as an N point FFT.

> A zero-padded FFT is the same as a rectangular window in the
> frequency domain which is identical to sin(x)/x or Sinc (actually
> Dirichlet kernel for finite length FFTs) interpolation in the time
> domain. However, most interpolation is done with much shorter
> kernels, which results in a loss of filter quality.  If you need the
> quality and a rectangular filter response, a zero-padded FFT might
> be a faster way to get the interpolated results than a sufficiently
> wide interpolation kernel (windowed Sinc, or similar).  Or a shorter
> interpolation kernel (or other interpolation method, such as
> bidirectional IIR filtering) may fit your quality requirements.

I would say it depends a lot on why you want the interpolation.

You could do a linear or cubic spline interpolation fairly fast,
which might be good enough for some cases.  Maybe even a higher
order spline.  If the spectrum is fairly smooth the spline will
likely be pretty close.  If it isn't, then, will, why are you
doing this?  (It likely matters.)

-- glen

Rick Lyons wrote:
> On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:

>>Suppose I have N samples and I want to do one N point FFT and a 4N
>>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>>the N-FFT? Is there a formula? Is the interpolation fast than just do
>>a zero-padded 4N-FFT?
(snip)

> I say that for the following reason.  Say our 
> N-point time sequence was a pure tone whose 
> frequency was exactly at a N-point FFT's bin center.
> The N-point FFT's positive-freq mag results would 
> be a single non-zero sample (an impulse sample). 
> Interpolating that would yield an interpolated 
> sequence whose samples are proportional to the 
> impulse response of the interpolation filter.

> The 4N-point FFT magnitude results (of a zero-padded 
> time sequence) will be a sin(x)/x sequence.
> So there's no guarantee that the impulse response 
> of the interpolation filter will be equal to a 
> sin(x)/x sequence.

But once you know N it isn't hard to figure out the response
of sin(x)/x for all N.  (With the complication of circular
boundary conditions, so hopefully N isn't too small.)

Then it is just matrix multiply, so hopefully N isn't too big.

-- glen