Linear vs Circular Convolution

Linear convolution vs circular convolution

Linear convolution (what nature does)

If:

• x[n] = transmitted signal
• h[n] = channel impulse response (multipath)

Then the received signal is:

y[n] = x[n] * h[n]

This means:

• Past symbols spill into future symbols
• Causes inter-symbol interference (ISI)
• DFT of y[n] is not a simple product

Circular convolution (what DFT assumes)

The DFT assumes periodic signals:

y[n] = x[n] ⊛ h[n], where indices wrap around modulo N

Only under circular convolution does the DFT satisfy:

Y[k] = X[k] · H[k]

This is what enables one-tap frequency-domain equalization.

What happens in the real channel (linear convolution)

The channel performs linear convolution:

y[n] = Σ_l=0^Lh−1 h[l] x[n-l]

But because:

• CP absorbs the “spillover”
• Receiver discards CP before DFT

The useful part of the received symbol becomes:

y[n] = Σ_l=0^Lh−1 h[l] x[(n-l) mod N]

Modulo indexing = circular convolution

Linear vs Circular Convolution Deep Dive

Linear convolution example

Let:

x[n] = [1, 2, 3]

h[n] = [4, 5]

Compute linear convolution:

y[0] = 1*4 = 4
y[1] = 1*5 + 2*4 = 13
y[2] = 2*5 + 3*4 = 22
y[3] = 3*5 = 15

y[n] = [4, 13, 22, 15]

Length = 3 + 2 - 1 = 4 → output longer than input

Circular convolution example

x[n] = [1, 2, 3], h[n] = [4, 5, 0] (padded to length 3)

y[0] = 1*4 + 2*0 + 3*5 = 19
y[1] = 1*5 + 2*4 + 3*0 = 13
y[2] = 1*0 + 2*5 + 3*4 = 22

y[n] = [19, 13, 22]

Summary of differences

Feature	Linear Convolution	Circular Convolution
Signal length	N+M-1	N
Wrap-around	No	Yes (mod N)
DFT property	No simple product	Y[k] = X[k] · H[k]
Natural / artificial	Nature (channel)	FFT assumption
OFDM role	Causes ISI if unchecked	Enables one-tap equalization

Understanding mod N in Circular Convolution

Linear Convolution

For two discrete-time sequences x[n] and h[n],

y[n] = x[n] * h[n] = Σ x[k] · h[n − k]
       (k = −∞ to ∞)
      

• Output length: L_x + L_h − 1
• Signals are assumed to be zero outside their defined duration
• Used to model LTI systems and physical communication channels

Circular Convolution

For two N-point sequences x[n] and h[n],

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

• Output length: N
• Signals are assumed to be periodic with period N
• Commonly used in DFT/FFT-based systems (e.g., OFDM)

Key Mathematical Difference

• Linear convolution uses h[n − k] (no wrapping)
• Circular convolution uses h[(n − k) mod N], causing wrap-around

1. What does mod N mean?

“mod N” means wrap around when you reach N.

Think of a clock:

• 13 mod 12 = 1
• 14 mod 12 = 2

The same idea applies in circular convolution.

2. Why do we need mod N?

In circular convolution, signals are assumed to be periodic.

• If the index becomes negative → wrap to the end
• If the index exceeds N−1 → wrap to the beginning

3. Simple Example (N = 4)

x[n] = [x₀, x₁, x₂, x₃]
h[n] = [h₀, h₁, h₂, h₃]
      

Circular convolution formula:

y[n] = Σ x[k] · h[(n − k) mod 4]
       (k = 0 to 3)
      

4. Compute One Output Sample (n = 1)

y[1] = x[0]h[(1−0) mod 4]
     + x[1]h[(1−1) mod 4]
     + x[2]h[(1−2) mod 4]
     + x[3]h[(1−3) mod 4]
      

Expression	Value
(1−0) mod 4	1
(1−1) mod 4	0
(1−2) mod 4	−1 → 3
(1−3) mod 4	−2 → 2

y[1] = x₀h₁ + x₁h₀ + x₂h₃ + x₃h₂
      

This shows how negative indices wrap around using mod N.

5. Visual Interpretation

0 → 1 → 2 → 3 → back to 0
      

• −1 → 3
• −2 → 2
• 4 → 0

6. Summary

• Linear convolution → no wrapping
• Circular convolution → indices wrap using mod N
• mod N enforces periodicity

Further Reading

1.