Overlap Save method

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.

Why use the overlap-save method?

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.

How the overlap-save method works

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. 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.
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.

Example of the overlap-save method

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.

Steps in the overlap-save method

Step 1: Divide the signal into overlapping blocks

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)

Step 2: Apply the FIR filter to each block

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]

Step 3: combine the filtered blocks

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] .

Benefits of the overlap-save method

• 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.

Where the overlap-save method is used

• 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.