Circular vs Linear

When a DSP engineer wants to use the FFT to perform fast filtering, the key challenge is that the DFT naturally computes circular convolution while filters require linear convolution. Understanding the difference between these two operations and how to convert between them is one of the most practically important topics in digital signal processing.

GATE consistently tests this topic through numerical problems involving short sequences. The ability to quickly compute both circular and linear convolution, and to determine when they are equal, is essential for scoring in DSP questions.

Core Concept Explanation

Linear convolution is the standard operation performed by an LTI filter. If x[n] has L1 samples and h[n] has L2 samples, their linear convolution has L1+L2-1 samples. There is no periodicity assumption. The output correctly represents the filtered signal. This is the operation required in FIR filtering, edge detection, and most signal processing applications.

Circular convolution, on the other hand, is what you get when you multiply DFTs and take the IDFT. It assumes both sequences are periodic with period N. Samples that would extend beyond index N-1 in the output wrap around and add to the beginning. This wraparound is called time-domain aliasing and it corrupts the result compared to linear convolution when N is too small.

The central insight is: if you zero-pad both sequences to length N where N is at least L1+L2-1, then circular convolution of the padded sequences equals linear convolution of the original sequences. The zero-padding ensures there is enough room for the output to spread without any wraparound overlap.

Mathematical Expression

Linear convolution: y[n] = sum_{k=0}^{L2-1} h[k] x[n-k] where x[n] is zero for n outside 0 to L1-1. Output has L1+L2-1 nonzero values.

Circular convolution (N-point): y[n] = sum_{m=0}^{N-1} x[m] h[(n-m) mod N]. The modulo operation is what causes wraparound. Output always has exactly N values.

The condition for equality is simply N >= L1 + L2 - 1. When this is satisfied, zero-pad x[n] and h[n] to N points by appending zeros, then compute the N-point circular convolution. The first L1+L2-1 values will exactly match the linear convolution result.

Practical Understanding

The entire motivation for using DFT-based convolution in practice is computational speed. Direct linear convolution of an L1-point signal with an L2-point filter requires O(L1*L2) multiplications. Using FFT-based circular convolution reduces this to O(N log N) where N >= L1+L2-1. For large L1 and L2, this speedup is enormous. Audio effects processing, image convolution, and communication channel equalization all rely on this technique.

For very long input signals, overlap-add and overlap-save methods break the input into blocks and use DFT-based convolution on each block. These methods systematically handle the edge effects between adjacent blocks while retaining the speed advantage of FFT computation.

Given:
x[n] = {1, 2, 3}    (L1 = 3)
h[n] = {1, 1}        (L2 = 2)
Compute both linear convolution and 4-point circular convolution.

Why this formula applies:
Linear conv output length = L1+L2-1 = 3+2-1 = 4
For N=4: N >= L1+L2-1 = 4, so circular will equal linear.

Linear Convolution (direct):
y[0] = x[0]*h[0] = 1*1 = 1
y[1] = x[0]*h[1] + x[1]*h[0] = 1*1 + 2*1 = 3
y[2] = x[1]*h[1] + x[2]*h[0] = 2*1 + 3*1 = 5
y[3] = x[2]*h[1] = 3*1 = 3

Linear result: {1, 3, 5, 3}

Circular Convolution (N=4, zero-pad to N):
x[n] = {1, 2, 3, 0}  (zero-padded)
h[n] = {1, 1, 0, 0}  (zero-padded)
y[0] = 1*1+0*0+0*0+2*0 = 1  (h flipped: {1,0,0,1} shifted)
y[0] = x[0]*h[0]+x[3]*h[1]+x[2]*h[2]+x[1]*h[3] = 1*1+0*1+3*0+2*0 = 1
y[1] = x[1]*h[0]+x[0]*h[1]+x[3]*h[2]+x[2]*h[3] = 2*1+1*1+0*0+3*0 = 3
y[2] = x[2]*h[0]+x[1]*h[1]+x[0]*h[2]+x[3]*h[3] = 3*1+2*1+1*0+0*0 = 5
y[3] = x[3]*h[0]+x[2]*h[1]+x[1]*h[2]+x[0]*h[3] = 0*1+3*1+2*0+1*0 = 3

Circular result: {1, 3, 5, 3}

Final Answer:
Both give {1, 3, 5, 3} because N=4 = L1+L2-1.
They are equal. The FFT method can be used for filtering here.

Exam Tip: A 3-point circular convolution of a 3-point and a 2-point sequence will NOT equal their linear convolution because 3 < 3+2-1=4. Always check N >= L1+L2-1 before claiming equivalence. This is a common GATE trap.

Quick Revision

• Linear convolution output length = L1 + L2 - 1. No periodicity. Correct filter output.
• Circular convolution output length = N. Assumes periodic extension. Computed via DFT multiply.
• They are equal when N >= L1 + L2 - 1 and both inputs are zero-padded to length N.
• If N < L1+L2-1, the circular result suffers time-domain aliasing and the outputs differ.
• FFT-based linear convolution steps: zero-pad, FFT both, multiply, IFFT, take first L1+L2-1 samples.
• Overlap-add and overlap-save methods use this technique for long input sequences in block-wise fashion.
• Exam trap: A 3-point circular convolution of a 3-point and 2-point sequence is NOT the same as linear convolution. Need at least N=4.