# time domain zero padding VS fft interpolation between bins

Started by October 1, 2008
```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&#2013266080;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

```