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:
# **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.
# **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 
# **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.
# **Overlap the Blocks**:
#* To ensure smooth transitions, each new block overlaps with the last 2 samples of the previous block.
# **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.

# **Convolve Block 1**: [0, 0, 1, 2, 3]
#* Convolution result (before discarding overlaps): [0, 0, 1, 2.5, 4.25, 2, 0.75]
#* Discard the first 2 values, keeping the non-overlapping part: **[1, 2.5, 4.25, 2, 0.75]**
# **Convolve Block 2**: [2, 3, 4, 5, 6]
#* Convolution result (before discarding overlaps): [2, 4, 6, 7.75, 9.5, 4.25, 1.5]
#* Discard the first 2 values, keeping the non-overlapping part: **[6, 7.75, 9.5, 4.25, 1.5]**
# **Convolve Block 3**: [5, 6, 7, 8, 9]
#* Convolution result (before discarding overlaps): [5, 8.5, 11.25, 13, 14.75, 6.5, 2.25]
#* Discard the first 2 values, keeping the non-overlapping part: **[11.25, 13, 14.75, 6.5, 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.25, 2, 0.75**]
* Filtered output from Block 2: [**6, 7.75, 9.5, 4.25, 1.5**]
* Filtered output from Block 3: [**11.25, 13, 14.75, 6.5, 2.25**]

**Final Output Signal**: [1, 2.5, 4.25, 2, 0.75, 6, 7.75, 9.5, 4.25, 1.5, 11.25, 13, 14.75, 6.5, 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.

## Reference