1

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).

jiandingzhe
  • 141
  • 3

2 Answers2

2

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.

hotpaw2
  • 35,346
  • 9
  • 47
  • 90
2

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.