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

# time domain zero padding VS fft interpolation between bins

Started by ●October 1, 2008

Posted by ●October 5, 2008

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? > >ThanksHi, 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-]

Posted by ●October 5, 2008

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? > >ThanksHi (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-]

Posted by ●October 6, 2008

On Oct 1, 11:17�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

Posted by ●October 6, 2008

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

Posted by ●October 6, 2008

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