time domain zero padding VS fft interpolation between bins

Started by SYL 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