Overlap Save method

The English used in this article or section may not be easy for everybody to understand. You can help Wikipedia by reading Wikipedia:How to write Simple English pages, then simplifying the article. (November 2024)

The overlap-save method is a technique used in digital signal processing (DSP) to perform convolution on long signals efficiently. Convolution is a mathematical operation that combines two signals to produce a third signal, often used in filtering or modifying signals in DSP.

When processing a long signal using a finite impulse response (FIR) filter, directly calculating the convolution can be slow and require a lot of memory. The overlap-save method speeds up this process by splitting the long signal into smaller blocks and processing each one separately. This approach saves memory and reduces the amount of computation needed.^[1]

The method breaks the input signal into overlapping blocks, processes each block, and then combines the results to form the final output. Here are the main steps:^[1]

1. Divide the Signal into Blocks:
   • The input signal is divided into blocks, each with a length equal to the filter length plus the desired output length minus 1.
   • For example, if the filter length is 4 and the block length is 6, each block will overlap by 3 samples.
2. Overlap the Blocks:
   • Each block overlaps with the previous block by a specific number of samples. This helps maintain continuity in the final output.
3. Apply the Filter to Each Block:
   • Perform convolution on each block using the FIR filter. The Fast Fourier transform (FFT) is often used here to make the process faster.^[2]
4. Save Only the Needed Part:
   • Discard the overlapping section at the beginning of each processed block, keeping only the non-overlapping part as the final output for that block.
5. Combine All Blocks:
   • After filtering each block and discarding the overlaps, the remaining parts are combined to form the complete output signal.

We have:

• An input signal x[n]=[1,2,3,4,5,6,7,8,9]
• A finite impulse response (FIR) filter h[n]=[1,0.5,0.25]

The goal is to filter x[n] using the Overlap-Save Method.

1. Define the Block Length:
   • Since our FIR filter has a length of 3, we add 2 extra points (length of the filter minus 1) to the block. We choose a block length of 5 for each section of x[n].
   • Each block will have 5 samples.
2. Overlap the Blocks:
   • To ensure smooth transitions, each new block overlaps with the last 2 samples of the previous block.
3. Divide x[n] into Blocks:
   • With block length 5 and overlap of 2 samples, we divide x[n] as follows:
     • Block 1: [0, 0, 1, 2, 3] (starting with two zeros for padding)
     • Block 2: [2, 3, 4, 5, 6] (overlaps with last 2 samples of Block 1)
     • Block 3: [5, 6, 7, 8, 9] (overlaps with last 2 samples of Block 2)

We’ll apply the filter h[n]=[1,0.5,0.25] to each block using convolution.

1. Convolve Block 1: [0, 0, 1, 2, 3]
   • Convolution result (before discarding overlaps): [0, 0, 1, 2.5, 4, 2.75, 0.75]
   • Discard the first 2 values, keeping the non-overlapping part: [1, 2.5, 4, 2.75, 0.75]
2. Convolve Block 2: [2, 3, 4, 5, 6]
   • Convolution result (before discarding overlaps): [2, 4, 6.25, 8.5, 10.5, 5.5, 1.5]
   • Discard the first 2 values, keeping the non-overlapping part: [6.25, 8.5, 10.5, 5.5, 1.5]
3. Convolve Block 3: [5, 6, 7, 8, 9]
   • Convolution result (before discarding overlaps): [5, 8.5, 12.25, 14.5, 16.5, 7.75, 2.25]
   • Discard the first 2 values, keeping the non-overlapping part: [12.25, 14.5, 16.5, 7.75, 2.25]

Now, we combine the non-overlapping portions of each filtered block to get the final result.

• Filtered output from Block 1: [1, 2.5, 4, 2.75, 0.75]
• Filtered output from Block 2: [6.25, 8.5, 10.5, 5.5, 1.5]
• Filtered output from Block 3: [12.25, 14.5, 16.5, 7.75, 2.25]

Final Output Signal: [1, 2.5, 4, 2.75, 0.75, 6.25, 8.5, 10.5, 5.5, 1.5, 12.25, 14.5, 16.5, 7.75, 2.25] .

• Efficiency: By processing smaller blocks, this method uses less memory and is faster than direct convolution, especially for long signals.
• Real-Time Processing: This method is ideal for real-time systems where fast response is needed, such as in audio and image processing.

• Audio Processing: In real-time audio filtering, where the audio signal is too long to process in one go.
• Image processing: To apply filters to images where the data is processed in blocks.
• Telecommunications: To filter signals in real-time communications.^[1]

1. ↑ ^{1.0 1.1 1.2} Proakis, John G; Dimitris G., Manolakis. Digital Signal Processing: Principles, Algorithms, and Applications. ISBN 9780133942897.
2. ↑ Lyons, Richard G. (2011). Understanding Digital Signal Processing. ISBN 9780137027415.