About

Discrete linear convolution is the foundation of signal processing, control theory, and polynomial multiplication. An error in manual computation propagates through every output sample. Given two finite sequences f[n] of length N and g[n] of length M, the output contains N + M − 1 samples. Each output sample requires up to min(N, M) multiply-accumulate operations. This tool computes every sample exactly and renders the flip-and-slide mechanism so you can verify each step visually. It assumes zero-indexed, causal sequences with no implicit zero-padding beyond the defined length.

The calculator handles signed and fractional values. It does not approximate. For sequences longer than a few hundred samples, consider FFT-based convolution (O(N log N)). This tool uses the direct sum formula which is exact and transparent for educational and verification purposes. Pro tip: polynomial multiplication is identical to convolution of coefficient vectors. Enter coefficients as your signal to multiply polynomials.

Formulas

The discrete linear convolution of two finite sequences f and g produces output sequence y:

y[n] = (f * g)[n] = M−1∑k=0 f[k] ⋅ g[n − k]

where n ranges from 0 to N + M − 2, and any index outside the defined range yields 0.

Where f[k] = first input sequence of length N, g[n] = second input sequence of length M, y[n] = output (convolved) sequence of length N + M − 1, and k = summation index. The operation "flip-and-slide" means g is reversed and shifted by n positions, then multiplied element-wise with f and summed.

Sum preservation property: ∑ y[n] = (∑ f[k]) ⋅ (∑ g[k]). This identity serves as a quick verification check for the result.

Reference Data

Property	Formula / Value	Notes
Output Length	N + M − 1	For inputs of length N and M
Commutativity	f * g = g * f	Order does not affect result
Associativity	(f * g) * h = f * (g * h)	Useful for cascaded systems
Distributivity	f * (g + h) = f * g + f * h	Linear operation
Identity Element	δ[n] = {1, 0, 0, …}	Kronecker delta / unit impulse
Time Complexity (Direct)	O(N ⋅ M)	Nested summation
Time Complexity (FFT)	O(N log N)	Where N ≥ len(f) + len(g) − 1
Polynomial Degree	deg(f) + deg(g)	Product polynomial degree
Energy Conservation	∑ y[n] = (∑ f[k]) ⋅ (∑ g[k])	Sum of output equals product of sums
Max Output Value	≤ max(\|f\|) ⋅ ∑ \|g[k]\|	Upper bound on amplitude
Circular vs Linear	Circular pads to period N	This tool computes linear (aperiodic)
Causal System Check	g[n] = 0 for n < 0	Assumed here (zero-indexed)
BIBO Stability	∑ \|g[k]\| < ∞	Finite sequences always BIBO stable
Deconvolution	Inverse operation via polynomial division	Not computed here; numerically unstable
Cross-correlation Link	R_fg[n] = f[−n] * g[n]	Correlation uses conjugate flip
Z-Transform	Y(z) = F(z) ⋅ G(z)	Convolution ↔ multiplication in Z-domain

Frequently Asked Questions

The output length is always N + M − 1 regardless of the ratio between N and M. However, computational cost is O(N ⋅ M), so a 5-sample signal convolved with a 1000-sample signal requires 5000 multiply-accumulate operations. The result is mathematically identical regardless of which signal you call f or g due to commutativity.

Use the sum preservation property: the sum of all output samples must equal the product of the sums of the two input sequences. For example, if f = [1, 2, 3] (sum 6) and g = [1, 1] (sum 2), the output sum must be 12. This tool displays this verification automatically.

Linear convolution (computed here) produces N + M − 1 samples with no periodicity assumption. Circular convolution wraps the sequences to a period L and produces exactly L samples. If you zero-pad both sequences to length ≥ N + M − 1 before circular convolution, the results are identical. DFT-based methods inherently compute circular convolution.

Yes. Convolution of coefficient vectors is algebraically identical to polynomial multiplication. Enter the coefficients in ascending power order. For (1 + 2x) ⋅ (3 + 4x + 5x²), enter f = [1, 2] and g = [3, 4, 5]. The output [3, 10, 13, 10] represents 3 + 10x + 13x² + 10x³.

The convolution formula requires evaluating g[n − k], which is the time-reversal of g shifted by n. Visually, you flip g around index 0, then slide it across f. At each position, overlapping samples are multiplied pairwise and summed. This "flip-and-slide" interpretation is the standard pedagogical approach and directly maps to the mathematical definition.

Yes. The maximum output value is bounded by max(|f|) ⋅ ∑ |g[k]|. For example, convolving [1, 1, 1] with [1, 1, 1] yields a peak of 3 at the center, despite both inputs having maximum value 1. In audio processing, this necessitates normalization to prevent clipping.