3
$\begingroup$

Imaging we have a signal $x$, which is segmented to 50% overlapped vectors $x_1,x_2,..,x_m$ , and we intent to compute FFT of each segment. Is there anyway that we can reduce computation of FFT of each block. I mean, if FFT of $x_1$ has taken and we know $x_2$ has a 50% overlap with $x_1$, so half of $x_2$, have already went through some FFT process.

  • Is there any method or modification that reuse this information to reduce computations of FFT of each segment based on information of the previous segment?
$\endgroup$
  • 1
    $\begingroup$ Unfortunately a %50 overlap is insufficient for a noticeable performance gain from such a reduction in computation... You may look for sliding DFT, sliding FFT or pruned FFT for similar examples. $\endgroup$ – Fat32 May 31 '17 at 10:56
  • $\begingroup$ @Fat32 , I am developing an idea on this regard, and I feel your point (about insufficiency of 50% overlap) is close to it. How much overlap suffices for a noticeable gain?, how? I'd appreciate if you share your knowledge on that. $\endgroup$ – MimSaad May 31 '17 at 13:30
  • 1
    $\begingroup$ this question and its answers might shed some light. $\endgroup$ – Fat32 May 31 '17 at 14:37
  • 1
    $\begingroup$ It is what I was looking for, exactly! $\endgroup$ – MimSaad Jun 2 '17 at 15:53
1
$\begingroup$

One method might be to split your length $N$ overlapping FFTs up, so that you compute the $\frac{N}{2}$-point FFT of each block of samples that come in. Then, in order to get the $N$-point FFT that you want, you can combine the last two $\frac{N}{2}$-point results with appropriate twiddle factors.

This would technically do what you want, but in most cases (especially on contemporary PC-like platforms with good FFT libraries), it's not going to be appreciably (if at all) faster than just doing the overlapping $N$-point FFTs.

$\endgroup$
  • $\begingroup$ Interesting method, I looked out the web for it, thank you. But this recursive FFT computation from smaller FFTs method you've mentioned seem to increases computations overall and I think it is more suitable when memory is limited. However though, I wasn't aware of such a trick, thank you! $\endgroup$ – MimSaad May 30 '17 at 13:42
  • $\begingroup$ It shouldn't require any more computations; in fact, this is why the FFT works. The complexity reduction comes from decomposing one transform into multiple smaller transforms. You would just be doing one of those steps here manually. As I said before, though, it probably won't be any faster for you. $\endgroup$ – Jason R May 30 '17 at 14:56

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.