fourier transform - Online DFT Algorithm

I have a discrete audio stream $x$ that needs to be processed in real-time. Specifically, as the each new sample is received, I would like to compute a Fourier transform of the last $n$ samples of the signal. So, for example, upon receiving the $i^{th}$ sample, I would like to compute the Fourier transform of the sequence $(x_{i-n+1}, x_{i-n+2}, \dots, x_{i-1}, x_{i})$. However this means that when I receive the $(i+1)^{th}$ sample, I will be computing the Fourier transform of $(x_{i-n+2}, x_{i-n+3}, \dots, x_{i}, x_{i+1})$, which is almost identical to the first sequence. So my question is, having already computed the Fourier transform of the first sequence, is there some way to compute the new Fourier transform from that, instead of having to recompute it from scratch each time?

Answer

(Note: the paper pointed by hotpaw2's link is actually describing in more detail the algorthm I presented here)

Consider a data window length of $N$ samples from $n=0$ to $n=N-1$. Let your original data window be $x_1[n]$, whose first sample is $x_{old} = x_1[0]$. Now your new data set is denoted as $x_2[n]$ whose samples are actually one sample left shifted verisons of $x_1[n]$, i.e. $x_2[n] = x_1[n+1]$ for $n=0,1,...,N-2$ plus a new arrived data to position $n=N-1$ which is denoted as $x_{new} = x_2[N-1]$.

Then the following algorithm will compute the N-point DFT, $X_2[k]$ of the new data set $x_2[n]$ from that of the already computed and stored N-point DFT $X_1[k]$ of the old data set $x_1[n]$ as:

$$ X_2[k] = e^{j \frac{2\pi}{N}k }( X_1[k] + (x_{new} - x_{old}) ) $$

for each $k=0,1,...,N-1$. This updated computation of $X_2[k]$ from pre-computed $X_1[k]$ requires N complex multiplications and N real additions. Compared to a direct N-point FFT which requires $N \log_2(N)$ complex MACs, this would therefore be an improvement by a factor of $\log_2(N)$ which for example would render to a factor of 10 when $N=1024$ using low level languages such as C.