Connexions

You are here: Home » Content » Circular Convolution
Content Actions

Circular Convolution

Module by: Richard Baraniuk

Summary: Introduction to circular convolution.

  • DSP-speak for the operation
    y=ℋx y ℋ x (1)
    when ℋℋ is a circulant matrix corresponding to an LSI system (Figure 1).
  • Write out matrix multiply y=ℋx y ℋ x
    ·=⋯⋯⋯⋯→⋮⋮⋮⋮↓ · ⋯ ⋯ ⋯ ⋯ → ⋮ ⋮ ⋮ ⋮ ↓ (2)
    where the · is in the nth n th row.
    yn=∑k=0N-1ℋnkxk y n k 0 N 1 ℋ n k x k (3)
    where ℋ ℋ is a circulant matrix and ℋnk=hn-kmodN ℋ n k h n k N
matmult.png
Figure 1: ℋ ℋ is LSI.
yn=∑k=0N-1hn-kmodNxk y n k 0 N 1 h n k N x k (4)
y= h ⊛ N x y h ⊛ N x (5)
yn= h ⊛ N x n y n h ⊛ N x n (6)

Notation

Since impulse response hh completely describes ℋℋ, we often write: Figure 2 and Figure 3.
matmult2.png
Figure 2
matmult3.png
Figure 3

Inner Product Interpretation of Circular Convolution

Define the time reversal matrix ℛℛ as a matrix that reverses the time axis of a column vector (Figure 4).
ℛhk=h-kmodN ℛ h k h k N (7)
trm1.png
Subfigure 4.1: hh.
trm2.png
Subfigure 4.2: flip h h.
trm3.png
Subfigure 4.3: flip hmodN flip h N i.e.: to periodize with a period of NN.
trm4.png
Subfigure 4.4: ℛh ℛ h .
Figure 4: N=4 N 4 .
h0modNh-1modNh-2modNh-3modN=h0modNh3modNh2modNh1modN=1000000100100100h0modNh1modNh2modNh3modN h 0 N h -1 N h -2 N h -3 N h 0 N h 3 N h 2 N h 1 N 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 h 0 N h 1 N h 2 N h 3 N (8)
Note: Given circulant ℋ=132213321 ℋ 1 3 2 2 1 3 3 2 1 zeroth column h0c=123 h 0 c 1 2 3 zeroth row ℛh0cT=132T=132 ℛ h 0 c 1 3 2 1 3 2
So circular convolution can be written as this yn= inner product of row n of ℋ (turned into a column) =<x, row n of ℋ tipped into a column > y n inner product of row n of ℋ (turned into a column) x row n of ℋ tipped into a column but row nn of ℋ ℋ tipped into a column vector is
hnrT= C n h0T= C n ℛh0c h n r C n h 0 C n ℛ h 0 c (9)
which is the circular shift of the zeroth row and where h0T=ℛh0c h 0 ℛ h 0 c and is the time reversed column.
& so...
yn=<x, C n ℛh0c> y n x C n ℛ h 0 c (10)
for ℝN N ; put a * in second entry for ℂN N .

The Ring of Doom

modN N operations are natural on a circle! Since they are naturally N N-periodic (Figure 5).
x.png
Subfigure 5.1: 0≤n≤N-1 0 n N 1 .
x2.png
Subfigure 5.2: -∞<n<∞ n .
Figure 5: x=3210T x 3 2 1 0 .
We can put xx on a circle/wheel (Figure 6).
circ1.png
Figure 6: Time runs counter-clockwise.
To do a circular shift by m m, C m x C m x : just spin the wheel counter-clockwise mm units and read off the new signal.
Example 1 
m=2 m 2 , C 2 C 2 (Figure 7).
circ1.png
Subfigure 7.1
circ2.png
Subfigure 7.2
Figure 7: Spin two spots counter-clockwise then C 2 x=x2x3x0x1T C 2 x x 2 x 3 x 0 x 1 .
Time reversal, ℛx ℛ x : just read off wheel in clockwise direction (Figure 8).
Example 2 
circ3.png
Subfigure 8.1
circ4.png
Subfigure 8.2
Figure 8: Read off in time reversed order then ℛx=x0x3x2x1T ℛ x x 0 x 3 x 2 x 1 .

"How to do" Cyclic Convolution

Cyclic convolution works modN N is equivalent to "on the wheel," where the cylinder analogy is powerful.
yn=∑m=0N-1xmhn-mmodN y n m 0 N 1 x m h n m N (11)

Step 1

Plot xm x m (Figure 9).
circ5.png
Figure 9

Step 2

Plot hm h m (backwards on cylinder) (Figure 10).
circ6.png
Figure 10

Step 3

Spin h-m h m nn steps to implement hn-mmodN h n m N anti-clockwise.

Step 4

Multiply pointwise xm x m wheel and hn-mmodN h n m N wheel. The sum equals yn y n .

Step 5

Repeat steps 3 and 4 for all n n.

Comments, questions, feedback, criticisms?

Send feedback