This module describes the circular convolution algorithm and an alternative algorithm

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)$ , the system's input, and
$h(n)$ , the system's response, we define the output of the
system as

$y(n)=(x(n), h(n))=\sum_{k=()} $∞∞xkhnk

When we are given two DFTs (finite-length sequences usually oflength
$N$ ), we cannot just
multiply them together as we do in the above convolutionformula, often referred to as
linear convolution .
Because the DFTs are periodic, they have nonzero values for
$n\ge N$ and thus the multiplication of these two DFTs will
be nonzero for
$n\ge N$ . We need to define a new type of convolution
operation that will result in our convolved signal being zerooutside of the range
$n=\{0, 1, \dots , 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)$ with Fourier coefficients
${c}_{k}$ and a signal
$g(n)$ with Fourier coefficients
${d}_{k}$ ,
we can define a new signal,
$v(n)$ ,
where
$v(n)=\u229b(f(n), g(n))$ We find that the
Fourier
Series representation of
$v(n)$ ,
${a}_{k}$ ,
is such that
${a}_{k}={c}_{k}{d}_{k}$ .
$\u229b(f(n), g(n))$ is the
circular convolution of two periodic signals and is equivalent to the convolution
over one interval,
i.e.$\u229b(f(n), g(n))=\sum_{n=0}^{N} \sum_{\eta =0}^{N} f(\eta )g(n-\eta )$ .

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

where we can reduce the second summation found in the above
equation into
$h({\left(\right(n-m\left)\right)()}_{N})=\frac{1}{N}\sum_{k=0}^{N-1} H(k)e^{(j\frac{2\pi}{N}k(n-m))}$$y(n)=\sum_{m=0}^{N-1} f(m)h({\left(\right(n-m\left)\right)()}_{N})$ which equals circular convolution! When we have
$0\le n\le N-1$ in the above, then we get:

$y(n)\equiv \u229b(f(n), h(n))$

The notation
$\u229b$ represents cyclic convolution "mod N".

Alternative convolution formula

Alternative circular convolution algorithm

Step 1: Calculate the DFT of
$f(n)$ which yields
$F(k)$ and calculate the DFT of
$h(n)$ which yields
$H(k)$ .

Step 2: Pointwise multiply
$Y(k)=F(k)H(k)$

Step 3: Inverse DFT
$Y(k)$ which yields
$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$$N$ -point sequences:
$y(n)=\sum_{m=0}^{N-1} f(m)h({\left(\right(n-m\left)\right)()}_{N})$ For each
$n$ :
$N$ multiples,
$N-1$ additions

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

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

To cyclic shift we follow these steps:

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

2) To cyclic shift by
$m$ , spin
cylinder m spots ACW
$$\to (f(n), f({((n+m))}_{N}))$$

Notes on circular shifting

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

$f({((n+N))}_{N})=f({((n-(N-m)))}_{N})$ Shifting ACW
$m$ is equivalent to
shifting CW
$N-m$

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

Convolve (n = 4)

$h({\left((\right(, -, m, \left), \right))}_{N})$

Multiply
$f(m)$ and
$\mathrm{sum}$ to yield:
$y(0)=3$

$h({\left((\right(, 1, -, m, \left), \right))}_{N})$

Multiply
$f(m)$ and
$\mathrm{sum}$ to yield:
$y(1)=5$

$h({\left((\right(, 2, -, m, \left), \right))}_{N})$

Multiply
$f(m)$ and
$\mathrm{sum}$ to yield:
$y(2)=3$

$h({\left((\right(, 3, -, m, \left), \right))}_{N})$

Multiply
$f(m)$ and
$\mathrm{sum}$ to yield:
$y(3)=1$

For this signal
${c}_{k}=\begin{cases}\frac{1}{N} & \text{if $k=0$}\\ \frac{1}{2}\frac{\sin (\frac{\pi}{2}k)}{\frac{\pi}{2}k} & \text{otherwise}\end{cases}$

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}=\frac{1}{4}\frac{\sin (\frac{\pi}{2}k)^{2}}{(\frac{\pi}{2}k)^{2}}$

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

If
$f(n)\stackrel{\text{DFT}}{\leftrightarrow}F(k)$ then
$f({((n-m))}_{N})\stackrel{\text{DFT}}{\leftrightarrow}e^{-(i\frac{2\pi}{N}km)}F(k)$ (
i.e. circular shift in time domain =
phase shift in DFT)

fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.

Tarell

what is the actual application of fullerenes nowadays?

Damian

That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.

Tarell

what is the Synthesis, properties,and applications of carbon nano chemistry

Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.

Harper

Do you know which machine is used to that process?