0
$\begingroup$

I have data whose latter half are all-zero. For example, data=[a, b, c, d, 0, 0, 0, 0], and front_half=[a, b, c, d]. Is there any way to obtain FFT(data), by some compute-efficient transform on the FFT(front_half)?

I made some work on the equations. The even items in FFT(data) are just equal with FFT(front_half). But the odd items in FFT(data) seems twisted with dot-multiply with a time-domain weight vector, which looks hard to be calculated from the FFT(front_half).

$\endgroup$
1
$\begingroup$

The computationally efficient way is to do an IFFT/zero-pad/FFT. It's usually less efficient to do a circular Sinc interpolation (to create the effect of a rectangular window in the other domain) for any large number of extra points. Any other interpolation is less accurate.

$\endgroup$
1
$\begingroup$

There are no really noteworthy savings here: for a half-zero data set, only the first butterfly operation is trivial and can be replaced by a copy over the zeroed elements. Everything afterwards is business as usual. So you can have something like 9*512 butterfly operations rather than 10*512 butterflies, a saving of 10%. With larger transforms, the savings make for an even smaller percentage.

$\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.