"Circular Convolution Explained Mathematically with DFT"

Understanding Circular Convolution Using DFT

Convolution is a foundational tool in signal processing, crucial for systems analysis, filtering, and more. While linear convolution is commonly taught, circular convolution is particularly important when working with the Discrete Fourier Transform (DFT) and periodic signals.

What is Circular Convolution?

Circular convolution (also called cyclic convolution) assumes that signals are periodic. This means that when the index exceeds the length of the signal, it wraps around due to modulo operation.

It is defined as:

y[n] = Σk=0N-1 x[k] · h[(n - k) mod N]

The modulo operation introduces the "circular" behavior.

DFT and the Convolution Theorem

According to the Convolution Theorem:

Circular Convolution in Time Domain ⟺ Pointwise Multiplication in Frequency Domain

That is:

x[n] ⊛ h[n] ↔ DFT ↔ X[k] · H[k]

This property enables fast computation using FFT.

How to Perform Circular Convolution via DFT

1. Compute the DFT of both signals
2. Multiply them pointwise in the frequency domain
3. Take Inverse DFT of the result to get the circular convolution

Matrix-Based Example

Let’s consider two sequences of length N = 4:

• x[n] = {1, 2, 3, 4}
• h[n] = {1, -1, 1, -1}

Step 1: Compute DFT of x[n]

Use the DFT matrix:

W₄ = [[1,  1,  1,  1],

      [1, -j, -1,  j],

      [1, -1,  1, -1],

      [1,  j, -1, -j]]

X[k] = W₄ · x[n]

     = [[1,  1,  1,  1],       [[1],       [[10],

        [1, -j, -1,  j],   ×    [2],   =     [-2+2j],

        [1, -1,  1, -1],        [3],         [-2],

        [1,  j, -1, -j]]        [4]]         [-2-2j]

Step 2: Compute h[-n] mod N

In circular convolution, we use the time-reversed sequence:

h[n]       = { h[0], h[1], h[2], h[3] } = {1, -1, 1, -1}

h[-n] mod 4 = { h[0], h[3], h[2], h[1] } = {1, -1, 1, -1}

Note: The first element stays the same. The rest are reversed modulo N.

Step 3: Compute DFT of h[-n]

H[k] = W₄ · h[-n]

     = [[1,  1,  1,  1],       [[1],       [[0],

        [1, -j, -1,  j],   ×    [-1],  =     [0+4j],

        [1, -1,  1, -1],        [1],         [0],

        [1,  j, -1, -j]]        [-1]]        [0-4j]

Step 4: Multiply X[k] · H[k]

Y[k] = X[k] × H[k]

     = { 0, (–2+2j)(4j), 0, (–2–2j)(–4j) }

     = { 0, 8+8j, 0, 8–8j }

Step 5: Compute Inverse DFT of Y[k]

y[n] = IDFT{Y[k]} = {4, 0, -4, 0}

Result:
The circular convolution of x[n] and h[n] is: {4, 0, -4, 0}

Circular vs Linear Convolution

Property	Linear Convolution	Circular Convolution
Output length	N + M – 1	max(N, M) or N
Padding	Required (zero-padding)	None (assumes periodic signals)
Application	Time-domain filtering	Frequency-domain (FFT-based) processing

Applications

• Fast filtering using FFT
• Overlap-add and overlap-save methods
• Spectral analysis
• Efficient signal correlation

Conclusion

Circular convolution is essential for efficient computation of signal processing operations in the frequency domain. When used with DFT, it simplifies convolution into simple multiplication. Understanding its mathematical basis and practical application helps you unlock high-speed algorithms and digital filter implementations.