Is there a FFT algorithm with the circular buffering?

Question

I have an audio signal and i want to process it sequentially. Is there an algorithm which allows to modify the spectrum of a signal when i remove a part of signal and add the other one?

For example, i obtain a set of 256 samples of input data. Then i do 256 FFT and i want to add the result spectrum to 16384 FFT which is the big buffer. So i have the big FFT buffer with the good frequency resolution and i should sometimes modify to correspond the spectrum as if i do 16384 FFT.

The main objective is i need to avoid 16384 FFT because it's quite expensive. The way i want to optimize is (in time domain):

1. Shift the buffer to 256 samples;
2. Place the new samples to last 256 entries in buffer;
3. Make 16384 FFT.

So whenever the 256 sapmles come i need to recompute 16384 FFT whereas i've already have 16384 - 256 computed samples. Is there way perform such task (circular buffering FFT)?

My thoughs was (in frequency domain):

1. Multiply the 16384 FFT buffer by the complex sinusoid (that coresponds to circular shift the signal in time domain to 256 samples);
2. Calculate 256 FFT of new portion of signal;
3. Expand the spectrum to 16384 by inserting zeroes between bins (it's corresponds duplication of time domain signal);
4. Mix the signal with removing duplication of the expanded spectrum (by convolving with sinc function), and zero last 256 samples (by convolving with sinc function).

Is there way to avoid two comlementar convolving in the last step?

Answer 1

The listed algorithm seems to be form of sliding DFT, summing narrow rectangular slice windows. In general, an FFT (O(NLogN) is faster than a sliding DFT of slice size b (O(b*N)), for b > LogN , due to a factorization that is not available to slices alone. Thus, avoiding the 16384 FFT seems to be more expensive than just doing the FFT (if you actually want all 8192 correct bin results), since 256 > log(16384).