Skip to content Skip to navigation

Connexions

You are here: Home » Content » Circular Convolution

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Circular Convolution

Module by: Richard Baraniuk. E-mail the author

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.
    y⁢n=∑ k =0N−1ℋn,k⁢x⁢k y n k 0 N 1 ℋ n k x k
    (3)
    where ℋ ℋ is a circulant matrix and ℋn,k=h⁢(n−k)modN ℋ n k h n k N
Figure 1: ℋ ℋ is LSI.
Figure 1 (matmult.png)
y⁢n=∑ k =0N−1h⁢(n−k)modN⁢x⁢k y n k 0 N 1 h n k N x k
(4)
y= h ⊛ N x y h ⊛ N x
(5)
y⁢n= 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.

Figure 2
Figure 2 (matmult2.png)
Figure 3
Figure 3 (matmult3.png)

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).

ℛ⁢h⁢k=h⁢(−k)modN ℛ h k h k N
(7)
Figure 4: N=4 N 4 .
(a) hh.
Figure 4(a) (trm1.png)
(b) flip h h.
Figure 4(b) (trm2.png)
(c) flip hmodN flip h N i.e.: to periodize with a period of NN.
Figure 4(c) (trm3.png)
(d) ℛ⁢h ℛ h .
Figure 4(d) (trm4.png)
h⁢0modNh⁢-1modNh⁢-2modNh⁢-3modN=h⁢0modNh⁢3modNh⁢2modNh⁢1modN=( 1000 0001 0010 0100 )⁢h⁢0modNh⁢1modNh⁢2modNh⁢3modN 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 ℋ=( 132 213 321 ) ℋ 1 3 2 2 1 3 3 2 1 zeroth column h 0 c =123 h 0 c 1 2 3 zeroth row (ℛ⁢ h 0 c )T=132T=( 132 ) ℛ h 0 c 1 3 2 1 3 2
So circular convolution can be written as this y⁢n= 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
h n r T= C n ⁢ h 0 T= C n ⁢ℛ⁢ h 0 c h n r C n h 0 C n ℛ h 0 c
(9)
which is the circular shift of the zeroth row and where h 0 T=ℛ⁢ h 0 c h 0 ℛ h 0 c and is the time reversed column.

& so...

y⁢n=〈x, C n ⁢ℛ⁢ h 0 c 〉 y n x C n ℛ h 0 c
(10)
for RN N ; put a * in second entry for CN N .

The Ring of Doom

modN N operations are natural on a circle! Since they are naturally N N-periodic (Figure 5).

Figure 5: x=3210T x 3 2 1 0 .
(a) 0≤n≤N−1 0 n N 1 .
Figure 5(a) (x.png)
(b) −∞<n<∞ n .
Figure 5(b) (x2.png)
We can put xx on a circle/wheel (Figure 6).
Figure 6: Time runs counter-clockwise.
Figure 6 (circ1.png)

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).

Figure 7: Spin two spots counter-clockwise then C 2 ⁢x=x⁢2x⁢3x⁢0x⁢1T C 2 x x 2 x 3 x 0 x 1 .
(a)
Figure 7(a) (circ1.png)
(b)
Figure 7(b) (circ2.png)

Time reversal, ℛ⁢x ℛ x : just read off wheel in clockwise direction (Figure 8).

Example 2

Figure 8: Read off in time reversed order then ℛ⁢x=x⁢0x⁢3x⁢2x⁢1T ℛ x x 0 x 3 x 2 x 1 .
(a)
Figure 8(a) (circ3.png)
(b)
Figure 8(b) (circ4.png)

"How to do" Cyclic Convolution

Cyclic convolution works modN N is equivalent to "on the wheel," where the cylinder analogy is powerful.

y⁢n=∑ m =0N−1x⁢m⁢h⁢(n−m)modN y n m 0 N 1 x m h n m N
(11)

Step 1

Plot x⁢m x m (Figure 9).

Figure 9
Figure 9 (circ5.png)

Step 2

Plot h⁢m h m (backwards on cylinder) (Figure 10).

Figure 10
Figure 10 (circ6.png)

Step 3

Spin h⁢−m h m nn steps to implement h⁢(n−m)modN h n m N anti-clockwise.

Step 4

Multiply pointwise x⁢m x m wheel and h⁢(n−m)modN h n m N wheel. The sum equals y⁢n y n .

Step 5

Repeat steps 3 and 4 for all n n.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks