State and prove circular convolution property

Statement

If x₁(n) ↔ X₁(k) and x₂(n) ↔ X₂(k) are N-point DFT pairs, then

x₁(n) ⊛ x₂(n) ↔ X₁(k) · X₂(k)

where the N-point circular convolution is x₃(n) = Σ (m = 0 to N−1) x₁(m) x₂((n − m) mod N). Multiplying DFTs in the frequency domain is equivalent to circular convolution in the time domain.

Proof

Let X₃(k) = X₁(k)X₂(k). The inverse DFT is

x₃(n) = (1/N) Σ (k = 0 to N−1) X₁(k) X₂(k) e^(j2πkn/N)

Substitute the definitions X₁(k) = Σ_m x₁(m) e^(−j2πkm/N) and X₂(k) = Σ_l x₂(l) e^(−j2πkl/N):

x₃(n) = (1/N) Σ_k Σ_m Σ_l x₁(m) x₂(l) e^(j2πk(n − m − l)/N)

Interchange the order of summation:

x₃(n) = Σ_m Σ_l x₁(m) x₂(l) · [ (1/N) Σ_k e^(j2πk(n − m − l)/N) ]

The bracket is a geometric sum:

(1/N) Σ (k = 0 to N−1) e^(j2πk(n − m − l)/N) = 1 if (n − m − l) is a multiple of N, i.e. l = (n − m) mod N; and 0 otherwise.

So only l = (n − m) mod N survives:

x₃(n) = Σ (m = 0 to N−1) x₁(m) x₂((n − m) mod N)

which is the N-point circular convolution of x₁ and x₂. ∎

Remarks

• Both sequences must be padded to the same length N.
• To make circular convolution equal to linear convolution, choose N ≥ L₁ + L₂ − 1.
• The dual property: multiplication x₁(n)x₂(n) ↔ (1/N) X₁(k) ⊛ X₂(k).