# Connexions

You are here: Home » Content » Circular Convolution

### 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.
yn= k =0N1n,kxk y n k 0 N 1 n k x k
(3)
where is a circulant matrix and n,k=h(nk)modN n k h n k N
yn= k =0N1h(nk)modNxk 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.

## 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(k)modN h k h k N
(7)
h0modNh-1modNh-2modNh-3modN=h0modNh3modNh2modNh1modN=( 1000 0001 0010 0100 )h0modNh1modNh2modNh3modN 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 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
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...

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

We can put xx on a circle/wheel (Figure 6).

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

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

## "How to do" Cyclic Convolution

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

yn= m =0N1xmh(nm)modN y n m 0 N 1 x m h n m N
(11)

### Step 1

Plot xm x m (Figure 9).

### Step 2

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

### Step 3

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

### Step 4

Multiply pointwise xm x m wheel and h(nm)modN h n m N wheel. The sum equals yn y n .

### Step 5

Repeat steps 3 and 4 for all n n.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

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?

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