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.
1. **Overlap the Blocks**:
    - Each block overlaps with the previous block by a specific number of samples. This helps maintain continuity in the final output.
1. **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.
1. **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.
1. **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.

#### 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.
1. **Overlap the Blocks**:
    - To ensure smooth transitions, each new block overlaps with the last 2 samples of the previous block.
1. **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.25, 2, 0.75]
    - Discard the first 2 values, keeping the non-overlapping part: **[1, 2.5, 4.25, 2, 0.75]**
1. **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]**
1. **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.