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!
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest.
Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.?
How this robot is carried to required site of body cell.?
what will be the carrier material and how can be detected that correct delivery of drug is done
Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?