1
$\begingroup$

I have trouble accepting the merits of zero padding in the frequency domain to give more points in FFT. Wonder if anyone else has similar thoughts.

The mathematical 'proof'for the validity of zero padding in the time domain shows that the original FFT points coincide with the interpolated points from the zero-padded time signal where the frequency bins correspond, but as far as I can tell, this in no way proves that the interpolation is correct or even meaningful.

When a section of a time history of length T is selected from which to produce an FFT, it is implicitly assumed that the section repeats from the beginning to the end of time so the resulting FFT has bins at frequencies of n/t only for integer vales of n (otherwise the sections would not repeat perfectly). Therfore, if more FFT points are required, the sensible/corect thing to do is stuff zeros between the FFT bins, which could also be achieved by concatenating several of the time sections before producing an FFT. Not very useful though, I admit.[Essentially, as far as 'the FFT is concerned'

If the time history is a very short transient, and otherwise the signal is zero, or very close to zero, then zero padding may actually (dare I say it!) increase the resolution because it adds information to the signal.

$\endgroup$
  • $\begingroup$ Also note that in FFT implementations, the most efficient (data size to computation time ratio) results are computed from powers-of-2-sized data inputs. That alone is a decent enough reason for data padding where it makes sense. $\endgroup$ – Florian Castellane Oct 20 '16 at 21:43
  • 2
    $\begingroup$ @FlorianCastellane that's not universally true – for example, the FFTW has implementations that work on non-powers-of-2 sizes about as well as for powers of 2! $\endgroup$ – Marcus Müller Oct 20 '16 at 21:47
  • $\begingroup$ Yes, they still work. If they run with a lower complexity please do send me a link, as I am most interested. $\endgroup$ – Florian Castellane Oct 20 '16 at 21:48
  • 1
    $\begingroup$ The difference in FFT execution efficiency between lengths that are powers of 2 and lengths that are the product of 2 and other very small primes is not that great for large FFTs. $\endgroup$ – hotpaw2 Oct 20 '16 at 23:37
  • 1
    $\begingroup$ uhm, can you describe what a "correct" or "meaningful" interpolation is? what makes an interpolation incorrect or not meaningful? $\endgroup$ – robert bristow-johnson Oct 21 '16 at 4:47
2
$\begingroup$

Zero-padding data for a longer FFT is equivalent to interpolation by a (periodic) Sinc kernel. Interpolation by a (periodic) Sinc kernel can reconstruct points between samples of a signal that was strictly bandlimited (to below the Nyquist frequency) prior to sampling. See: https://ccrma.stanford.edu/~jos/resample/Theory_Ideal_Bandlimited_Interpolation.html . This is a property of bandlimited signals (e.g. a linear-phase "brick-wall" bandlimiting FIR filter looks a lot like a Sinc function).

A lot of real-world data can be made close enough to bandlimited to meet existing or needed S/N criteria, and thus a zero padded FFT is "close enough" to "work" as needed.

It is not necessary to implicitly assume the repetition of a window of FFT data for all uses of an FFT. The phase vocoder and fast convolution algorithms require the assumption that the data is windowed and not necessarily periodic in FFT aperture width, otherwise one could end up with a contradiction regarding the data samples across overlapped or adjacent windows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.