# Efficient FFT (or SFFT) for adjacent parts of signal with overlap?

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?
• 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. – Fat32 May 31 '17 at 10:56
• @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. – MimSaad May 31 '17 at 13:30
• this question and its answers might shed some light. – Fat32 May 31 '17 at 14:37
• It is what I was looking for, exactly! – MimSaad Jun 2 '17 at 15:53

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.

• 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! – MimSaad May 30 '17 at 13:42
• 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. – Jason R May 30 '17 at 14:56