What is the difference between linear and circular convolution?

Linear convolution has no wraparound — the output length is M+N−1. Circular convolution assumes periodicity, so values wrap around. To get linear convolution from FFT (which naturally gives circular), zero-pad both sequences to length ≥ M+N−1.

Why is FFT-based convolution faster?

Direct convolution requires O(MN) multiplications. FFT-based convolution requires O((M+N)log(M+N)) operations — FFT both sequences, multiply pointwise, and inverse FFT. For long sequences (M, N > 100), the FFT approach is dramatically faster.

How does discrete convolution relate to FIR filters?

A FIR filter IS discrete convolution. The filter coefficients form the impulse response h[n], and the filter output y[n] = Σ h[k]·x[n−k] is exactly the convolution of the input with the impulse response.

Discrete Convolution

Quick Answer

Discrete convolution computes y[n] = Σ x[k]·h[n−k], where the sum runs over all valid indices. For finite sequences x of length M and h of length N, the output y has length M+N−1. For example, convolving x = [1, 2, 3] with h = [1, -1] gives y = [1, 1, 1, -3]: multiply-and-shift each element of h against x and sum the overlapping products. Discrete convolution is the basis of FIR digital filtering, and it can be computed efficiently using the FFT when sequences are long.

Calculate this instantly on LAPLACE Calculator →

Computing Discrete Convolution by Hand

The sliding-window method works as follows: write x[k] and flip h[k] to get h[-k]. Slide h[-k] to the right by n positions to get h[n-k]. At each position n, multiply overlapping elements and sum. For x = [2, 3, 1] and h = [1, 2]: at n=0, only x[0]h[0] overlaps → y[0] = 2·1 = 2. At n=1, x[0]h[1] + x[1]h[0] → y[1] = 2·2 + 3·1 = 7. At n=2, x[1]h[1] + x[2]h[0] → y[2] = 3·2 + 1·1 = 7. At n=3, x[2]h[1] → y[3] = 1·2 = 2. Result: [2, 7, 7, 2]. An equivalent table method arranges the partial products in a grid and sums diagonals.

Key Formulas

Discrete Convolution in Digital Signal Processing

Every FIR (Finite Impulse Response) digital filter performs discrete convolution. The filter coefficients h[0], h[1], ..., h[N-1] define the impulse response, and the filter output is the convolution of the input samples with these coefficients. A moving average filter has all coefficients equal to 1/N. A differencing filter has coefficients [1, -1]. Sophisticated audio equalizers, noise cancelers, and communication receivers all implement carefully designed convolution kernels running in real time on DSP hardware, computing millions of multiply-accumulate operations per second.

Compute discrete convolution Instantly

Get step-by-step solutions with AI-powered explanations. Free for basic computations.

Open Calculator

Linear vs. Circular Convolution

Linear convolution (the standard definition) produces an output of length M+N-1 with no wraparound. Circular convolution assumes both sequences are periodic with some period L, so values that shift off one end wrap around to the other. The DFT naturally computes circular convolution of period N (the DFT length). To get linear convolution from the DFT/FFT, zero-pad both sequences to length ≥ M+N-1 before transforming. This ensures the circular result is long enough to contain the complete linear convolution without aliasing. This is the standard technique for fast convolution in practice.

Fast Convolution Using FFT: The Overlap-Add Method

When convolving a very long input stream x (like real-time audio) with a filter h of length N, you cannot wait for the entire input before computing. The overlap-add method segments x into blocks of length L, convolves each block with h using FFT (requiring DFT size ≥ L+N-1), and adds overlapping output segments together. Each block is processed independently, enabling real-time streaming. The overlap-save method is an alternative that uses circular convolution directly, discarding the corrupted output samples at block boundaries. Both methods produce exactly the same result as direct linear convolution.

Relationship to the Z-Transform

Just as the Laplace transform converts continuous convolution to multiplication, the Z-transform converts discrete convolution to multiplication: Z{x*h} = X(z)·H(z). The transfer function H(z) of a discrete system is the Z-transform of its impulse response h[n]. Cascading two discrete systems multiplies their Z-domain transfer functions. This parallel between continuous and discrete domains means all the analysis techniques from Laplace transform theory — poles, zeros, stability, frequency response — have direct Z-transform counterparts for digital systems.

Frequently Asked Questions

Flip one sequence, slide it across the other from left to right, and at each position multiply overlapping elements and sum. The output at position n is Σ x[k]·h[n−k] for all valid k values where both indices are in range.

Master Your Engineering Math

Join thousands of students and engineers using LAPLACE Calculator for instant, step-by-step solutions.

Start Calculating Free →