Site Feedback

# Introduction

This module relates circular convolution of periodic signals in one domain to multiplication in the other domain.

You should be familiar with Discrete-Time Convolution, which tells us that given two discrete-time signals $x⁢n x n$, the system's input, and $h⁢n h n$, the system's response, we define the output of the system as

$y⁢n=x⁢n*h⁢n=∑ k =−∞∞x⁢k⁢h⁢n−k y n x n h n k x k h n k$
1
When we are given two DFTs (finite-length sequences usually of length $NN$), we cannot just multiply them together as we do in the above convolution formula, often referred to as linear convolution. Because the DFTs are periodic, they have nonzero values for $n≥N n N$ and thus the multiplication of these two DFTs will be nonzero for $n≥N n N$. We need to define a new type of convolution operation that will result in our convolved signal being zero outside of the range $n=01…N−1 n 0 1 … N 1$. This idea led to the development of circular convolution, also called cyclic or periodic convolution.

# Signal Circular Convolution

Given a signal $f⁢n f n$ with Fourier coefficients $c k c k$ and a signal $g⁢n g n$ with Fourier coefficients $d k d k$, we can define a new signal, $v⁢n v n$, where $v⁢n=f⁢n⊛g⁢n v n ⊛ f n g n$ We find that the Fourier Series representation of $v⁢n v n$, $a k a k$, is such that $a k = c k ⁢ d k a k c k d k$. $f⁢n⊛g⁢n ⊛ f n g n$ is the circular convolution of two periodic signals and is equivalent to the convolution over one interval, i.e. $f⁢n⊛g⁢n=∑ n =0N∑ η =0Nf⁢η⁢g⁢n−η ⊛ f n g n n 0 N η 0 N f η g n η$.

Note:
Circular convolution in the time domain is equivalent to multiplication of the Fourier coefficients.
This is proved as follows
$a k =1N⁢∑ n =0Nv⁢n⁢e−(j⁢ ω 0 ⁢k⁢n)=1N2⁢∑ n =0N∑ η =0Nf⁢η⁢g⁢n−η⁢e−(ω⁢ j 0 ⁢k⁢n)=1N⁢∑ η =0Nf⁢η⁢(1N⁢∑ n =0Ng⁢n−η⁢e−(j⁢ ω 0 ⁢k⁢n))=∀ ν ,ν=n−η:1N⁢∑ η =0Nf⁢η⁢(1N⁢∑ ν =−ηN−ηg⁢ν⁢e−(j⁢ ω 0 ⁢(ν+η)))=1N⁢∑ η =0Nf⁢η⁢(1N⁢∑ ν =−ηN−ηg⁢ν⁢e−(j⁢ ω 0 ⁢k⁢ν))⁢e−(j⁢ ω 0 ⁢k⁢η)=1N⁢∑ η =0Nf⁢η⁢dk⁢e−(j⁢ ω 0 ⁢k⁢η)= d k ⁢(1N⁢∑ η =0Nf⁢η⁢e−(j⁢ ω 0 ⁢k⁢η))= c k ⁢ d k a k 1 N n 0 N v n j ω 0 k n 1 N 2 n 0 N η 0 N f η g n η ω j 0 k n 1 N η 0 N f η 1 N n 0 N g n η j ω 0 k n ν ν n η 1 N η 0 N f η 1 N ν η N η g ν j ω 0 ν η 1 N η 0 N f η 1 N ν η N η g ν j ω 0 k ν j ω 0 k η 1 N η 0 N f η d k j ω 0 k η d k 1 N η 0 N f η j ω 0 k η c k d k$
2

# Circular Convolution Formula

What happens when we multiply two DFT's together, where $Y⁢k Y k$ is the DFT of $y⁢n y n$?

$Y⁢k=F⁢k⁢H⁢k Y k F k H k$
3
when $0≤k≤N−1 0 k N 1$

Using the DFT synthesis formula for $y⁢n y n$

$y⁢n=1N⁢∑ k =0N−1F⁢k⁢H⁢k⁢ej⁢2⁢πN⁢k⁢n y n 1 N k 0 N 1 F k H k j 2 N k n$
4

And then applying the analysis formula $F⁢k=∑ m =0N−1f⁢m⁢e(−j)⁢2⁢πN⁢k⁢n F k m 0 N 1 f m j 2 N k n$

$y⁢n=1N⁢∑ k =0N−1∑ m =0N−1f⁢m⁢e(−j)⁢2⁢πN⁢k⁢n⁢H⁢k⁢ej⁢2⁢πN⁢k⁢n=∑ m =0N−1f⁢m⁢(1N⁢∑ k =0N−1H⁢k⁢ej⁢2⁢πN⁢k⁢(n−m)) y n 1 N k 0 N 1 m 0 N 1 f m j 2 N k n H k j 2 N k n m 0 N 1 f m 1 N k 0 N 1 H k j 2 N k n m$
5
where we can reduce the second summation found in the above equation into $h⁢ ( ( n − m ) ) N =1N⁢∑ k =0N−1H⁢k⁢ej⁢2⁢πN⁢k⁢(n−m) h ( ( n − m ) ) N 1 N k 0 N 1 H k j 2 N k n m$ $y⁢n=∑ m =0N−1f⁢m⁢h⁢ ( ( n − m ) ) N y n m 0 N 1 f m h ( ( n − m ) ) N$ which equals circular convolution! When we have $0≤n≤N−1 0 n N 1$ in the above, then we get:
$y⁢n≡f⁢n⊛h⁢n y n ⊛ f n h n$
6
Note:
The notation $⊛ ⊛$ represents cyclic convolution "mod N".

# Alternative Convolution Formula

Alternative Circular Convolution Algorithm
• Step 1: Calculate the DFT of $f⁢n f n$ which yields $F⁢k F k$ and calculate the DFT of $h⁢n h n$ which yields $H⁢k H k$.
• Step 2: Pointwise multiply $Y⁢k=F⁢k⁢H⁢k Y k F k H k$
• Step 3: Inverse DFT $Y⁢k Y k$ which yields $y⁢n y n$

Seems like a roundabout way of doing things, but it turns out that there are extremely fast ways to calculate the DFT of a sequence.

To circularily convolve $2 2$ $N N$-point sequences: $y⁢n=∑ m =0N−1f⁢m⁢h⁢ ( ( n − m ) ) N y n m 0 N 1 f m h ( ( n − m ) ) N$ For each $n n$ : $N N$ multiples, $N−1 N 1$ additions

$N N$ points implies $N2 N 2$ multiplications, $N⁢(N−1) N N 1$ additions implies $O⁢N2 O N 2$ complexity.

# Steps for Circular Convolution

We can picture periodic sequences as having discrete points on a circle as the domain

Shifting by $mm$, $f⁢n+m f n m$, corresponds to rotating the cylinder $mm$ notches ACW (counter clockwise). For $m=-2 m -2$, we get a shift equal to that in the following illustration:

To cyclic shift we follow these steps:

1) Write $f⁢n f n$ on a cylinder, ACW

2) To cyclic shift by $mm$, spin cylinder m spots ACW $f⁢n→f⁢ (( n + m )) N → f n f (( n + m )) N$

# Notes on circular shifting

$f⁢ (( n + N )) N =f⁢n f (( n + N )) N f n$ Spinning $NN$ spots is the same as spinning all the way around, or not spinning at all.

$f⁢ (( n + N )) N =f⁢ (( n - ( N - m ) )) N f (( n + N )) N f (( n - ( N - m ) )) N$ Shifting ACW $mm$ is equivalent to shifting CW $N−m N m$

$f⁢ (( - n )) N f (( - n )) N$ The above expression, simply writes the values of $f⁢n f n$ clockwise.

Example 1: Convolve (n = 4)

• $h⁢ ((−(m()() N h ( ( − m ) ) N$

Multiply $f⁢m f m$ and $sum sum$ to yield: $y⁢0=3 y 0 3$

• $h⁢ ((1(−(m()() N h ( ( 1 − m ) ) N$

Multiply $f⁢m f m$ and $sum sum$ to yield: $y⁢1=5 y 1 5$

• $h⁢ ((2(−(m()() N h ( ( 2 − m ) ) N$

Multiply $f⁢m f m$ and $sum sum$ to yield: $y⁢2=3 y 2 3$

• $h⁢ ((3(−(m()() N h ( ( 3 − m ) ) N$

Multiply $f⁢m f m$ and $sum sum$ to yield: $y⁢3=1 y 3 1$

# Exercise

Take a look at a square pulse with a period of T.

For this signal

Take a look at a triangle pulse train with a period of T.

This signal is created by circularly convolving the square pulse with itself. The Fourier coefficients for this signal are $a k = c k 2=14⁢sin2π2⁢kπ2⁢k2 a k c k 2 1 4 2 k 2 2 k 2$

Exercise 1

Find the Fourier coefficients of the signal that is created when the square pulse and the triangle pulse are convolved.

Solution

$a k = undefined k = 0 1 8 s i n 3 [ π 2 k ] [ π 2 k ] 3 otherwise a k = undefined k = 0 1 8 s i n 3 [ π 2 k ] [ π 2 k ] 3 otherwise$

# Circular Shifts and the DFT

Theorem 1: Circular Shifts and DFT

If $f⁢n ↔ DFT F⁢k f n ↔ DFT F k$ then $f⁢ (( n - m )) N ↔ DFT e−(i⁢2⁢πN⁢k⁢m)⁢F⁢k f (( n - m )) N ↔ DFT 2 N k m F k$ (i.e. circular shift in time domain = phase shift in DFT)

Proof

$f⁢n=1N⁢∑k=0N−1F⁢k⁢ei⁢2⁢πN⁢k⁢n f n 1 N k 0 N 1 F k 2 N k n$
7
so phase shifting the DFT
$f⁢n=1N⁢∑k=0N−1F⁢k⁢e−(i⁢2⁢πN⁢k⁢n)⁢ei⁢2⁢πN⁢k⁢n=1N⁢∑k=0N−1F⁢k⁢ei⁢2⁢πN⁢k⁢(n−m)=f⁢ (( n - m )) N f n 1 N k 0 N 1 F k 2 N k n 2 N k n 1 N k 0 N 1 F k 2 N k n m f (( n - m )) N$
8

# Conclusion

Circular convolution in the time domain is equivalent to multiplication of the Fourier coefficients in the frequency domain.