2
$\begingroup$

As a response to this question I have proposed interpolating new samples in a DFT (meaning the frequency samples of an existing DFT result) sufficient to be the new samples that if we were to take the inverse DFT we would get a zero padded sequence. The property referenced is that a zero padded time domain sequence will create interpolated samples in between the existing samples of the DFT of the original sequence. The new samples are determined from a circular convolution of the DFT with the Dirichlet Kernel, and when done properly, the inverse FFT of the result will be the original sequence zero-padded out to the longer length.

In deriving the details of implementing that, my most efficient solution (in a long round-about path to get there not seeing the forest for the trees) ended up being to simply take the inverse FFT, zero pad that and take the FFT.

This leads to my question now in that if our intention was to create an interpolated FFT from a given FFT (that would be the FFT of a zero padded inverse FFT), is there a more direct approach that would be more efficient than inverse FFT, zero pad, FFT based on the convolution property stated? Can we predict the frequency domain samples without having to go to the time domain in a way that would be more efficient?

$\endgroup$
10
  • $\begingroup$ If you want to compute all of the uniform frequency samples in the range $[-\pi,\pi)$ (or $[0 , 2\pi)$) then, afaik, the DFT (via FFT) approach is the most efficient way to "exactly" compute that whole set of interpolated samples... If you need just a subset of the interpolated frequency samples, may be CTA, ChirpZ etc can help... $\endgroup$
    – Fat32
    Dec 3, 2021 at 15:31
  • $\begingroup$ @Fat32 yes will need ALL and in the case when zero padding out to an integer multiple then we can reuse the original samples (so only need about half the samples when doubling for example) $\endgroup$ Dec 3, 2021 at 15:57
  • $\begingroup$ Why not just use the DTFT? $\endgroup$
    – MBaz
    Dec 3, 2021 at 17:24
  • $\begingroup$ @MBaz can you elaborate? I always did the DTFT as a zero padded FFT but that too is done from the time domain samples. The question here is if we can get the missing samples of the DTFT from the FFT samples directly (and the answer is yes of course as there is only one solution - but then is there a more efficient and direct approach over what I am doing: which is IFFT first and then DTFT $\endgroup$ Dec 3, 2021 at 18:15
  • 1
    $\begingroup$ @DanBoschen If all you need is more samples, or if the zero-padded interpolated samples happen to fall on the frequencies you want, then I think zero-padding is the best approach. If you want to interpolate at very specific frequencies, then it's possible that you'd have to pad with lots of zeros, and in the process calculating many more samples than you needed. This is the case where I think the DTFT could be attractive, since it does not need any padding. $\endgroup$
    – MBaz
    Dec 3, 2021 at 23:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.