Overview
Convolution measures how one sequence, kernel, or impulse response overlaps another at each shift. It is central to filtering, image processing, and systems analysis.
FoundationSource checked
Convolution
Combines two signals or arrays by sliding one over the other and summing pointwise products.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Signal Processing
- Difficulty
- Beginner
- Family
- Filtering
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 5
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
kernelsliding windowoverlap sumboundary handling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(nk)
Average
O(nk)
Worst
O(nk)
Space
O(n)
When to Use
- Use it for smoothing, filtering, feature extraction, and linear time-invariant systems.
- Use direct convolution for small kernels.
- Use FFT-based convolution for large inputs when boundary handling is understood.
When Not to Use
- Avoid it when the operation needed is correlation and kernel reversal matters.
- Avoid assuming one boundary convention fits every application.
- Avoid FFT convolution for tiny kernels where direct methods are simpler.
What It Does
- Slides a kernel over data
- Computes weighted local sums
Use Cases
- Audio filtering
- Image filtering
- Feature extraction
Inputs
- Signal or image
- Kernel
Outputs
- Filtered signal or image
Key Formulas (1)
Discrete convolution
y[i] = ∑(x[i − k] · h[k])
y[i] = sum(x[i - k] * h[k])Combines a signal or image with a kernel around each position.
Pseudocode
- 1.Place the kernel at the first output position
- 2.Multiply overlapping input values by kernel weights
- 3.Sum the products
- 4.Write the sum to the output
- 5.Move the kernel and repeat
Canonical Example
- Input
- samples = [1, 2, 3, 2, 1]
- Output
- transformed or filtered samples
- Explanation
- Convolution: The algorithm reads local or frequency structure from the sample sequence.
Implementation Notes
- State the padding, stride, and output-size convention explicitly.
- For separable kernels, use two one-dimensional passes when possible.
- For FFT methods, pad enough to avoid circular convolution artifacts.
Common Pitfalls
- Confusing convolution with cross-correlation.
- Ignoring padding and boundary behavior.
- Using the wrong output size convention: full, same, or valid.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a kernel window sliding across samples or pixels.
Step 1 of 5: Place the kernel at the first output position
kernel-slideNotes
In many machine-learning libraries, operations called convolution are technically cross-correlation unless the kernel is reversed.
Sources (1)
What each reference supports for this entry.
Discrete-Time Signal Processing
BookSignal-processing reference covering convolution, systems, and frequency-domain interpretation.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byConvolutional Neural Network
Machine Learning · Core
CNN layers apply learned convolutions to grid-like inputs.
Compare with thisUsed byTemplate Matching
Image Processing · Core
Template matching is commonly implemented as correlation or convolution over image windows.
Compare with thisRelationships
View full relationship pageUsed byConvolutional Neural Network
CNN layers apply learned convolutions to grid-like inputs.
Prerequisite ofFIR Filter
FIR filters compute finite convolutions with filter coefficients.
Related Algorithms
Tags
Signal ProcessingFilteringImage Processing