# 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. May 31, 2017 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. May 31, 2017 at 13:30
• this question and its answers might shed some light. May 31, 2017 at 14:37
• It is what I was looking for, exactly! Jun 2, 2017 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.