Side-by-side comparison
| Parameter | Linear Convolution | Circular Convolution |
|---|---|---|
| Definition | y[n] = Σ x[k]·h[n−k], k = −∞ to ∞ | y_c[n] = Σ x[k]·h[(n−k) mod N], k = 0 to N−1 |
| Output length | L + M − 1 for inputs of length L and M | Always N (same as DFT size); may have aliasing if N < L+M−1 |
| Computation | Direct sum; O(L·M) multiplications | Via N-point FFT: O(N log N); faster for large N |
| Periodicity assumption | No periodicity assumed | Both sequences assumed periodic with period N |
| DFT relationship | Not directly computed by DFT | y_c[n] = IDFT{X[k]·H[k]} — pointwise product in DFT domain |
| Equivalence condition | Linear = circular when N ≥ L + M − 1 | Zero-pad both x and h to length N ≥ L + M − 1 first |
| Time-domain aliasing | Does not occur | Occurs if N < L + M − 1 — tails wrap around |
| Application | FIR filter direct-form implementation in MATLAB conv() | Overlap-add and overlap-save FFT-based filtering |
| MATLAB function | conv(x, h) | ifft(fft(x,N).*fft(h,N)) with N ≥ L+M−1 |
| Real example | Filtering 100 audio samples with a 10-tap FIR: output is 109 samples | Overlap-add block processing of audio in 256-sample frames |
Key differences
Linear convolution of length-L and length-M sequences produces L+M−1 samples; circular convolution of N-point sequences always produces N samples. They give the same result only when N ≥ L + M − 1 and both sequences are zero-padded to length N. Without zero-padding, the last M−1 samples of the circular result are corrupted by time-domain aliasing (the tail wraps around). Overlap-add filtering — used in real-time audio processing — exploits this equivalence by choosing N = next power of 2 above L + M − 1.
When to use Linear Convolution
Use linear convolution when computing the exact output of an FIR filter in direct form — for example, convolving a 100-sample speech frame with a 20-tap FIR low-pass filter to get 119 output samples using MATLAB's conv().
When to use Circular Convolution
Use circular convolution (via FFT) when processing long signals in blocks for speed — for example, implementing a 256-tap FIR audio equaliser using the overlap-add method with 1024-point FFTs on an ARM Cortex-M7 for real-time playback.
Recommendation
For GATE, always compute linear convolution by hand and then check if circular convolution matches it given the N value. For placements in DSP roles, choose FFT-based circular convolution for any problem where filter length exceeds 32 taps — it is faster and that's what every real DSP implementation uses.
Exam tip: GATE gives two length-4 sequences and asks for the 4-point circular convolution — use the DFT property: compute X[k], H[k] as 4-point DFTs, multiply pointwise, take IDFT; also check if it matches linear convolution (it will only if L+M−1 ≤ 4).
Interview tip: An interviewer at a DSP or audio company will ask why overlap-add is preferred over direct FIR convolution for long signals — explain that N log N grows slower than N², so a 1024-point FFT multiplies 1024-element blocks in ~10,000 operations versus ~1,000,000 for direct convolution.