This module describes FFT, convolution, filtering, LTI systems,
digital filters and circular convolution.
Important application of the fft
How many complex multiplies and adds are required to
convolve two
$N$ -pt
sequences?
$$y(n)=\sum_{m=0}^{N-1} x(m)h(n-m)$$
There are
$2N-1$ non-zero output points and each will be computed
using
$N$ complex mults and
$N-1$ complex adds. Therefore,
$$\text{Total Cost}=(2N-1)(N+N-1)\approx O(N^{2})$$
Zero-pad these two sequences to length
$2N-1$ , take DFTs using the FFT algorithm
$$x(n)\to X(k)$$$$h(n)\to H(k)$$ The cost is
$$O((2N-1)\lg (2N-1))=O(N\lg N)$$
Multiply DFTs
$$X(k)H(k)$$ The cost is
$$O(2N-1)=O(N)$$
Inverse DFT using FFT
$$X(k)H(k)\to y(n)$$ The cost is
$$O((2N-1)\lg (2N-1))=O(N\lg N)$$
So the total cost for direct convolution of two
$N$ -point sequences is
$O(N^{2})$ . Total cost for convolution using FFT algorithm is
$O(N\lg N)$ . That is a
huge savings (
).
Summary of dft
$x(n)$ is an
$N$ -point signal
(
).
$$X(k)=\sum_{n=0}^{N-1} x(n)e^{-(i\frac{2\pi}{N}kn)}=\sum_{n=0}^{N-1} x(n){W}_{N}^{(kn)}$$ where
${W}_{N}=e^{-(i\frac{2\pi}{N})}$ is a "twiddle factor" and the first part is the basic DFT.
What is the dft
$$X(k)=X(F=\frac{k}{N})=\sum_{n=0}^{N-1} x(n)e^{-(i\times 2\pi Fn)}$$ where
$X(F=\frac{k}{N})$ is the DTFT of
$x(n)$ and
$\sum_{n=0}^{N-1} x(n)e^{-(i\times 2\pi Fn)}$ is the DTFT of
$x(n)$ at digital frequency
$F$ . This is a sample of the
DTFT. We can do frequency domain analysis on a computer!
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?
In this morden time nanotechnology used in many field .
1-Electronics-manufacturad IC ,RAM,MRAM,solar panel etc
2-Helth and Medical-Nanomedicine,Drug Dilivery for cancer treatment etc
3- Atomobile -MEMS, Coating on car etc.
and may other field for details you can check at Google
Azam
anybody can imagine what will be happen after 100 years from now in nano tech world
Prasenjit
after 100 year this will be not nanotechnology maybe this technology name will be change .
maybe aftet 100 year . we work on electron lable practically about its properties and behaviour by the different instruments
Azam
name doesn't matter , whatever it will be change... I'm taking about effect on circumstances of the microscopic world
Prasenjit
how hard could it be to apply nanotechnology against viral infections such HIV or Ebola?
Damian
silver nanoparticles could handle the job?
Damian
not now but maybe in future only AgNP maybe any other nanomaterials
Azam
Hello
Uday
I'm interested in Nanotube
Uday
this technology will not going on for the long time , so I'm thinking about femtotechnology 10^-15
Prasenjit
can nanotechnology change the direction of the face of the world