Discrete Convolution
Discrete convolution computes (x * h)[n] = Σ_{k=−∞}^{∞} x[k]·h[n−k], summing the element-wise products of one sequence with a reversed and shifted version of the other. For finite sequences of lengths M and N, the output has M + N − 1 samples. Discrete convolution is the fundamental operation in FIR digital filtering, polynomial multiplication, and discrete-time LTI system analysis, with its z-transform equivalent Y(z) = X(z)·H(z) mirroring the Laplace-domain relationship Y(s) = X(s)·H(s).
What Is Discrete Convolution?
Discrete convolution is the operation that combines two discrete-time sequences x[n] and h[n] to produce an output sequence y[n] = (x * h)[n] = Σ_{k=−∞}^{∞} x[k]·h[n−k]. It is the discrete-time counterpart of the continuous convolution integral (f * g)(t) = ∫f(τ)g(t−τ)dτ, with summation replacing integration and sequence indices replacing continuous time. Discrete convolution is the defining input-output relationship for discrete-time linear time-invariant (LTI) systems: if h[n] is the impulse response (output when input is δ[n]), then the output for any input x[n] is y[n] = x[n] * h[n]. This relationship parallels the continuous-time Laplace-domain analysis at www.lapcalc.com, where Y(s) = X(s)·H(s).
Key Formulas
Discrete Convolution Formula and Computation
For two finite sequences x = [x₀, x₁, ..., x_{M-1}] and h = [h₀, h₁, ..., h_{N-1}], the discrete convolution produces y of length M + N − 1, computed as y[n] = Σ_{k=max(0,n-N+1)}^{min(n,M-1)} x[k]·h[n−k]. For example, x = [1, 2, 3] convolved with h = [1, 1] gives y[0] = 1·1 = 1, y[1] = 2·1 + 1·1 = 3, y[2] = 3·1 + 2·1 = 5, y[3] = 3·1 = 3, producing y = [1, 3, 5, 3]. The computation requires M·N multiply-accumulate operations. This is equivalent to multiplying polynomials: (1 + 2z⁻¹ + 3z⁻²)(1 + z⁻¹) = 1 + 3z⁻¹ + 5z⁻² + 3z⁻³, which connects to z-transform analysis just as continuous convolution connects to Laplace transforms.
Compute discrete convolution Instantly
Get step-by-step solutions with AI-powered explanations. Free for basic computations.
Open CalculatorDiscrete-Time Convolution in Signal Processing
Every FIR (Finite Impulse Response) digital filter implements discrete convolution: the filter coefficients h[0], h[1], ..., h[N−1] define the impulse response, and filtering input x[n] requires computing y[n] = Σ_{k=0}^{N-1} h[k]·x[n−k] at each sample. A 64-tap lowpass FIR filter performs 64 multiply-accumulate operations per output sample. At 48 kHz audio sample rate, this requires 3.07 million MACs per second — easily handled by modern DSP processors operating at hundreds of MFLOPS. Moving average filters are the simplest FIR example: a length-N moving average has coefficients h[k] = 1/N for all k, computing the running mean of the last N samples. Matched filters in radar and communications maximize SNR by convolving the received signal with a time-reversed copy of the transmitted waveform.
Linear vs. Circular Discrete Convolution
Linear convolution produces an output of length M + N − 1 and is the standard convolution operation. Circular (cyclic) convolution wraps the output modulo N, producing a length-N result: y_circ[n] = Σ_{k=0}^{N-1} x[k]·h[(n−k) mod N]. The DFT naturally computes circular convolution: IDFT{DFT{x} · DFT{h}} = x ⊛ h (circular). To use FFT for efficient linear convolution, zero-pad both sequences to length ≥ M + N − 1 before applying DFT, which makes the circular result equal the linear result. The overlap-add and overlap-save algorithms implement this for streaming signals, processing long inputs in blocks while maintaining continuity. This FFT-based approach reduces complexity from O(MN) to O(N log N), crucial for real-time audio, image, and communications processing.
Connection to Z-Transform and Laplace Transform
The z-transform plays the same role for discrete convolution that the Laplace transform plays for continuous convolution. The convolution theorem states: Z{x * h} = X(z)·H(z), converting the summation operation into multiplication in the z-domain. For a discrete-time LTI system with transfer function H(z) = Σ h[n]z⁻ⁿ, the output z-transform is Y(z) = X(z)·H(z), directly analogous to the Laplace-domain Y(s) = X(s)·H(s). The bilinear transform s = (2/T)(z−1)/(z+1) maps between z-domain and s-domain, enabling conversion of continuous-time Laplace designs to discrete implementations. This continuity between transform domains is why mastering the Laplace transform at www.lapcalc.com provides a foundation for all transform-based signal analysis.
Related Topics in convolution operations
Understanding discrete convolution connects to several related concepts: discrete time convolution, and discrete convolution formula. Each builds on the mathematical foundations covered in this guide.
Frequently Asked Questions
Master Your Engineering Math
Join thousands of students and engineers using LAPLACE Calculator for instant, step-by-step solutions.
Start Calculating Free →