OverlapSave

Overlap-Save is an efficient method for computing the linear convolution of a long input sequence with a finite impulse response (FIR) filter using the fast Fourier transform (FFT). The technique splits the input into overlapping blocks and performs circular convolution in the frequency domain, discarding the portion of each block that contains wrap-around artifacts, and then concatenates the valid outputs to form the final result.

To implement Overlap-Save, choose an FFT size N that is at least as large as the impulse response length L. The impulse response h[0..L-1] is padded with zeros to length N and its FFT H is precomputed. The input is processed in blocks of length N, where consecutive blocks overlap by L-1 samples. For each block, form a length-N vector by taking the current N-L+1 new samples of x and prepending the L-1 samples carried over from the previous block. Compute the FFT of this block, multiply by H pointwise, and take the inverse FFT. The first L-1 samples of the result are discarded, and the remaining N-L+1 samples are appended to the output. The process then advances by N-L+1 samples.

Advantages include reduced computational cost for long sequences, especially when the impulse response is short relative to the block size, and good suitability for real-time or streaming processing. The method typically pairs with real-valued FFTs to improve efficiency. It is often compared with the Overlap-Add method; both use FFT-based convolution and block processing but differ in how they form and combine blocks.

Limitations include the need to select appropriate N and handle the initial and final boundaries with padding, which can introduce latency and edge effects. Overlap-Save is widely used in digital filtering, audio processing, and other real-time signal processing applications.