How it works
Circular convolution of two N-point sequences x[n] and h[n] is defined as y[n] = Σ x[m]·h[(n−m) mod N] for m = 0 to N−1. This is equivalent to multiplying their N-point DFTs: Y[k] = X[k]·H[k], then taking IDFT{Y[k]}. Linear convolution of an N1-point and N2-point sequence produces an (N1+N2−1)-point output. To make circular convolution equal to linear convolution, both sequences must be zero-padded to length N ≥ N1+N2−1 before DFT. The matrix method for circular convolution uses a circulant matrix: the first row is h[0], h[N−1], h[N−2], ..., h[1], and each subsequent row is a cyclic right shift of the previous.
Key points to remember
The condition N ≥ L+M−1 (where L and N1 are the signal and filter lengths) must be satisfied for circular convolution to give the same result as linear convolution — this single inequality is tested in almost every DSP exam numerical. Overlap-add method breaks a long input into L-sample blocks, computes N-point circular convolution (N ≥ L+M−1) for each block, and overlaps and adds adjacent output blocks to reconstruct the full linear convolution. Overlap-save method uses N-point circular convolution but discards the first M−1 samples of each block output because they contain circular aliasing. The DFT-based convolution requires O(N log N) operations versus O(N²) for direct linear convolution — for N = 1024, this is roughly 100× faster.
Exam tip
The examiner always asks you to compute the 4-point circular convolution of two given sequences using the DFT method and verify it matches linear convolution after zero-padding — show the DFT, pointwise multiplication, IDFT, and zero-padding steps separately and compare the two results.