Overview
Overlap-save processes blocks with FFT convolution, keeps only the valid output section, and carries the overlap into the next block.
CoreSource checked
Overlap-Save
Performs long convolution by reusing overlapped input blocks and discarding invalid edges.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Signal Processing
- Difficulty
- Intermediate
- Family
- Fast Convolution
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
block convolutionfft multiplyoverlap regiondiscarded prefix
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(blocks * n log n)
Worst
O(blocks * n log n)
Space
O(block size)
When to Use
- Use when filtering noisy signals needs block convolution.
- Use when the input matches the assumptions behind fast Convolution.
When Not to Use
- Avoid when sampling rate, phase, or boundary assumptions are unknown.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Performs long convolution by reusing overlapped input blocks and discarding invalid edges
- Uses block convolution and fft multiply to guide the work.
- Produces filtered signal.
Use Cases
- Filtering noisy signals
- Spectral analysis
- Audio and sensor processing
Inputs
- Sampled signal
- Filter or transform parameters
Outputs
- Filtered signal
- Spectrum or feature representation
Key Formulas (1)
Frequency convolution
yblock = inversefft(fft(block) · fft(kernel))
y_block = inverse_fft(fft(block) * fft(kernel))Computes each block convolution efficiently in the frequency domain.
Pseudocode
- 1.Validate sampling rate, window, boundary, and parameter choices
- 2.Prepare the signal state, coefficients, or transform workspace
- 3.Apply the filter, transform, or measurement rule to each sample or frame
- 4.Handle boundaries and normalization consistently
- 5.Return the filtered signal, coefficients, or feature values
Canonical Example
- Input
- Overlap-Save
- Output
- Filtered signal
- Explanation
- Overlap-Save applies block convolution to produce filtered signal.
Implementation Notes
- Document sample rate, windowing, and normalization conventions.
- Keep the block convolution step separate enough to test independently.
- Keep sampling rate, window size, latency, and boundary conventions explicit in tests.
Common Pitfalls
- Boundary handling and normalization choices can change the interpretation of the result.
- Test edge cases, not only clean examples.
- Ignoring sampling rate, boundary handling, or phase behavior can make the output misleading.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow the input signal beside the filtered, transformed, or reconstructed output.
Step 1 of 5: Validate sampling rate, window, boundary, and parameter choices
signal-processing-mechanismNotes
Overlap-Save should be used with the assumptions and tradeoffs of fast Convolution in mind.
Sources (1)
What each reference supports for this entry.
Discrete-Time Signal Processing
BookSignal-processing reference for digital filters, convolution, spectral analysis, windows, resampling, and transform-based methods.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toOverlap-Add
Overlap-save handles block convolution boundaries by discarding corrupted samples.
Related Algorithms
Tags
Signal ProcessingConvolutionFrequency DomainSliding Window