DTS 01discrete-fourier-transform (1).pdf
vikalankit84710
10 views
91 slides
Mar 09, 2025
Slide 1 of 91
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
About This Presentation
digitaal foruirier tranform
Slide Content
UNIT - 1: Discrete Fourier Transforms
(DFT)[1, 2, 3, 4, 5]
Dr. Manjunatha. P
[email protected]
Professor
Dept. of ECE
J.N.N. College of Engineering, Shimoga
September 11, 2014
(DFT)[1, 2, 3, 4, 5]
Dr. Manjunatha. P
[email protected]
Professor
Dept. of ECE
J.N.N. College of Engineering, Shimoga
September 11, 2014
DSP SyllabusIntroduction
Digital Signal Processing: Introduction
Slides are prepared to use in class room purpose, may be used as a
reference material
All the slides are prepared based on the reference material
Most of the gures/content used in this material are redrawn, some
of the gures/pictures are downloaded from the Internet.
I will greatly acknowledge for copying the some the images from the
Internet.
This material is not for
This material is prepared based on
ECE/TCE
syllabus (Karnataka State, India).
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 2 / 91
Digital Signal Processing: Introduction
Slides are prepared to use in class room purpose, may be used as a
reference material
All the slides are prepared based on the reference material
Most of the gures/content used in this material are redrawn, some
of the gures/pictures are downloaded from the Internet.
I will greatly acknowledge for copying the some the images from the
Internet.
This material is not for
This material is prepared based on
ECE/TCE
syllabus (Karnataka State, India).
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 2 / 91
DSP Syllabus
DSP Syllabus
PART - A
UNIT - 1:
Frequency domain sampling and reconstruction of discrete time signals.
DFT as a linear transformation, its relationship with other transforms.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 3 / 91
DSP Syllabus
PART - A
UNIT - 1:
Frequency domain sampling and reconstruction of discrete time signals.
DFT as a linear transformation, its relationship with other transforms.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 3 / 91
IntroductionThe concept of frequency in continuous and discrete time signals
The concept of frequency in continuous and discrete time signals
Continuous Time Sinusoidal Signals
The concept of frequency is closely related to specic type of motion called harmonic
oscillation which is directly related to the concept of time.
A simple harmonic oscillation is mathematically described by:
xa(t) =Acos(t+); 1<t<1
The subscript a is used withx(t) to denote an analog signal. A is the amplitude, is the
frequency in radians per second(rad/s), andis the phase in radians. The is related by
frequency F in cycles per second or hertz by
= 2F
xa(t) =Acos(2Ft+); 1<t<1
Figure 1: Example of an analog sinusoidal signal
Cycle and Period
The completion of one full pattern waveform is called a cycle. A period is dened as the
amount of time required to complete one full cycle.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 4 / 91
The concept of frequency in continuous and discrete time signals
Continuous Time Sinusoidal Signals
The concept of frequency is closely related to specic type of motion called harmonic
oscillation which is directly related to the concept of time.
A simple harmonic oscillation is mathematically described by:
xa(t) =Acos(t+); 1<t<1
The subscript a is used withx(t) to denote an analog signal. A is the amplitude, is the
frequency in radians per second(rad/s), andis the phase in radians. The is related by
frequency F in cycles per second or hertz by
= 2F
xa(t) =Acos(2Ft+); 1<t<1
Figure 1: Example of an analog sinusoidal signal
Cycle and Period
The completion of one full pattern waveform is called a cycle. A period is dened as the
amount of time required to complete one full cycle.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 4 / 91
IntroductionThe concept of frequency in continuous and discrete time signals
Complex exponential signals
xa(t) =Ae
j(t+)
where
e
j
=cosjsin
xa(t) =Acos(t+) =
A
2
e
j(t+)
+
A
2
e
j(t+)
As time progress the phasors rotate in opposite directions with angular frequencies
radians per second.
A positive frequency corresponds to counterclockwise uniform angular motion, a negative
frequency corresponds to clockwise angular motion.
Figure 2: Representation of cosine function by phasor
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 5 / 91
Complex exponential signals
xa(t) =Ae
j(t+)
where
e
j
=cosjsin
xa(t) =Acos(t+) =
A
2
e
j(t+)
+
A
2
e
j(t+)
As time progress the phasors rotate in opposite directions with angular frequencies
radians per second.
A positive frequency corresponds to counterclockwise uniform angular motion, a negative
frequency corresponds to clockwise angular motion.
Figure 2: Representation of cosine function by phasor
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 5 / 91
IntroductionDiscrete Time Sinusoidal Signals
Discrete Time Sinusoidal Signals
A discrete time sinusoidal may expressed as
x(n) =Acos(!n+); 1<t<1
where n is an integer variable called the sample number.
A is the amplitude,!is the frequency in radians per sample(rad/s), andis the phase in
radians.
The!is related by frequency f cycles per sample by
!= 2f
x(n) =Acos(2fn+); 1<t<1
A discrete time signalx(n) is periodic with periodN(N>0) if and only if
x(n+N) =x(n)for all n
Figure 3: Discrete signal
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 6 / 91
Discrete Time Sinusoidal Signals
A discrete time sinusoidal may expressed as
x(n) =Acos(!n+); 1<t<1
where n is an integer variable called the sample number.
A is the amplitude,!is the frequency in radians per sample(rad/s), andis the phase in
radians.
The!is related by frequency f cycles per sample by
!= 2f
x(n) =Acos(2fn+); 1<t<1
A discrete time signalx(n) is periodic with periodN(N>0) if and only if
x(n+N) =x(n)for all n
Figure 3: Discrete signal
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 6 / 91
IntroductionDiscrete Time Sinusoidal Signals
Periodic and aperiodic (non-periodic) signals.
A periodic signal consists a continuously repeated pattern. Signal is periodic if it exhibits
periodicity i.e.
x(t+T) = x(t)for all t
It has a property that it is unchanged by a time shift of T.
An
over the time.
Figure 4:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 7 / 91
Periodic and aperiodic (non-periodic) signals.
A periodic signal consists a continuously repeated pattern. Signal is periodic if it exhibits
periodicity i.e.
x(t+T) = x(t)for all t
It has a property that it is unchanged by a time shift of T.
An
over the time.
Figure 4:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 7 / 91
IntroductionDiscrete Time Sinusoidal Signals
Periodic and aperiodic (non-periodic) signals.
Figure 5:Figure 6:Figure 7:Figure 8:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 8 / 91
Periodic and aperiodic (non-periodic) signals.
Figure 5:Figure 6:Figure 7:Figure 8:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 8 / 91
IntroductionDiscrete Time Sinusoidal Signals
Periodic and aperiodic (non-periodic) signals.
Figure 9:Figure 10:
signals
Figure 11:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 9 / 91
Periodic and aperiodic (non-periodic) signals.
Figure 9:Figure 10:
signals
Figure 11:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 9 / 91
IntroductionDiscrete Time Sinusoidal Signals
Periodic and aperiodic (non-periodic) signals.
Figure 12:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 10 / 91
Periodic and aperiodic (non-periodic) signals.
Figure 12:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 10 / 91
Fourier series
Fourier series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 11 / 91
Fourier series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 11 / 91
Fourier seriesFourier series
Sinusoidal functions are wide applications in Engineering and they are easy to generate.
Fourier has shown that periodic signals can be represented by series of sinusoids with
dierent frequency.
A signalf(t) is said to be periodic of periodTiff(t) =f(t+T) for all t.
Periodic signals can be represented by the Fourier series and non periodic signals can be
represented by the Fourier transform.
For example square wave pattern can be approximated with a suitable sum of a
fundamental sine wave plus a combination of harmonics of this fundamental frequency.
Several waveforms that are represented by sinusoids are as shown in Figure 14. This sum
is called a Fourier series.
The major dierence with respect to the line spectra of periodic signals is that the spectra
of aperiodic signals are dened for all real values of the frequency variable!.
Figure 13: Square Wave from
Fourier Series
Figure 14: Waveforms from Fourier Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 12 / 91
Sinusoidal functions are wide applications in Engineering and they are easy to generate.
Fourier has shown that periodic signals can be represented by series of sinusoids with
dierent frequency.
A signalf(t) is said to be periodic of periodTiff(t) =f(t+T) for all t.
Periodic signals can be represented by the Fourier series and non periodic signals can be
represented by the Fourier transform.
For example square wave pattern can be approximated with a suitable sum of a
fundamental sine wave plus a combination of harmonics of this fundamental frequency.
Several waveforms that are represented by sinusoids are as shown in Figure 14. This sum
is called a Fourier series.
The major dierence with respect to the line spectra of periodic signals is that the spectra
of aperiodic signals are dened for all real values of the frequency variable!.
Figure 13: Square Wave from
Fourier Series
Figure 14: Waveforms from Fourier Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 12 / 91
Fourier seriesFourier series
Fourier analysis:
and cosine functions with dierent frequencies, phases, and amplitudes.
The functions are integral harmonics of the fundamental frequencyfof the composite
signal.
Using the series we can decompose any periodic signal into its harmonics.
f() = a0+
1
X
n=1
ancos(n) +
1
X
n=1
bnsin(n)
where
a0=
1
2
2Z
0
f()d
an=
1
2Z
0
f()cos(n)d
bn=
1
2Z
0
f()sin(n)d
Line spectra, harmonics
The fundamental frequencyf0= 1=T. The Fourier series coecients plotted as a function
ofnornf0is called a Fourier spectrum.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 13 / 91
Fourier analysis:
and cosine functions with dierent frequencies, phases, and amplitudes.
The functions are integral harmonics of the fundamental frequencyfof the composite
signal.
Using the series we can decompose any periodic signal into its harmonics.
f() = a0+
1
X
n=1
ancos(n) +
1
X
n=1
bnsin(n)
where
a0=
1
2
2Z
0
f()d
an=
1
2Z
0
f()cos(n)d
bn=
1
2Z
0
f()sin(n)d
Line spectra, harmonics
The fundamental frequencyf0= 1=T. The Fourier series coecients plotted as a function
ofnornf0is called a Fourier spectrum.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 13 / 91
Fourier seriesFourier series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 14 / 91
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 14 / 91
Fourier seriesFourier series
Figure 15: Square Wave
f() =
A when 0< <
A when < <2
f(+ 2) =f()
a0=
1
2
Z
2
0
f()d
=
1
2
Z
0
f()d+
Z
2
f()d
=
1
2
Z
0
Ad+
Z
2
(A)d
= 0
an=
1
Z
2
0
f() cosnd
=
1
Z
0
Acosnd+
Z
2
(A) cosnd
=
1
A
sinn
n
0
+
1
A
sinn
n
2
= 0
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 15 / 91
Figure 15: Square Wave
f() =
A when 0< <
A when < <2
f(+ 2) =f()
a0=
1
2
Z
2
0
f()d
=
1
2
Z
0
f()d+
Z
2
f()d
=
1
2
Z
0
Ad+
Z
2
(A)d
= 0
an=
1
Z
2
0
f() cosnd
=
1
Z
0
Acosnd+
Z
2
(A) cosnd
=
1
A
sinn
n
0
+
1
A
sinn
n
2
= 0
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 15 / 91
Fourier seriesFourier series
bn=
1
Z
2
0
f() sinnd
=
1
Z
0
Asinnd+
Z
2
(A) sinnd
=
1
A
cosn
n
0
+
1
A
cosn
n
2
=
A
n
[cosn+ cos 0 + cos 2ncosn]
=
A
n
[1 + 1 + 1 + 1]
=
4A
n
when n is odd
bn=
A
n
[cosn+ cos 0 + cos 2ncosn]
=
A
n
[1 + 1 + 11]
= 0 when n is even
4A
sin+
1
3
sin 3+
1
5
sin 5+
1
7
sin 7+
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 16 / 91
bn=
1
Z
2
0
f() sinnd
=
1
Z
0
Asinnd+
Z
2
(A) sinnd
=
1
A
cosn
n
0
+
1
A
cosn
n
2
=
A
n
[cosn+ cos 0 + cos 2ncosn]
=
A
n
[1 + 1 + 1 + 1]
=
4A
n
when n is odd
bn=
A
n
[cosn+ cos 0 + cos 2ncosn]
=
A
n
[1 + 1 + 11]
= 0 when n is even
4A
sin+
1
3
sin 3+
1
5
sin 5+
1
7
sin 7+
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 16 / 91
Fourier seriesFourier series
4A
sin+
1
3
sin 3+
1
5
sin 5+
1
7
sin 7+
Figure 16: Square Wave from Fourier
Series
Figure 17: Square Wave from Fourier
Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 17 / 91
4A
sin+
1
3
sin 3+
1
5
sin 5+
1
7
sin 7+
Figure 16: Square Wave from Fourier
Series
Figure 17: Square Wave from Fourier
Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 17 / 91
Fourier seriesFourier series
clc;clear all; close all;
f=100;%Fundamental frequency 100 Hz
t=0:.00001:.05;
xsin = sin(2*pi*f*t);
x1 = sin(2*pi*f*t);
x3 = (1/3)*sin(3*2*pi*f*t);
x5 = (1/5)*sin(5*2*pi*f*t);
x7 = (1/7)*sin(7*2*pi*f*t);
x=x1+x3+x5+x7;
subplot(2,1,1)
plot(t,xsin,'linewidth',2);
xlabel(' heta','fontsize',16)
ylabel('sin(\theta)','fontsize',16)
title('Fundamental sinusoidal signal')
subplot(2,1,2)
plot(t,x,'linewidth',2);
xlabel(' heta','fontsize',16)
ylabel('f ( heta)','fontsize',16)
title('Reconstructed square wave by Fourier ')00.0050.010.0150.020.0250.030.0350.040.0450.05
-1
-0.5
0
0.5
1
θ
sin(θ)
Fundamental sinusoidal signal
00.0050.010.0150.020.0250.030.0350.040.0450.05
-1
-0.5
0
0.5
1
θ
f (θ)
Reconstructed square wave by Fourier
Figure 18: Square Wave
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 18 / 91
clc;clear all; close all;
f=100;%Fundamental frequency 100 Hz
t=0:.00001:.05;
xsin = sin(2*pi*f*t);
x1 = sin(2*pi*f*t);
x3 = (1/3)*sin(3*2*pi*f*t);
x5 = (1/5)*sin(5*2*pi*f*t);
x7 = (1/7)*sin(7*2*pi*f*t);
x=x1+x3+x5+x7;
subplot(2,1,1)
plot(t,xsin,'linewidth',2);
xlabel(' heta','fontsize',16)
ylabel('sin(\theta)','fontsize',16)
title('Fundamental sinusoidal signal')
subplot(2,1,2)
plot(t,x,'linewidth',2);
xlabel(' heta','fontsize',16)
ylabel('f ( heta)','fontsize',16)
title('Reconstructed square wave by Fourier ')00.0050.010.0150.020.0250.030.0350.040.0450.05
-1
-0.5
0
0.5
1
θ
sin(θ)
Fundamental sinusoidal signal
00.0050.010.0150.020.0250.030.0350.040.0450.05
-1
-0.5
0
0.5
1
θ
f (θ)
Reconstructed square wave by Fourier
Figure 18: Square Wave
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 18 / 91
Fourier seriesFourier series
Figure 19: Triangular Wave
bn=
2
T
Z
T
0
f(t) sin
2n
T
t
dt
=
4
T
Z
T=2
0
f(t) sin
2n
T
t
dt
=
4
T
Z
T=4
0
tsin
2n
T
t
dt+
4
T
Z
T=4
0
t+
T
2
sin
2n
T
t
dt
=
4
T
"
2
T
2n
2
sin
n
2
#
=
2T
2
2
n
2
sin
n
2
= 0when n is even
2T
2
sin
2
T
t
1
3
2
sin
6
T
t
+
1
5
2
sin
10
T
t
f(t) =
t when
T
4
t
T
4
t+
T
2
when
T
4
t
3T
4
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 19 / 91
Figure 19: Triangular Wave
bn=
2
T
Z
T
0
f(t) sin
2n
T
t
dt
=
4
T
Z
T=2
0
f(t) sin
2n
T
t
dt
=
4
T
Z
T=4
0
tsin
2n
T
t
dt+
4
T
Z
T=4
0
t+
T
2
sin
2n
T
t
dt
=
4
T
"
2
T
2n
2
sin
n
2
#
=
2T
2
2
n
2
sin
n
2
= 0when n is even
2T
2
sin
2
T
t
1
3
2
sin
6
T
t
+
1
5
2
sin
10
T
t
f(t) =
t when
T
4
t
T
4
t+
T
2
when
T
4
t
3T
4
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 19 / 91
Fourier seriesFourier series
Figure 20: Figure 21:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 20 / 91
Figure 20: Figure 21:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 20 / 91
Fourier seriesFourier series
The Exponential (Complex) Form of Fourier Series
f() =a0+
1
X
n=1
ancosn+
1
X
n=1
bnsinn
cos=
e
j
+e
j
2
sin=
e
j
e
j
2j
ancosn+bnsinn=
=an
e
jn
+e
jn
2
+bn
e
jn
e
jn
2j
=an
e
jn
+e
jn
2
jbn
e
jn
e
jn
2
=
anjbn
2
e
jn
+
an+jbn
2
e
jn
let cn=
anjbn
2
cn=
an+jbn
2
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 21 / 91
The Exponential (Complex) Form of Fourier Series
f() =a0+
1
X
n=1
ancosn+
1
X
n=1
bnsinn
cos=
e
j
+e
j
2
sin=
e
j
e
j
2j
ancosn+bnsinn=
=an
e
jn
+e
jn
2
+bn
e
jn
e
jn
2j
=an
e
jn
+e
jn
2
jbn
e
jn
e
jn
2
=
anjbn
2
e
jn
+
an+jbn
2
e
jn
let cn=
anjbn
2
cn=
an+jbn
2
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 21 / 91
Fourier seriesFourier series
ancosn+bnsinn=cne
jn
+cne
jn
f() = c0+
1
X
n=1
cne
jn
+cne
jn
=
1
X
n=1
cne
jn
where
cn=
anjbn
2
The coecientcncan be evaluated as.
cn=
1
2
Z
f() cosnd
j
2
Z
f() sinnd
=
1
2
Z
f() (cosnjsinn)d
=
1
2
Z
f()e
jn
d
In exponential Fourier series only one
integral has to be calculated and it is
simpler integration.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 22 / 91
ancosn+bnsinn=cne
jn
+cne
jn
f() = c0+
1
X
n=1
cne
jn
+cne
jn
=
1
X
n=1
cne
jn
where
cn=
anjbn
2
The coecientcncan be evaluated as.
cn=
1
2
Z
f() cosnd
j
2
Z
f() sinnd
=
1
2
Z
f() (cosnjsinn)d
=
1
2
Z
f()e
jn
d
In exponential Fourier series only one
integral has to be calculated and it is
simpler integration.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 22 / 91
Fourier seriesFourier series
Figure 22:
Figure 23:
>> N=256; % number of samples
>> T=1/128; % sampling frequency=128Hz
>> k=0:N-1; time=k*T;
>> f=0.25+2*sin(2*pi*5*k*T)+1*sin(2*pi*12.5*k*T)+…
+1.5*sin(2*pi*20*k*T)+0.5*sin(2*pi*35*k*T);
>> plot(time,f); title('Signal sampled at 128Hz');
>> F=fft(f);
>> magF=abs([F(1)/N,F(2:N/2)/(N/2)]);
>> hertz=k(1:N/2)*(1/(N*T));
>> stem(hertz,magF), title('Frequency components');
Example
Find the spectrum of the following signal:
f=0.25+2sin(2π5k)+sin(2π12.5k)+1.5sin(2π20k)+0.5sin(2π35k)
Figure 24:
Find th
e
1000 Hz
with ran
e frequency
z. Form a s
dom noise.
y componen
ignal consis
nts of a sig
sting of 50
gnal buried
Hz and 120
d in noise.
0 Hz sinuso
Consider d
oids and co
data sample
orrupt the s
ed at
signal Figure 25:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 23 / 91
Figure 22:
Figure 23:
>> N=256; % number of samples
>> T=1/128; % sampling frequency=128Hz
>> k=0:N-1; time=k*T;
>> f=0.25+2*sin(2*pi*5*k*T)+1*sin(2*pi*12.5*k*T)+…
+1.5*sin(2*pi*20*k*T)+0.5*sin(2*pi*35*k*T);
>> plot(time,f); title('Signal sampled at 128Hz');
>> F=fft(f);
>> magF=abs([F(1)/N,F(2:N/2)/(N/2)]);
>> hertz=k(1:N/2)*(1/(N*T));
>> stem(hertz,magF), title('Frequency components');
Example
Find the spectrum of the following signal:
f=0.25+2sin(2π5k)+sin(2π12.5k)+1.5sin(2π20k)+0.5sin(2π35k)
Figure 24:
Find th
e
1000 Hz
with ran
e frequency
z. Form a s
dom noise.
y componen
ignal consis
nts of a sig
sting of 50
gnal buried
Hz and 120
d in noise.
0 Hz sinuso
Consider d
oids and co
data sample
orrupt the s
ed at
signal Figure 25:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 23 / 91
Fourier seriesFourier series
-5
-4
-3
-2
-1
0
1
2
3
4
5
0
200 4400 600
0 80010001200 14400
Figure 26: Figure 27:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 24 / 91
-5
-4
-3
-2
-1
0
1
2
3
4
5
0
200 4400 600
0 80010001200 14400
Figure 26: Figure 27:
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 24 / 91
Fourier Transform
Fourier Transform
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 25 / 91
Fourier Transform
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 25 / 91
Fourier TransformFourier Transform
The Fourier transform is a generalization of the Fourier series representation of functions.
The Fourier series is limited to periodic functions, while the Fourier transform can be used
for a larger class of functions which are not necessarily periodic. S
Sinusoidal functions are wide applications in Engineering and they are easy to generate.
Fourier has shown that periodic signals can be represented by series of sinusoids with
dierent frequency.
A signalf(t) is said to be periodic of periodTiff(t) =f(t+T) for all t.
Periodic signals can be represented by the Fourier series and non periodic signals can be
represented by the Fourier transform.
For example square wave pattern can be approximated with a suitable sum of a
fundamental sine wave plus a combination of harmonics of this fundamental frequency.
Several waveforms that are represented by sinusoids are as shown in Figure 14. This sum
is called a Fourier series.
The major dierence with respect to the line spectra of periodic signals is that the spectra
of aperiodic signals are dened for all real values of the frequency variable!.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 26 / 91
The Fourier transform is a generalization of the Fourier series representation of functions.
The Fourier series is limited to periodic functions, while the Fourier transform can be used
for a larger class of functions which are not necessarily periodic. S
Sinusoidal functions are wide applications in Engineering and they are easy to generate.
Fourier has shown that periodic signals can be represented by series of sinusoids with
dierent frequency.
A signalf(t) is said to be periodic of periodTiff(t) =f(t+T) for all t.
Periodic signals can be represented by the Fourier series and non periodic signals can be
represented by the Fourier transform.
For example square wave pattern can be approximated with a suitable sum of a
fundamental sine wave plus a combination of harmonics of this fundamental frequency.
Several waveforms that are represented by sinusoids are as shown in Figure 14. This sum
is called a Fourier series.
The major dierence with respect to the line spectra of periodic signals is that the spectra
of aperiodic signals are dened for all real values of the frequency variable!.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 26 / 91
Fourier TransformFourier Transform
f() =
1
X
n=1
cne
jn
where
cn=
1
2
Z
f()e
jn
d
=!t
!is the angular velocity in radians per
second.
!= 2f and= 2ft
=
2
T
t and d=
2
T
dt
when=
=
2t
T
)t=
T
2
when=
=
2t
T
)t=
T
2
f(t) =
1
X
n=1
cne
jn!t
cn=
1
T
Z
T=2
T=2
f(t)e
jn!t
dt
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 27 / 91
f() =
1
X
n=1
cne
jn
where
cn=
1
2
Z
f()e
jn
d
=!t
!is the angular velocity in radians per
second.
!= 2f and= 2ft
=
2
T
t and d=
2
T
dt
when=
=
2t
T
)t=
T
2
when=
=
2t
T
)t=
T
2
f(t) =
1
X
n=1
cne
jn!t
cn=
1
T
Z
T=2
T=2
f(t)e
jn!t
dt
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 27 / 91
Fourier TransformFourier Transform
Relationship from Fourier series to Fourier Transform
f(t) =
1
X
n=1
cne
jn!t
cn=
1
T
Z
T=2
T=2
f(t)e
jn!t
dt
As T approaches innity
!approaches zero
and n becomes meaningless
n!)! !)!
T)
2
!
f(t) =
!
X
n=!
c!e
j!t
c!=
!
2
Z
T=2
T=2
f(t)e
j!t
dt
f(t) =
1
2
2
4
1
X
!=1
Z
T=2
T=2
f(t)e
j!t
dt
3
5e
j!t
!
T) 1!)d!and
P
)
R
f(t) =
1
2
Z
1
1
Z
1
1
f(t)e
(j!t)
dt
e
(j!t)
d!
f(t) =
1
2
Z
1
1
F(!)e
(j!t)
d!
F(!) =
Z
1
1
f(t)e
(j!t)
dt
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 28 / 91
Relationship from Fourier series to Fourier Transform
f(t) =
1
X
n=1
cne
jn!t
cn=
1
T
Z
T=2
T=2
f(t)e
jn!t
dt
As T approaches innity
!approaches zero
and n becomes meaningless
n!)! !)!
T)
2
!
f(t) =
!
X
n=!
c!e
j!t
c!=
!
2
Z
T=2
T=2
f(t)e
j!t
dt
f(t) =
1
2
2
4
1
X
!=1
Z
T=2
T=2
f(t)e
j!t
dt
3
5e
j!t
!
T) 1!)d!and
P
)
R
f(t) =
1
2
Z
1
1
Z
1
1
f(t)e
(j!t)
dt
e
(j!t)
d!
f(t) =
1
2
Z
1
1
F(!)e
(j!t)
d!
F(!) =
Z
1
1
f(t)e
(j!t)
dt
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 28 / 91
Fourier TransformFourier Transform
Figure 28: Figure 29:
F(!) =
1=2
Z
1=2
exp(j!t)dt=
1
j!
[exp(j!t)]
1=2
1=2
=
1
j!
[exp(j!=2)exp(j!=2)]
=
1
(!=2)
exp(j!=2)exp(j!=2)
2j
=
sin(!=2)
(!=2)
=sinc(!=2) since it is
sinx
x
form
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 29 / 91
Figure 28: Figure 29:
F(!) =
1=2
Z
1=2
exp(j!t)dt=
1
j!
[exp(j!t)]
1=2
1=2
=
1
j!
[exp(j!=2)exp(j!=2)]
=
1
(!=2)
exp(j!=2)exp(j!=2)
2j
=
sin(!=2)
(!=2)
=sinc(!=2) since it is
sinx
x
form
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 29 / 91
Fourier TransformFourier Transform
Figure 30: Figure 31:
F(!) =
1Z
0
exp(at) exp(j!t)dt
=
1Z
0
exp(atj!t)dt=
1Z
0
exp([a+j!]t)dt
=
1
a+j!
exp([a+j!]t)j
+1
0
=
1
a+j!
[exp(1)exp(0)]
=
1
a+j!
[01]
=
1
a+j!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 30 / 91
Figure 30: Figure 31:
F(!) =
1Z
0
exp(at) exp(j!t)dt
=
1Z
0
exp(atj!t)dt=
1Z
0
exp([a+j!]t)dt
=
1
a+j!
exp([a+j!]t)j
+1
0
=
1
a+j!
[exp(1)exp(0)]
=
1
a+j!
[01]
=
1
a+j!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 30 / 91
Fourier TransformFourier Transform
1Z
1
(t) exp(i!t)dt= exp(i![0]) = 1
1Z
1
1 exp(i!t)dt= 2 (!)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 31 / 91
1Z
1
(t) exp(i!t)dt= exp(i![0]) = 1
1Z
1
1 exp(i!t)dt= 2 (!)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 31 / 91
Fourier TransformFourier Transform
Ffexp(i!0t)g=
1Z
1
exp(i!0t) exp(i!t)dt
=
1Z
1
exp(i[!!0]t)dt
= 2 (!!0)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 32 / 91
Ffexp(i!0t)g=
1Z
1
exp(i!0t) exp(i!t)dt
=
1Z
1
exp(i[!!0]t)dt
= 2 (!!0)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 32 / 91
Fourier TransformFourier Transform
Ffcos(!0t)g=
1Z
1
cos(!0t) exp(j!t)dt
=
1
2
1Z
1
[exp(j!0t) + exp(j!0t)] exp(j!t)dt
=
1
2
1Z
1
exp(j[!!0]t)dt+
1
2
1Z
1
exp(j[!+!0]t)dt
= (!!0) + (!+!0)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 33 / 91
Ffcos(!0t)g=
1Z
1
cos(!0t) exp(j!t)dt
=
1
2
1Z
1
[exp(j!0t) + exp(j!0t)] exp(j!t)dt
=
1
2
1Z
1
exp(j[!!0]t)dt+
1
2
1Z
1
exp(j[!+!0]t)dt
= (!!0) + (!+!0)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 33 / 91
Fourier TransformFourier Transform
Figure 32: A signal with four dierent frequencies
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 34 / 91
Figure 32: A signal with four dierent frequencies
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 34 / 91
Fourier TransformFourier Transform
Figure 33: A signal with four dierent frequency components at four dierent time intervals
Figure 34: Each peak corresponds to a frequency of a periodic component
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 35 / 91
Figure 33: A signal with four dierent frequency components at four dierent time intervals
Figure 34: Each peak corresponds to a frequency of a periodic component
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 35 / 91
Discrete Fourier Transform (DFT)
Discrete Fourier Transform (DFT)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 36 / 91
Discrete Fourier Transform (DFT)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 36 / 91
Discrete Fourier Transform (DFT)
Many applications demand the processing of signals in frequency domain.
The analysis of signal frequency, periodicity, energy and power spectrums can be analyzed
in frequency domain.
Frequency analysis of discrete time signals is usually and most conveniently performed on
a digital signal processor.
Applications of DFT:
Spectral analysis
Convolution of signals
Partial dierential equations
Multiplication of large integers
Data compression
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 37 / 91
Many applications demand the processing of signals in frequency domain.
The analysis of signal frequency, periodicity, energy and power spectrums can be analyzed
in frequency domain.
Frequency analysis of discrete time signals is usually and most conveniently performed on
a digital signal processor.
Applications of DFT:
Spectral analysis
Convolution of signals
Partial dierential equations
Multiplication of large integers
Data compression
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 37 / 91
Discrete Fourier Transform (DFT)Summary of FS and FT
Fourier Series is
x() = a0+
1
X
n=1
ancos(n) +
1
X
n=1
bnsin(n)
wherea0=
1
2
2R
0
x()d
an=
1
2Z
0
x()cos(n)dbn=
1
2Z
0
x()sin(n)d
The Exponential (Complex) Form
x() =
1
X
n=1
cne
jn
where cn=
1
2
Z
x()e
jn
d
x(t) =
1
X
n=1
cne
jn!t
where cn=
1
T
Z
T=2
T=2
x(t)e
jn!t
dt
Fourier Transform pair is
X(!) =
Z
1
1
f(t)e
(!t)
dt (t) =
1
2
Z
1
1
X(!)e
(j!t)
d!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 38 / 91
Fourier Series is
x() = a0+
1
X
n=1
ancos(n) +
1
X
n=1
bnsin(n)
wherea0=
1
2
2R
0
x()d
an=
1
2Z
0
x()cos(n)dbn=
1
2Z
0
x()sin(n)d
The Exponential (Complex) Form
x() =
1
X
n=1
cne
jn
where cn=
1
2
Z
x()e
jn
d
x(t) =
1
X
n=1
cne
jn!t
where cn=
1
T
Z
T=2
T=2
x(t)e
jn!t
dt
Fourier Transform pair is
X(!) =
Z
1
1
f(t)e
(!t)
dt (t) =
1
2
Z
1
1
X(!)e
(j!t)
d!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 38 / 91
Discrete Fourier Transform (DFT)Summary of FS and FT
Time Domain Frequency Domain Transform
Continuous Periodic Discrete nonperiodic Fourier series
Continuous nonperiodicContinuous nonperiodicFourier Transform
Discrete nonperiodic Continuous nonperiodicSequences Fourier Transform
Discrete periodic Discrete periodic Discrete Fourier Transform
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 39 / 91
Time Domain Frequency Domain Transform
Continuous Periodic Discrete nonperiodic Fourier series
Continuous nonperiodicContinuous nonperiodicFourier Transform
Discrete nonperiodic Continuous nonperiodicSequences Fourier Transform
Discrete periodic Discrete periodic Discrete Fourier Transform
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 39 / 91
Discrete Fourier Transform (DFT)Summary of FS and FT
The Fourier Series for
Synthesis Equation x(t) =
1P
k=1
cke
j2nft
Analysis Equation cn=
1
T
1R
1
x(t)e
j2nft
dt
The Fourier Transform for
Synthesis Equation x(t) =
1R
1
X(F)e
j2Ft
dF
Analysis Equation X(F) =
1R
1
x(t)e
j2Ft
dt
The Fourier Series for
Synthesis Equation x(n) =
N1P
k=0
cke
j2kn=N
Analysis Equation ck=
1
N
N1P
n=0
x(n)e
j2kn=N
The Fourier Transform of
Synthesis Equation x(n) =
1
2
1R
1
X(F)e
j2F1t
dF
Analysis Equation X(!) =
1P
n=1
x(n)e
j2kn=N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 40 / 91
The Fourier Series for
Synthesis Equation x(t) =
1P
k=1
cke
j2nft
Analysis Equation cn=
1
T
1R
1
x(t)e
j2nft
dt
The Fourier Transform for
Synthesis Equation x(t) =
1R
1
X(F)e
j2Ft
dF
Analysis Equation X(F) =
1R
1
x(t)e
j2Ft
dt
The Fourier Series for
Synthesis Equation x(n) =
N1P
k=0
cke
j2kn=N
Analysis Equation ck=
1
N
N1P
n=0
x(n)e
j2kn=N
The Fourier Transform of
Synthesis Equation x(n) =
1
2
1R
1
X(F)e
j2F1t
dF
Analysis Equation X(!) =
1P
n=1
x(n)e
j2kn=N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 40 / 91
Discrete Fourier Transform (DFT)Summary of FS and FT
DFT transforms the time domain signal samples to the frequency domain components.Time
Amplitude
Signal
Frequency
Amplitude
Signal
Spectrum
Figure 35:
Signal Types of TransformsExample Waveform
Continuous and periodic Fourier Series sine wave
Continuous and aperiodic Fourier Series
Discrete and periodic Fourier Series
Discrete and aperiodic Fourier Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 41 / 91
DFT transforms the time domain signal samples to the frequency domain components.Time
Amplitude
Signal
Frequency
Amplitude
Signal
Spectrum
Figure 35:
Signal Types of TransformsExample Waveform
Continuous and periodic Fourier Series sine wave
Continuous and aperiodic Fourier Series
Discrete and periodic Fourier Series
Discrete and aperiodic Fourier Series
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 41 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Need For Frequency Domain Sampling
In practical application, signal processed by computer has two main characteristics: It
should be
But !, and it is a
periodic function in!with a .
So it is not suitable to solve practical digital signal processing.
Frequency analysis on a discrete-time signalx(n) is achieved by converting time domain
sequence to an equivalent frequency domain representation, which is represented by the
Fourier transformX(!) of the sequencex(n).
Consider an aperiodic discrete time signal x(n) and its Fourier transform is
X(!) =
1
X
n=1
x(n)e
j!n
The Fourier transformX(!) is a
computationally convenient representation of the sequence.
To, the spectrum of the signal X(!) is sampled periodically in
frequency at a spacing of!radians between successive samples.
The signalX(!) is periodic with period 2and take N equidistant samples in the interval
0!2with spacing= 2=N.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 42 / 91
Need For Frequency Domain Sampling
In practical application, signal processed by computer has two main characteristics: It
should be
But !, and it is a
periodic function in!with a .
So it is not suitable to solve practical digital signal processing.
Frequency analysis on a discrete-time signalx(n) is achieved by converting time domain
sequence to an equivalent frequency domain representation, which is represented by the
Fourier transformX(!) of the sequencex(n).
Consider an aperiodic discrete time signal x(n) and its Fourier transform is
X(!) =
1
X
n=1
x(n)e
j!n
The Fourier transformX(!) is a
computationally convenient representation of the sequence.
To, the spectrum of the signal X(!) is sampled periodically in
frequency at a spacing of!radians between successive samples.
The signalX(!) is periodic with period 2and take N equidistant samples in the interval
0!2with spacing= 2=N.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 42 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Figure 36: Frequency domain
sampling
Figure 37: Frequency domain
sampling
To Determine The Value Of N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 43 / 91
Figure 36: Frequency domain
sampling
Figure 37: Frequency domain
sampling
To Determine The Value Of N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 43 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Now consider!= 2k=N
X
2
N
k
=
1
X
n=1
x(n)e
j2kn=N
k= 0;1;2; : : :N1
X
2
N
k
= +
1
X
n=N
x(n)e
j2kn=N
+
N1
X
n=0
x(n)e
j2kn=N
+
2N1
X
n=N
x(n)e
j2kn=N
+
=
1
X
n=1
lN+N1
X
n=lN
x(n)e
j2kn=N
By changing the index in the inner summation fromntonlNand interchanging the
order of summation
X
2
N
k
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j
2
N
k(nlN)
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j
2
N
kn
e
j2kl
e
j2kl
= 1*both k and l integers
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 44 / 91
Now consider!= 2k=N
X
2
N
k
=
1
X
n=1
x(n)e
j2kn=N
k= 0;1;2; : : :N1
X
2
N
k
= +
1
X
n=N
x(n)e
j2kn=N
+
N1
X
n=0
x(n)e
j2kn=N
+
2N1
X
n=N
x(n)e
j2kn=N
+
=
1
X
n=1
lN+N1
X
n=lN
x(n)e
j2kn=N
By changing the index in the inner summation fromntonlNand interchanging the
order of summation
X
2
N
k
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j
2
N
k(nlN)
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j
2
N
kn
e
j2kl
e
j2kl
= 1*both k and l integers
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 44 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
X
2
N
k
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j2kn=N
k= 0;1;2; : : :N1
Let x p(n) =
1
X
n=1
x(nlN)
The termxp(n) is obtained by the periodic repetition ofx(n) every N samples hence it is
a periodic signal. This can be expanded by Fourier series as
xp(n) =
N1
X
k=0
cke
j2kn=N
n= 0;1; N1
whereckis the fourier coecients expressed as
ck=
1
N
N1
X
n=0
xp(n)e
j2kn=N
k= 0;1; N1
Upon comparing
ck=
1
N
X
2
N
k
k= 0;1; N1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 45 / 91
X
2
N
k
=
N1
X
n=0
2
4
1
X
n=1
x(nlN)
3
5e
j2kn=N
k= 0;1;2; : : :N1
Let x p(n) =
1
X
n=1
x(nlN)
The termxp(n) is obtained by the periodic repetition ofx(n) every N samples hence it is
a periodic signal. This can be expanded by Fourier series as
xp(n) =
N1
X
k=0
cke
j2kn=N
n= 0;1; N1
whereckis the fourier coecients expressed as
ck=
1
N
N1
X
n=0
xp(n)e
j2kn=N
k= 0;1; N1
Upon comparing
ck=
1
N
X
2
N
k
k= 0;1; N1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 45 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
xp(n) =
1
N
N1
X
k=0
X
2
N
k
e
j2kn=N
n= 0;1; N1
xp(n) is the reconstruction of the periodic signal from the spectrumX(!) (IDFT).
The equally spaced frequency samplesX
2
N
k= 0;1; N1 do not uniquely
represent the original sequence whenx(n) has innite duration. Whenx(n) has a nite
duration thenxp(n) is a periodic repetition ofx(n) andxp(n) over a single period is
xp(n) =
x(n) 0 nL1
0 LnN1
For the nite duration sequence of length L the Fourier transform is:
X(!) =
L1
X
n=0
x(n)e
j!n
0!2
WhenX(!) is sampled at frequencies!k= 2k=N k= 0;1;2; : : :N1 then
X(k) = X
2k
N
=
L1
X
n=0
x(n)e
j2kn=N
=
N1
X
n=0
x(n)e
j2kn=N
The upper index in the sum has been increased fromL1 toN1 since x(n)=0 fornL
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 46 / 91
xp(n) =
1
N
N1
X
k=0
X
2
N
k
e
j2kn=N
n= 0;1; N1
xp(n) is the reconstruction of the periodic signal from the spectrumX(!) (IDFT).
The equally spaced frequency samplesX
2
N
k= 0;1; N1 do not uniquely
represent the original sequence whenx(n) has innite duration. Whenx(n) has a nite
duration thenxp(n) is a periodic repetition ofx(n) andxp(n) over a single period is
xp(n) =
x(n) 0 nL1
0 LnN1
For the nite duration sequence of length L the Fourier transform is:
X(!) =
L1
X
n=0
x(n)e
j!n
0!2
WhenX(!) is sampled at frequencies!k= 2k=N k= 0;1;2; : : :N1 then
X(k) = X
2k
N
=
L1
X
n=0
x(n)e
j2kn=N
=
N1
X
n=0
x(n)e
j2kn=N
The upper index in the sum has been increased fromL1 toN1 since x(n)=0 fornL
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 46 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
DFT and IDFT expressions are
DFT expressions is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1
IDFT expressions is
xp(n) =
1
N
N1
X
k=0
X
2
N
k
e
j2kn=N
n= 0;1; N1
Ifxp(n) is evaluated forn= 0;1;2: : :N1 thenxp(n) =x(n)
x(n) =
1
N
N1
X
k=0
X(k)e
j2kn=N
n= 0;1; N1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 47 / 91
DFT and IDFT expressions are
DFT expressions is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1
IDFT expressions is
xp(n) =
1
N
N1
X
k=0
X
2
N
k
e
j2kn=N
n= 0;1; N1
Ifxp(n) is evaluated forn= 0;1;2: : :N1 thenxp(n) =x(n)
x(n) =
1
N
N1
X
k=0
X(k)e
j2kn=N
n= 0;1; N1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 47 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
DFT as a Linear Transformation
X(k) =
N1
X
n=0
x(n)e
j
2
N
kn
k= 0;1; : : :N1
Let
WN=e
j
2
N is called twiddle factor
X(k) =
N1
X
x=0
x(n)W
nk
N
for k= 0;1::;N1
2
6
6
6
6
6
4
X(0)
X(1)
X(2)
.
.
.
X(3)
3
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
4
1 1 1 1 : : : 1
1 W W
2
W
3
: : :W
N1
1W
2
W
2
W
4
: : :W
2(N1)
1W
3
W
6
W
9
: : :W
3(N1)
.
.
.
1W
N1
W
N2
W
N3
: : :W
(N1)(N1)
3
7
7
7
7
7
7
7
7
5
:
2
6
6
6
6
6
4
x(0)
x(1)
x(2)
.
.
.
x(N1)
3
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 48 / 91
DFT as a Linear Transformation
X(k) =
N1
X
n=0
x(n)e
j
2
N
kn
k= 0;1; : : :N1
Let
WN=e
j
2
N is called twiddle factor
X(k) =
N1
X
x=0
x(n)W
nk
N
for k= 0;1::;N1
2
6
6
6
6
6
4
X(0)
X(1)
X(2)
.
.
.
X(3)
3
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
4
1 1 1 1 : : : 1
1 W W
2
W
3
: : :W
N1
1W
2
W
2
W
4
: : :W
2(N1)
1W
3
W
6
W
9
: : :W
3(N1)
.
.
.
1W
N1
W
N2
W
N3
: : :W
(N1)(N1)
3
7
7
7
7
7
7
7
7
5
:
2
6
6
6
6
6
4
x(0)
x(1)
x(2)
.
.
.
x(N1)
3
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 48 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Periodicity property ofWN
WN=e
j
2
N
Let us consider for N=8
W8=e
j
2
81 =e
j
4
kn W
kn
8
=e
4
kn
Result
0 W
0
8
=e
0
Magnitude 1 Phase 0
1 W
1
8
=e
j
4
1
=e
j
4 Magnitude 1 Phase=4
2 W
2
8
=e
j
4
2
=e
j
2 Magnitude 1 Phase=2
3 W
3
8
=e
j
4
3
=e
j3
4 Magnitude 1 Phase3
4
4 W
4
8
=e
j
4
4
=e
j
Magnitude 1 Phase
5 W
5
8
=e
j
4
5
=e
j3
5 Magnitude 1 Phase5=4
6 W
6
8
=e
j
4
6
=e
j3
2 Magnitude 1 Phase3=2
7 W
7
8
=e
j
4
7
=e
j7
4 Magnitude 1 Phase7=4
8 W
8
8
=e
j
4
8
=e
j2
Magnitude 1 Phase2W
8
8
=W
0
8
9 W
9
8
=e
j
4
9
=e
j(2+
4
)
Magnitude 1 Phase (2+=4)W
9
8
=W
1
8
10 W
10
8
=e
j
4
10
=e
j(2
2
)
Magnitude 1 Phase (2+=2)W
10
8
=W
2
8
11 W
11
8
=e
j
4
11
=e
j2+
3
4 W
11
8
=W
3
8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 49 / 91
Periodicity property ofWN
WN=e
j
2
N
Let us consider for N=8
W8=e
j
2
81 =e
j
4
kn W
kn
8
=e
4
kn
Result
0 W
0
8
=e
0
Magnitude 1 Phase 0
1 W
1
8
=e
j
4
1
=e
j
4 Magnitude 1 Phase=4
2 W
2
8
=e
j
4
2
=e
j
2 Magnitude 1 Phase=2
3 W
3
8
=e
j
4
3
=e
j3
4 Magnitude 1 Phase3
4
4 W
4
8
=e
j
4
4
=e
j
Magnitude 1 Phase
5 W
5
8
=e
j
4
5
=e
j3
5 Magnitude 1 Phase5=4
6 W
6
8
=e
j
4
6
=e
j3
2 Magnitude 1 Phase3=2
7 W
7
8
=e
j
4
7
=e
j7
4 Magnitude 1 Phase7=4
8 W
8
8
=e
j
4
8
=e
j2
Magnitude 1 Phase2W
8
8
=W
0
8
9 W
9
8
=e
j
4
9
=e
j(2+
4
)
Magnitude 1 Phase (2+=4)W
9
8
=W
1
8
10 W
10
8
=e
j
4
10
=e
j(2
2
)
Magnitude 1 Phase (2+=2)W
10
8
=W
2
8
11 W
11
8
=e
j
4
11
=e
j2+
3
4 W
11
8
=W
3
8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 49 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)Real part
of W
N
08
88
.. 1WW===
Imaginary
part of W
N
412
88
..
1
WW==
=−
210
88
..WW j===−
19
88
..
11
22
WW
j
==
=−
311
88
..
11
22
WW
j
==
=− −
513
88
..
11
22
WW
j
==
=− +
614
88
..WW j===
715
88
..
11
22
WW
j
==
=+
Figure 38: Periodicity ofWNand its values
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 50 / 91
of W
N
08
88
.. 1WW===
Imaginary
part of W
N
412
88
..
1
WW==
=−
210
88
..WW j===−
19
88
..
11
22
WW
j
==
=−
311
88
..
11
22
WW
j
==
=− −
513
88
..
11
22
WW
j
==
=− +
614
88
..WW j===
715
88
..
11
22
WW
j
==
=+
Figure 38: Periodicity ofWNand its values
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 50 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)Real part
of W
N
04
44
8
4
1WW
W
==
=
26
44
10
4
1WW
W
=− =
=
3711
444
WjWW== =
159
444
WjWW=− = =
Imaginary
part of W
N
Figure 39: Periodicity ofWNand its values
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 51 / 91
of W
N
04
44
8
4
1WW
W
==
=
26
44
10
4
1WW
W
=− =
=
3711
444
WjWW== =
159
444
WjWW=− = =
Imaginary
part of W
N
Figure 39: Periodicity ofWNand its values
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 51 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find Discrete Fourier Transform (DFT) of x(n) = [2 3 4 4]
Solution:
X(k) =
N1
X
n=0
x(n)e
j
2
N
nk
for k= 0;1::;N1
e
j
2=cos
2
jsin
2
=j e
j
=cos()jsin() =1
e
j
3
2=cos
3
2
jsin
3
2
=j e
j2
=cos(2)jsin2() = 1
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
2e
0
+ 3e
0
+ 4e
0
+ 4e
0
= [2 + 3 + 4 + 4] = 13
X(1) =
3P
n=0
x(n)e
j
2n
4=
2e
0
+ 3e
j=2
+ 4e
j
+ 4e
j3=2
= [23j4 + 4j] = [2 +j]
X(2) =
3P
n=0
x(n)e
j4n
4=
2e
0
+ 3e
j
+ 4e
j2
+ 4e
j3
= [23 + 44] = [10j] =1
X(3) =
3P
n=0
x(n)e
j6n
4=
2e
0
+ 3e
j3=2
+ 4e
j3
+ 4e
j9=2
= [2 + 3j44j][2j]
The DFT of the sequence x(n) = [2 3 4 4] is [13, -2+j, -1, -2-j]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 52 / 91
Find Discrete Fourier Transform (DFT) of x(n) = [2 3 4 4]
Solution:
X(k) =
N1
X
n=0
x(n)e
j
2
N
nk
for k= 0;1::;N1
e
j
2=cos
2
jsin
2
=j e
j
=cos()jsin() =1
e
j
3
2=cos
3
2
jsin
3
2
=j e
j2
=cos(2)jsin2() = 1
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
2e
0
+ 3e
0
+ 4e
0
+ 4e
0
= [2 + 3 + 4 + 4] = 13
X(1) =
3P
n=0
x(n)e
j
2n
4=
2e
0
+ 3e
j=2
+ 4e
j
+ 4e
j3=2
= [23j4 + 4j] = [2 +j]
X(2) =
3P
n=0
x(n)e
j4n
4=
2e
0
+ 3e
j
+ 4e
j2
+ 4e
j3
= [23 + 44] = [10j] =1
X(3) =
3P
n=0
x(n)e
j6n
4=
2e
0
+ 3e
j3=2
+ 4e
j3
+ 4e
j9=2
= [2 + 3j44j][2j]
The DFT of the sequence x(n) = [2 3 4 4] is [13, -2+j, -1, -2-j]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 52 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find Discrete Fourier Transform (DFT) of x(n) = [2 3 4 4]
X(k) =
N1
X
n=0
x(n)e
j
2
N
nk
for k= 0;1::;N1
Matlab code for the DFT equation is:
clc; clear all; close all
xn=[2 3 4 4]
N=length(xn);
n=0:N-1;
k=0:N-1;
WN=exp(-1j*2*pi/N);
nk=n'*k;
WNnk=WN.^nk;
Xk=xn*WNnk
Matlab code using FFT command
clc; clear all; close all
xn=[2 3 4 4]
y=fft(xn)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 53 / 91
Find Discrete Fourier Transform (DFT) of x(n) = [2 3 4 4]
X(k) =
N1
X
n=0
x(n)e
j
2
N
nk
for k= 0;1::;N1
Matlab code for the DFT equation is:
clc; clear all; close all
xn=[2 3 4 4]
N=length(xn);
n=0:N-1;
k=0:N-1;
WN=exp(-1j*2*pi/N);
nk=n'*k;
WNnk=WN.^nk;
Xk=xn*WNnk
Matlab code using FFT command
clc; clear all; close all
xn=[2 3 4 4]
y=fft(xn)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 53 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find DFT for a given a sequencex(n) for 0n3 where
x(0) = 1;x(1) = 2;x(2) = 3;x(3) = 4
Solution:
x(n) = [1 2 3 4]
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
4e
0
+ 2e
0
+ 3e
0
+ 4e
0
= [1 + 2 + 3 + 4] = 10
X(1) =
3P
n=0
x(n)e
j
2n
4=
1e
0
+ 2e
j=2
+ 2e
j
+ 4e
j3=2
= [1j23 +j4] = [2 +j2]
X(2) =
3P
n=0
x(n)e
j4n
4=
1e
0
+ 2e
j
+ 3e
j2
+ 4e
j3
= [12 + 34] = [10j] =2
X(3) =
3P
n=0
x(n)e
j6n
4=
1e
0
+ 2e
j3=2
+ 3e
j3
+ 4e
j9=2
= [1 + 2j34j][2j2]
The DFT of the sequence x(n) = [1 2 3 4] is [10;2 +j2;2;2j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 54 / 91
Find DFT for a given a sequencex(n) for 0n3 where
x(0) = 1;x(1) = 2;x(2) = 3;x(3) = 4
Solution:
x(n) = [1 2 3 4]
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
4e
0
+ 2e
0
+ 3e
0
+ 4e
0
= [1 + 2 + 3 + 4] = 10
X(1) =
3P
n=0
x(n)e
j
2n
4=
1e
0
+ 2e
j=2
+ 2e
j
+ 4e
j3=2
= [1j23 +j4] = [2 +j2]
X(2) =
3P
n=0
x(n)e
j4n
4=
1e
0
+ 2e
j
+ 3e
j2
+ 4e
j3
= [12 + 34] = [10j] =2
X(3) =
3P
n=0
x(n)e
j6n
4=
1e
0
+ 2e
j3=2
+ 3e
j3
+ 4e
j9=2
= [1 + 2j34j][2j2]
The DFT of the sequence x(n) = [1 2 3 4] is [10;2 +j2;2;2j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 54 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find 8 point DFT for a given a sequencex(n) = [1;1;1;1] assume imaginary part is zero. Also
calculate magnitude and phase
Solution:
x(n) = [1 1 1 1]
The 8 point DFT is of length 8. Append zeros at the end of the sequence. x(n) = [1 1 1 1 0 0 0
0]
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1W
1
8
W
2
8
W
3
8
W
4
8
W
5
8
W
6
8
W
7
8
1W
2
8
W
4
8
W
6
8
W
8
8
W
10
8
W
12
8
W
14
8
1W
3
8
W
6
8
W
9
8
W
12
8
W
15
8
W
18
8
W
21
8
1W
4
8
W
8
8
W
12
8
W
16
8
W
20
8
W
24
8
W
28
8
1W
5
8
W
10
8
W
15
8
W
20
8
W
25
8
W
30
8
W
35
8
1W
6
8
W
12
8
W
18
8
W
24
8
W
30
8
W
36
8
W
42
8
1W
7
8
W
14
8
W
21
8
W
28
8
W
35
8
W
42
8
W
49
8
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
x(0)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 55 / 91
Find 8 point DFT for a given a sequencex(n) = [1;1;1;1] assume imaginary part is zero. Also
calculate magnitude and phase
Solution:
x(n) = [1 1 1 1]
The 8 point DFT is of length 8. Append zeros at the end of the sequence. x(n) = [1 1 1 1 0 0 0
0]
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1W
1
8
W
2
8
W
3
8
W
4
8
W
5
8
W
6
8
W
7
8
1W
2
8
W
4
8
W
6
8
W
8
8
W
10
8
W
12
8
W
14
8
1W
3
8
W
6
8
W
9
8
W
12
8
W
15
8
W
18
8
W
21
8
1W
4
8
W
8
8
W
12
8
W
16
8
W
20
8
W
24
8
W
28
8
1W
5
8
W
10
8
W
15
8
W
20
8
W
25
8
W
30
8
W
35
8
1W
6
8
W
12
8
W
18
8
W
24
8
W
30
8
W
36
8
W
42
8
1W
7
8
W
14
8
W
21
8
W
28
8
W
35
8
W
42
8
W
49
8
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
x(0)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 55 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
W
0
8
=W
8
8
=W
16
8
=W
24
8
=W
40
8
:::= 1
W
1
8
=W
9
8
=W
17
8
=W
25
8
=W
33
8
:::=
1
p
2
j
1
p
2
W
2
8
=W
10
8
=W
18
8
=W
26
8
=W
34
8
:::=j
W
3
8
=W
11
8
=W
19
8
=W
27
8
=W
35
8
:::=
1
p
2
j
1
p
2
W
4
8
=W
12
8
=W
20
8
=W
28
8
=W
36
8
:::=1
W
5
8
=W
13
8
=W
21
8
=W
29
8
=W
37
8
:::=
1
p
2
+j
1
p
2
W
6
8
=W
14
8
=W
22
8
=W
30
8
=W
38
8
:::=j
W
7
8
=W
15
8
=W
23
8
=W
31
8
=W
39
8
:::=
1
p
2
+j
1
p
2
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 1 1 1 1 1 1 1
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
3
7
7
7
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1
1
1
1
0
0
0
0
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
4
1j(1 +
p
2)
0
1 +j(1
p
2)
0
1j(1
p
2)
0
1 +j(1 +
p
2)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
X
R(0)
X
R(1)
X
R(2)
X
R(3)
X
R(4)
X
R(5)
X
R(6)
X
R(7)
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
4
1
0
1
0
1
0
1
3
7
7
7
7
7
7
7
7
7
5
and
2
6
6
6
6
6
6
6
6
6
4
X
I(0)
X
I(1)
X
I(2)
X
I(3)
X
I(4)
X
I(5)
X
I(6)
X
I(7)
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
0
(1 +
p
2)
0
(1
p
2)
0
(1
p
2)
0
(1 +
p
2)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 56 / 91
W
0
8
=W
8
8
=W
16
8
=W
24
8
=W
40
8
:::= 1
W
1
8
=W
9
8
=W
17
8
=W
25
8
=W
33
8
:::=
1
p
2
j
1
p
2
W
2
8
=W
10
8
=W
18
8
=W
26
8
=W
34
8
:::=j
W
3
8
=W
11
8
=W
19
8
=W
27
8
=W
35
8
:::=
1
p
2
j
1
p
2
W
4
8
=W
12
8
=W
20
8
=W
28
8
=W
36
8
:::=1
W
5
8
=W
13
8
=W
21
8
=W
29
8
=W
37
8
:::=
1
p
2
+j
1
p
2
W
6
8
=W
14
8
=W
22
8
=W
30
8
=W
38
8
:::=j
W
7
8
=W
15
8
=W
23
8
=W
31
8
=W
39
8
:::=
1
p
2
+j
1
p
2
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 1 1 1 1 1 1 1
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
3
7
7
7
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1
1
1
1
0
0
0
0
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
4
1j(1 +
p
2)
0
1 +j(1
p
2)
0
1j(1
p
2)
0
1 +j(1 +
p
2)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
X
R(0)
X
R(1)
X
R(2)
X
R(3)
X
R(4)
X
R(5)
X
R(6)
X
R(7)
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
4
1
0
1
0
1
0
1
3
7
7
7
7
7
7
7
7
7
5
and
2
6
6
6
6
6
6
6
6
6
4
X
I(0)
X
I(1)
X
I(2)
X
I(3)
X
I(4)
X
I(5)
X
I(6)
X
I(7)
3
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
0
(1 +
p
2)
0
(1
p
2)
0
(1
p
2)
0
(1 +
p
2)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 56 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find DFT for a given a sequencex(n) = [2 3 4 4]
Solution: 2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1W W
2
W
3
1W
2
W
4
W
6
1W
3
W
6
W
9
3
7
7
5
=
2
6
6
4
2
3
4
4
3
7
7
5
WN=e
2
N=e
2
4=e
2=j
W
2
=j
2
=1,W
3
=j
3
=j
Using the property of periodicity of WW
p
=W
P+r:N
=jwith basic periodN= 4
W
4
=W
44
=W
0
= 1,W
6
=W
64
=W
2
=1,W
9
=W
92:4
=W
1
=j
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
2
3
4
4
3
7
7
5
=
2
6
6
4
13
2 +j
1
2j
3
7
7
5
The DFT of the sequence x(n) = [2 3 4 4] is [13;2 +j;1;2j]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 57 / 91
Find DFT for a given a sequencex(n) = [2 3 4 4]
Solution: 2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1W W
2
W
3
1W
2
W
4
W
6
1W
3
W
6
W
9
3
7
7
5
=
2
6
6
4
2
3
4
4
3
7
7
5
WN=e
2
N=e
2
4=e
2=j
W
2
=j
2
=1,W
3
=j
3
=j
Using the property of periodicity of WW
p
=W
P+r:N
=jwith basic periodN= 4
W
4
=W
44
=W
0
= 1,W
6
=W
64
=W
2
=1,W
9
=W
92:4
=W
1
=j
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
2
3
4
4
3
7
7
5
=
2
6
6
4
13
2 +j
1
2j
3
7
7
5
The DFT of the sequence x(n) = [2 3 4 4] is [13;2 +j;1;2j]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 57 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find DFT for a given a sequencex(n) = [1 2 3 4]
Solution: 2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1W W
2
W
3
1W
2
W
4
W
6
1W
3
W
6
W
9
3
7
7
5
=
2
6
6
4
1
2
3
4
3
7
7
5
WN=e
2
N=e
2
4=e
2=j
W
2
=j
2
=1,W
3
=j
3
=j
Using the property of periodicity of WW
p
=W
P+r:N
=jwith basic periodN= 4
W
4
=W
44
=W
0
= 1,W
6
=W
64
=W
2
=1,W
9
=W
92:4
=W
1
=j
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
2
3
4
3
7
7
5
=
2
6
6
4
10
2 + 2j
2
22j
3
7
7
5
The DFT of the sequence x(n) = [1 2 3 4] is [10;2 +j2;2;2j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 58 / 91
Find DFT for a given a sequencex(n) = [1 2 3 4]
Solution: 2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1W W
2
W
3
1W
2
W
4
W
6
1W
3
W
6
W
9
3
7
7
5
=
2
6
6
4
1
2
3
4
3
7
7
5
WN=e
2
N=e
2
4=e
2=j
W
2
=j
2
=1,W
3
=j
3
=j
Using the property of periodicity of WW
p
=W
P+r:N
=jwith basic periodN= 4
W
4
=W
44
=W
0
= 1,W
6
=W
64
=W
2
=1,W
9
=W
92:4
=W
1
=j
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
2
3
4
3
7
7
5
=
2
6
6
4
10
2 + 2j
2
22j
3
7
7
5
The DFT of the sequence x(n) = [1 2 3 4] is [10;2 +j2;2;2j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 58 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Inverse DFT: Find the IDFT for X(k) = [10;2 +j2;2;2j2]
x(n) =
1
N
N1
X
k=0
X(k)e
2
N
kn
for n= 0;1::;N1
x(n) =
1
N
N1
X
k=0
X(k)W
kn
for n= 0;1::;N1where W
=e
2
N
x(0) =
1
4
N1
X
k=0
X(k)e
j0
=X(0)e
j0
+X(1)e
j0
+X(2)e
j0
+X(3)e
j0
=
1
4
(10 + (2 +j2)2 + (2j2)) = 1
x(1) =
1
4
N1
X
k=0
X(k)e
j
k
2=X(0)e
j0
+X(1)e
j
2+X(2)e
j
+X(3)e
j
3
2
=
1
4
(X(0) +jX(1)X(2)jX(3)
=
1
4
(10 +j(2 +j2)(2)j(2j2)) = 2
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 59 / 91
Inverse DFT: Find the IDFT for X(k) = [10;2 +j2;2;2j2]
x(n) =
1
N
N1
X
k=0
X(k)e
2
N
kn
for n= 0;1::;N1
x(n) =
1
N
N1
X
k=0
X(k)W
kn
for n= 0;1::;N1where W
=e
2
N
x(0) =
1
4
N1
X
k=0
X(k)e
j0
=X(0)e
j0
+X(1)e
j0
+X(2)e
j0
+X(3)e
j0
=
1
4
(10 + (2 +j2)2 + (2j2)) = 1
x(1) =
1
4
N1
X
k=0
X(k)e
j
k
2=X(0)e
j0
+X(1)e
j
2+X(2)e
j
+X(3)e
j
3
2
=
1
4
(X(0) +jX(1)X(2)jX(3)
=
1
4
(10 +j(2 +j2)(2)j(2j2)) = 2
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 59 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
x(2) =
1
4
N1
X
k=0
X(k)e
j
k
2=X(0)e
j0
+X(1)e
j
+X(2)e
j2
+X(3)e
j3
=
1
4
(X(0)X(1) +X(2)X(3)
=
1
4
(10(2 +j2) + (2)(2j2)) = 3
x(1) =
1
4
N1
X
k=0
X(k)e
j
k3
2=X(0)e
j0
+X(1)e
j
3
2+X(2)e
j3
+X(3)e
j
9
2
=
1
4
(X(0)jX(1)X(2) +jX(3)
=
1
4
(10j(2 +j2)(2) +j(2j2)) = 4
Matlab command used to calculate the Inverse DFT isit
x=[10 -2+j2 -2 -2-j2]
y=ifft(x)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 60 / 91
x(2) =
1
4
N1
X
k=0
X(k)e
j
k
2=X(0)e
j0
+X(1)e
j
+X(2)e
j2
+X(3)e
j3
=
1
4
(X(0)X(1) +X(2)X(3)
=
1
4
(10(2 +j2) + (2)(2j2)) = 3
x(1) =
1
4
N1
X
k=0
X(k)e
j
k3
2=X(0)e
j0
+X(1)e
j
3
2+X(2)e
j3
+X(3)e
j
9
2
=
1
4
(X(0)jX(1)X(2) +jX(3)
=
1
4
(10j(2 +j2)(2) +j(2j2)) = 4
Matlab command used to calculate the Inverse DFT isit
x=[10 -2+j2 -2 -2-j2]
y=ifft(x)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 60 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the Discrete Fourier Transform of the following signal: x(n), n = 0,1,2,3 = [1, 1, -1, -1].
Solution:
N=4 The matrix notation is
X=T:f
whereTis matrix of the transform with elementsTkn=W
kn
N
k;n= 0;1::;N1
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
1
1
1
3
7
7
5
=
2
6
6
4
0
22j
0
2 + 2j
3
7
7
5
The DFT of the sequence x(n) = [1 1 -1 -1] is [0;2j2;0;2 +j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 61 / 91
Find the Discrete Fourier Transform of the following signal: x(n), n = 0,1,2,3 = [1, 1, -1, -1].
Solution:
N=4 The matrix notation is
X=T:f
whereTis matrix of the transform with elementsTkn=W
kn
N
k;n= 0;1::;N1
2
6
6
4
X(0)
X(1)
X(2)
X(3)
3
7
7
5
=
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
1
1
1
3
7
7
5
=
2
6
6
4
0
22j
0
2 + 2j
3
7
7
5
The DFT of the sequence x(n) = [1 1 -1 -1] is [0;2j2;0;2 +j2]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 61 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the Inverse Discrete Fourier Transform of the following signal: x(n), n = 0,1,2,3 = [0, 2-2j,
0, 2+2j].
Solution:
The IDFT of the discrete signal X(k)is x(n):
N= 4 andW4=e
=2
x(n) =
1
N
N1
X
k=0
X(k)W
kn
N
for n= 0;1::;N1where W=e
2
N
N=4 The matrix notation is
[WN] =
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
[W
N
] =
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
x(0)
x(1)
x(2)
x(3)
3
7
7
5
=
1
N
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
0
22j
0
2 + 2j
3
7
7
5
=
2
6
6
4
1
1
1
1
3
7
7
5
The IDFT of the sequenceX(k) = [0;2j2;0;2 +j2] is [1 1 -1 -1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 62 / 91
Find the Inverse Discrete Fourier Transform of the following signal: x(n), n = 0,1,2,3 = [0, 2-2j,
0, 2+2j].
Solution:
The IDFT of the discrete signal X(k)is x(n):
N= 4 andW4=e
=2
x(n) =
1
N
N1
X
k=0
X(k)W
kn
N
for n= 0;1::;N1where W=e
2
N
N=4 The matrix notation is
[WN] =
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
[W
N
] =
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
x(0)
x(1)
x(2)
x(3)
3
7
7
5
=
1
N
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
0
22j
0
2 + 2j
3
7
7
5
=
2
6
6
4
1
1
1
1
3
7
7
5
The IDFT of the sequenceX(k) = [0;2j2;0;2 +j2] is [1 1 -1 -1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 62 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find DFT for a given a sequence x[0]=1, x[1]=2, x[2]=2, x[3]=1, x[n]=0 otherwise: x =
[1,2,2,1]
Solution:
x(n) = [1 2 2 1]
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
1e
0
+ 2e
0
+ 2e
0
+ 1e
0
= [1 + 2 + 2 + 1] = 6
X(1) =
3P
n=0
x(n)e
j
2n
4=
1e
0
+ 2e
j=2
+ 2e
j
+ 1e
j3=2
= [1j22 +j1] = [1j1]
X(2) =
3P
n=0
x(n)e
j4n
4=
1e
0
+ 2e
j
+ 2e
j2
+ 1e
j3
= [12 + 21] = [0] = 0
X(3) =
3P
n=0
x(n)e
j6n
4=
1e
0
+ 2e
j3=2
+ 2e
j3
+ 1e
j9=2
= [1 + 2j21j][1 +j1]
The DFT of the sequence x(n) = [1 2 2 1] is [6;1j1;0;1 +j1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 63 / 91
Find DFT for a given a sequence x[0]=1, x[1]=2, x[2]=2, x[3]=1, x[n]=0 otherwise: x =
[1,2,2,1]
Solution:
x(n) = [1 2 2 1]
for k=0,1,2,3
X(0) =
3P
n=0
x(n)e
0
=
1e
0
+ 2e
0
+ 2e
0
+ 1e
0
= [1 + 2 + 2 + 1] = 6
X(1) =
3P
n=0
x(n)e
j
2n
4=
1e
0
+ 2e
j=2
+ 2e
j
+ 1e
j3=2
= [1j22 +j1] = [1j1]
X(2) =
3P
n=0
x(n)e
j4n
4=
1e
0
+ 2e
j
+ 2e
j2
+ 1e
j3
= [12 + 21] = [0] = 0
X(3) =
3P
n=0
x(n)e
j6n
4=
1e
0
+ 2e
j3=2
+ 2e
j3
+ 1e
j9=2
= [1 + 2j21j][1 +j1]
The DFT of the sequence x(n) = [1 2 2 1] is [6;1j1;0;1 +j1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 63 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find IDFT for a given a sequence X[0]=6, X[1]=-1-j1, X[2]=0, X[3]=-1+j1, X[n]=0 otherwise:
x = [6;1j1;0;1 +j1]
Solution:
x(n) = [6;1j1;0;1 +j1]
for k=0,1,2,3
X(0) =
1
4
3P
n=0
x(n)e
0
=
6e
0
+ (1j1)e
0
+ 0e
0
+ (1 +j1)e
0
=
1
4
[61j1+01+j1] = 1
X(1) =
1
4
3P
n=0
x(n)e
j
2n
4=
6e
0
+ (1j1)e
j=2
+ 0e
j
+ (1 +j1)e
j3=2
=
1
4
[6j+ 1 +j+ 1] = [2]
X(2) =
1
4
3P
n=0
x(n)e
j4n
4=
6e
0
+ (1j1)e
j
+ 0e
j2
+ (1 +j1)e
j3
=
1
4
[6 + (1j1)(j) + 0 + (1 +j)(j)] =
1
4
[6j1 + 1 + 0 + 1 +j] = [2]
X(3) =
1
4
3P
n=0
x(n)e
j6n
4=
6e
0
+ (1j1)e
j3=2
+ 0e
j3
+ (1 +j1)e
j9=2
=
1
4
[6 + (1j1)(j) + 0 + (1 +j)(j)] =
1
4
[6 +j11 + 01j] = [1]
The IDFT of the sequence [6;1j1;0;1 +j1] is x(n) = [1 2 2 1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 64 / 91
Find IDFT for a given a sequence X[0]=6, X[1]=-1-j1, X[2]=0, X[3]=-1+j1, X[n]=0 otherwise:
x = [6;1j1;0;1 +j1]
Solution:
x(n) = [6;1j1;0;1 +j1]
for k=0,1,2,3
X(0) =
1
4
3P
n=0
x(n)e
0
=
6e
0
+ (1j1)e
0
+ 0e
0
+ (1 +j1)e
0
=
1
4
[61j1+01+j1] = 1
X(1) =
1
4
3P
n=0
x(n)e
j
2n
4=
6e
0
+ (1j1)e
j=2
+ 0e
j
+ (1 +j1)e
j3=2
=
1
4
[6j+ 1 +j+ 1] = [2]
X(2) =
1
4
3P
n=0
x(n)e
j4n
4=
6e
0
+ (1j1)e
j
+ 0e
j2
+ (1 +j1)e
j3
=
1
4
[6 + (1j1)(j) + 0 + (1 +j)(j)] =
1
4
[6j1 + 1 + 0 + 1 +j] = [2]
X(3) =
1
4
3P
n=0
x(n)e
j6n
4=
6e
0
+ (1j1)e
j3=2
+ 0e
j3
+ (1 +j1)e
j9=2
=
1
4
[6 + (1j1)(j) + 0 + (1 +j)(j)] =
1
4
[6 +j11 + 01j] = [1]
The IDFT of the sequence [6;1j1;0;1 +j1] is x(n) = [1 2 2 1]
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 64 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Continuous Time Fourier Transform (CTFT)
X(j!) =
1Z
1
x(t)e
j!t
dt
x(t) =
1
2
1Z
1
X(j!)e
j!t
d!
Discrete Time Fourier Transform (DTFT)
X(e
j!
) =
1
X
1
x(n)e
j!n
x(n) =
1
2
Z
2
X(e
j!
)e
j!n
d!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 65 / 91
Continuous Time Fourier Transform (CTFT)
X(j!) =
1Z
1
x(t)e
j!t
dt
x(t) =
1
2
1Z
1
X(j!)e
j!t
d!
Discrete Time Fourier Transform (DTFT)
X(e
j!
) =
1
X
1
x(n)e
j!n
x(n) =
1
2
Z
2
X(e
j!
)e
j!n
d!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 65 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Unit sample(n)
x(n) =
1for n= 0
0for n6= 0
X(k) =
N1
X
x=0
x(n)e
j
2
N
nk
=
N1
X
x=0
x(0)e
0
= 11 = 1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 66 / 91
Unit sample(n)
x(n) =
1for n= 0
0for n6= 0
X(k) =
N1
X
x=0
x(n)e
j
2
N
nk
=
N1
X
x=0
x(0)e
0
= 11 = 1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 66 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the N Point DFT ofx(n) =a
n
for0nN1
X(k) =
N1
X
x=0
x(n)e
j
2
N
nk
=
N1
X
x=0
a
n
e
j
2
N
nk
=
N1
X
x=0
(ae
j
2k
N)
n
X(k) =
1a
N
e
j2k
1ae
j2k
=N
Using series expansion
N1
X
k=0
a
k
=
a
N1a
N2+1
1a
!
e
j2k
= 1
X(k) =
1a
N
1ae
j2k
=N
x[n] = (0:5)
n
u[n] 0n3
X(k) =
1(0:5)
4
10:5e
j2k
=4
=
0:9375
10:5e
j=2k
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 67 / 91
Find the N Point DFT ofx(n) =a
n
for0nN1
X(k) =
N1
X
x=0
x(n)e
j
2
N
nk
=
N1
X
x=0
a
n
e
j
2
N
nk
=
N1
X
x=0
(ae
j
2k
N)
n
X(k) =
1a
N
e
j2k
1ae
j2k
=N
Using series expansion
N1
X
k=0
a
k
=
a
N1a
N2+1
1a
!
e
j2k
= 1
X(k) =
1a
N
1ae
j2k
=N
x[n] = (0:5)
n
u[n] 0n3
X(k) =
1(0:5)
4
10:5e
j2k
=4
=
0:9375
10:5e
j=2k
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 67 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the 4 Point DFT ofx(n) =cos(
n
4
)
Solution:
x(0) =cos(0) = 1
x(1) =cos(
1
4
) = 0:707
x(2) =cos(
2
4
) = 0
x(3) =cos(
3
4
) =0:707
2
6
6
4
x(0)
x(1)
x(2)
x(3)
3
7
7
5
=
1
N
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
0:707
0
0:707
3
7
7
5
=
2
6
6
4
1
1j1:414
1
1 +j1:414
3
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 68 / 91
Find the 4 Point DFT ofx(n) =cos(
n
4
)
Solution:
x(0) =cos(0) = 1
x(1) =cos(
1
4
) = 0:707
x(2) =cos(
2
4
) = 0
x(3) =cos(
3
4
) =0:707
2
6
6
4
x(0)
x(1)
x(2)
x(3)
3
7
7
5
=
1
N
2
6
6
4
1 1 1 1
1j1j
11 1 1
1j1j
3
7
7
5
2
6
6
4
1
0:707
0
0:707
3
7
7
5
=
2
6
6
4
1
1j1:414
1
1 +j1:414
3
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 68 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
If the length ofx[n] is N=4, and if its 8-point DFT is:X8[k]
k= 0::7 = [5;3
p
2j;3;1
p
2j;1;1 +
p
2j;3;3 +
p
2j] , nd the 4 point DFT of the signal
x[n].
Solution:
The samples ofXs[k] are eight equally spaced samples from the frequency spectrum of
the signalx[n]:
More precisely, they are samples from the spectrum for the following frequencies:
!T=
0;
4
;
2
;
3
4
;
5
4
;
3
2
;
7
4
With 4-point DFT of x[n] we get 4 samples from the spectrum of x[n]:!T=
0;
2
; ;
3
2
By comparing the two sets of frequencies:
X4[0] =X(e
j0
) =Xs[0] = 5
X4[1] =X(e
j=2
) =Xs[2] = 3
X4[2] =X(e
j
) =Xs[4] = 1
X4[3] =X(e
j3=2
) =Xs[6] = 3
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 69 / 91
If the length ofx[n] is N=4, and if its 8-point DFT is:X8[k]
k= 0::7 = [5;3
p
2j;3;1
p
2j;1;1 +
p
2j;3;3 +
p
2j] , nd the 4 point DFT of the signal
x[n].
Solution:
The samples ofXs[k] are eight equally spaced samples from the frequency spectrum of
the signalx[n]:
More precisely, they are samples from the spectrum for the following frequencies:
!T=
0;
4
;
2
;
3
4
;
5
4
;
3
2
;
7
4
With 4-point DFT of x[n] we get 4 samples from the spectrum of x[n]:!T=
0;
2
; ;
3
2
By comparing the two sets of frequencies:
X4[0] =X(e
j0
) =Xs[0] = 5
X4[1] =X(e
j=2
) =Xs[2] = 3
X4[2] =X(e
j
) =Xs[4] = 1
X4[3] =X(e
j3=2
) =Xs[6] = 3
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 69 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the Fourier Transform of the sequence
x[n] =
1 0n4
0 else
X
e
jw
=
1
X
n=1
x[n]e
jwn
X
e
j!
=e
j2!
sin (5!=2)
sin (!=2)
Consider a causal sequence x[n] where;
x[n] = (0:5)
n
u[n]
Its DTFTX
e
jw
can be obtained as
X
e
jw
=
1
X
n=1
(0:5)
n
u[n]e
jwn
=
1
X
n=0
(0:5)
n
(1)e
jwn
=
1
X
n=0
0:5e
jw
n
=
1
10:5e
jw
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 70 / 91
Find the Fourier Transform of the sequence
x[n] =
1 0n4
0 else
X
e
jw
=
1
X
n=1
x[n]e
jwn
X
e
j!
=e
j2!
sin (5!=2)
sin (!=2)
Consider a causal sequence x[n] where;
x[n] = (0:5)
n
u[n]
Its DTFTX
e
jw
can be obtained as
X
e
jw
=
1
X
n=1
(0:5)
n
u[n]e
jwn
=
1
X
n=0
(0:5)
n
(1)e
jwn
=
1
X
n=0
0:5e
jw
n
=
1
10:5e
jw
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 70 / 91
Discrete Fourier Transform (DFT)Discrete Fourier Transform (DFT)
Find the N Point DFT ofx(n) = 4 +cos
2
(
2n
N
)
Solution:
x(0) = 4 +cos
2
(0) = 5
x(1) = 4 +cos
2
(
21
10
) = 4:6545
x(2) = 4 +cos
2
(
22
10
) = 4:09549
x(3) = 4 +cos
2
(
23
10
) = 4:09549
x(4) = 4 +cos
2
(
24
10
) = 4:09549
x(5) = 4 +cos
2
(
25
10
) = 5
x(6) = 4 +cos
2
(
26
10
) = 4:6545
x(7) = 4 +cos
2
(
27
10
) = 4:09549
x(8) = 4 +cos
2
(
28
10
) = 4:09549
x(9) = 4 +cos
2
(
29
10
) = 4:6545
x(n) =x(Nn)
Cosine function is even function
x(n) =x(n)
X(k) =
N1
X
n=0
x(n)cos
2kn
N
0kN1
X(k) =
N1
X
n=0
4 +cos
2
(
2n
N
)
cos
2kn
N
0kN1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 71 / 91
Find the N Point DFT ofx(n) = 4 +cos
2
(
2n
N
)
Solution:
x(0) = 4 +cos
2
(0) = 5
x(1) = 4 +cos
2
(
21
10
) = 4:6545
x(2) = 4 +cos
2
(
22
10
) = 4:09549
x(3) = 4 +cos
2
(
23
10
) = 4:09549
x(4) = 4 +cos
2
(
24
10
) = 4:09549
x(5) = 4 +cos
2
(
25
10
) = 5
x(6) = 4 +cos
2
(
26
10
) = 4:6545
x(7) = 4 +cos
2
(
27
10
) = 4:09549
x(8) = 4 +cos
2
(
28
10
) = 4:09549
x(9) = 4 +cos
2
(
29
10
) = 4:6545
x(n) =x(Nn)
Cosine function is even function
x(n) =x(n)
X(k) =
N1
X
n=0
x(n)cos
2kn
N
0kN1
X(k) =
N1
X
n=0
4 +cos
2
(
2n
N
)
cos
2kn
N
0kN1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 71 / 91
Relationship of the DFT to other TransformsRelationship of the DFT to other Transforms
Relationship of the DFT to other Transforms
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 72 / 91
Relationship of the DFT to other Transforms
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 72 / 91
Relationship of the DFT to other TransformsRelationship of the DFT to other Transforms
Relationship to the Fourier series coecients of periodic sequence
DFT expression is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1 (1)
IDFT expression is
x(n) =
1
N
N1
X
k=0
X(k)e
j2kn=N
n= 0;1; N1 (2)
Fourier series is
xp(n) =
N1
X
k=0
cke
j
2
N
nk
1 n 1 (3)
Fourier series coecients are expressed as:
ck=
1
N
N1
X
k=0
xp(n)e
j
2
N
nk
k= 0;1::;N1 (4)
By comparingX(k) andckfourier series coecients has the form of a DFT.
x(n) =xp(n) 0nN1
X(k) =Nck0nN1
Fourier series has the form of an IDFT
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 73 / 91
Relationship to the Fourier series coecients of periodic sequence
DFT expression is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1 (1)
IDFT expression is
x(n) =
1
N
N1
X
k=0
X(k)e
j2kn=N
n= 0;1; N1 (2)
Fourier series is
xp(n) =
N1
X
k=0
cke
j
2
N
nk
1 n 1 (3)
Fourier series coecients are expressed as:
ck=
1
N
N1
X
k=0
xp(n)e
j
2
N
nk
k= 0;1::;N1 (4)
By comparingX(k) andckfourier series coecients has the form of a DFT.
x(n) =xp(n) 0nN1
X(k) =Nck0nN1
Fourier series has the form of an IDFT
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 73 / 91
Relationship of the DFT to other TransformsRelationship of the DFT to other Transforms
Relationship to the Fourier transform of an aperiodic sequence (DFT and DTFT)
Fourier transformX(!)
X(!) =
1
X
n=1
x(n)
j!n
1 n 1 (5)
X(k) =X(!j
!=2k=N) =
1
X
n=1
x(n)
j
2
N
nk
1 n 1 (6)
DFT coecients are expressed as:
xp(n) =
1
X
n=1
x(nlN) (7)
xp(n) is determined by aliasing x(n) over the interval 0nN1. The nite duration
sequence
^x(n) =
xp(n) 0nN1
0Otherwise
The relation between ^x(n)and x(n) exist when x(n) is of nite duration
x(n) = ^x(n) 0nN1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 74 / 91
Relationship to the Fourier transform of an aperiodic sequence (DFT and DTFT)
Fourier transformX(!)
X(!) =
1
X
n=1
x(n)
j!n
1 n 1 (5)
X(k) =X(!j
!=2k=N) =
1
X
n=1
x(n)
j
2
N
nk
1 n 1 (6)
DFT coecients are expressed as:
xp(n) =
1
X
n=1
x(nlN) (7)
xp(n) is determined by aliasing x(n) over the interval 0nN1. The nite duration
sequence
^x(n) =
xp(n) 0nN1
0Otherwise
The relation between ^x(n)and x(n) exist when x(n) is of nite duration
x(n) = ^x(n) 0nN1
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 74 / 91
Relationship of the DFT to other TransformsRelationship of the DFT to other Transforms
Relationship to the Z Transform
Z transform of the sequence x(n) is
X(z) =
1
X
n=1
x(n)z
n
(8)
Sample X(z) at N equally spaced points on the unit circle. These points will be
Zk=e
j2k=N
k= 0;1; N1 (9)
X(z)jzk=e
j2k=N
=
1
X
n=1
x(n)e
j2kn=N
(10)
If x(n) is causal and has N number of samples then
X(z)jzk=e
j2k=N
=
1
X
n=0
x(n)e
j2kn=N
(11)
This is equivalent to DFT X(k)
X(k) =X(z)jzk=e
j2k=N
(12)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 75 / 91
Relationship to the Z Transform
Z transform of the sequence x(n) is
X(z) =
1
X
n=1
x(n)z
n
(8)
Sample X(z) at N equally spaced points on the unit circle. These points will be
Zk=e
j2k=N
k= 0;1; N1 (9)
X(z)jzk=e
j2k=N
=
1
X
n=1
x(n)e
j2kn=N
(10)
If x(n) is causal and has N number of samples then
X(z)jzk=e
j2k=N
=
1
X
n=0
x(n)e
j2kn=N
(11)
This is equivalent to DFT X(k)
X(k) =X(z)jzk=e
j2k=N
(12)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 75 / 91
Relationship of the DFT to other TransformsRelationship of the DFT to other Transforms
Parseval's Theorem
Consider a sequence x(n) and y(n)
x(n)
DFT
$X(k)
y(n)
DFT
$Y(k)
N1
X
n=0
x(n)y
(n) =
1
N
N1
X
k=0
X(k)Y
(k) (13)
When x(n)=y(n)
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
(14)
This equation give the energy of nite duration sequence it terms of its frequency
components
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 76 / 91
Parseval's Theorem
Consider a sequence x(n) and y(n)
x(n)
DFT
$X(k)
y(n)
DFT
$Y(k)
N1
X
n=0
x(n)y
(n) =
1
N
N1
X
k=0
X(k)Y
(k) (13)
When x(n)=y(n)
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
(14)
This equation give the energy of nite duration sequence it terms of its frequency
components
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 76 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
Determine the DFT of the sequence for N=8,h(n) =
1
2
2n2
0 otherwise
Plot the magnitude and phase response for N=8
Solution:
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
9
>
=
>
;
Consider a sequence x(n) and its DFT is
x(n)
DFT
$X(k)
xp(n)
DFT
$X(k)
wherexp(n) is the periodic sequence of x(n) in this example x(n) is of h(n) and is of
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
9
>
=
>
;
There are 5 samples in h(n) append 3 zeros to the right side of the sequence h(n)
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
;0;0;0
9
>
=
>
;
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 77 / 91
Determine the DFT of the sequence for N=8,h(n) =
1
2
2n2
0 otherwise
Plot the magnitude and phase response for N=8
Solution:
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
9
>
=
>
;
Consider a sequence x(n) and its DFT is
x(n)
DFT
$X(k)
xp(n)
DFT
$X(k)
wherexp(n) is the periodic sequence of x(n) in this example x(n) is of h(n) and is of
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
9
>
=
>
;
There are 5 samples in h(n) append 3 zeros to the right side of the sequence h(n)
h(n) =
8
>
<
>
:
1
2
;
1
2
;
1
2
"
;
1
2
;
1
2
;0;0;0
9
>
=
>
;
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 77 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
The DFT ofh(n) andhp(n) ish(n)
DFT
$H(k) hp(n)
DFT
$H(k)n-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
These are new
sequences x(n)
()
p
hn
-2 -1 0 1 2 3 4 5 n
()hn
1
2
Figure 40: Plot ofh(n) andhp(n)
The value of h(n) from the Figure is represented as
h(n) =
hp(n) 0nN1
0Otherwise
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 78 / 91
The DFT ofh(n) andhp(n) ish(n)
DFT
$H(k) hp(n)
DFT
$H(k)n-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
These are new
sequences x(n)
()
p
hn
-2 -1 0 1 2 3 4 5 n
()hn
1
2
Figure 40: Plot ofh(n) andhp(n)
The value of h(n) from the Figure is represented as
h(n) =
hp(n) 0nN1
0Otherwise
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 78 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
The new sequenceh(n) fromhp(n) is
h(n) =
8
>
<
>
:
1
2
"
;
1
2
;
1
2
;0;0;0;
1
2
;
1
2
9
>
=
>
;
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1W
1
8
W
2
8
W
3
8
W
4
8
W
5
8
W
6
8
W
7
8
1W
2
8
W
4
8
W
6
8
W
8
8
W
10
8
W
12
8
W
14
8
1W
3
8
W
6
8
W
9
8
W
12
8
W
15
8
W
18
8
W
21
8
1W
4
8
W
8
8
W
12
8
W
16
8
W
20
8
W
24
8
W
28
8
1W
5
8
W
10
8
W
15
8
W
20
8
W
25
8
W
30
8
W
35
8
1W
6
8
W
12
8
W
18
8
W
24
8
W
30
8
W
36
8
W
42
8
1W
7
8
W
14
8
W
21
8
W
28
8
W
35
8
W
42
8
W
49
8
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
x(0)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 79 / 91
The new sequenceh(n) fromhp(n) is
h(n) =
8
>
<
>
:
1
2
"
;
1
2
;
1
2
;0;0;0;
1
2
;
1
2
9
>
=
>
;
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1W
1
8
W
2
8
W
3
8
W
4
8
W
5
8
W
6
8
W
7
8
1W
2
8
W
4
8
W
6
8
W
8
8
W
10
8
W
12
8
W
14
8
1W
3
8
W
6
8
W
9
8
W
12
8
W
15
8
W
18
8
W
21
8
1W
4
8
W
8
8
W
12
8
W
16
8
W
20
8
W
24
8
W
28
8
1W
5
8
W
10
8
W
15
8
W
20
8
W
25
8
W
30
8
W
35
8
1W
6
8
W
12
8
W
18
8
W
24
8
W
30
8
W
36
8
W
42
8
1W
7
8
W
14
8
W
21
8
W
28
8
W
35
8
W
42
8
W
49
8
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
x(0)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 79 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
W
0
8
=W
8
8
=W
16
8
=W
24
8
=W
40
8
:::= 1
W
1
8
=W
9
8
=W
17
8
=W
25
8
=W
33
8
:::=
1
p
2
j
1
p
2
W
2
8
=W
10
8
=W
18
8
=W
26
8
=W
34
8
:::=j
W
3
8
=W
11
8
=W
19
8
=W
27
8
=W
35
8
:::=
1
p
2
j
1
p
2
W
4
8
=W
12
8
=W
20
8
=W
28
8
=W
36
8
:::=1
W
5
8
=W
13
8
=W
21
8
=W
29
8
=W
37
8
:::=
1
p
2
+j
1
p
2
W
6
8
=W
14
8
=W
22
8
=W
30
8
=W
38
8
:::=j
W
7
8
=W
15
8
=W
23
8
=W
31
8
=W
39
8
:::=
1
p
2
+j
1
p
2|H(k)|
Magnitude
0 1 2 3 4 5 6 7 k
0 .5 1 1.5 2 2.5
0 1 2 3 4 5 6 7 k
-180
180
-90
90
Phase of H(k)
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 1 1 1 1 1 1 1
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
3
7
7
7
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
4
1
2
1
2
1
2
0
0
0
1
2
1
2
3
7
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
2:5
1:207
0:5
0:207
0:5
0:207
0:5
1:207
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
2:5\0
1:207\0
0:5\180
0:207\180
0:5\0
0:207\180
0:5\180
1:207\0
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 80 / 91
W
0
8
=W
8
8
=W
16
8
=W
24
8
=W
40
8
:::= 1
W
1
8
=W
9
8
=W
17
8
=W
25
8
=W
33
8
:::=
1
p
2
j
1
p
2
W
2
8
=W
10
8
=W
18
8
=W
26
8
=W
34
8
:::=j
W
3
8
=W
11
8
=W
19
8
=W
27
8
=W
35
8
:::=
1
p
2
j
1
p
2
W
4
8
=W
12
8
=W
20
8
=W
28
8
=W
36
8
:::=1
W
5
8
=W
13
8
=W
21
8
=W
29
8
=W
37
8
:::=
1
p
2
+j
1
p
2
W
6
8
=W
14
8
=W
22
8
=W
30
8
=W
38
8
:::=j
W
7
8
=W
15
8
=W
23
8
=W
31
8
=W
39
8
:::=
1
p
2
+j
1
p
2|H(k)|
Magnitude
0 1 2 3 4 5 6 7 k
0 .5 1 1.5 2 2.5
0 1 2 3 4 5 6 7 k
-180
180
-90
90
Phase of H(k)
2
6
6
6
6
6
6
6
6
6
4
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
6
6
4
1 1 1 1 1 1 1 1
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1 1 1 1 1 1 1 1
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
1 j 1 j 1 j 1 j
1
1
p
2
+j
1
p
2
j
1
p
2
+j
1
p
2
1
1
p
2
j
1
p
2
j
1
p
2
j
1
p
2
3
7
7
7
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
6
4
1
2
1
2
1
2
0
0
0
1
2
1
2
3
7
7
7
7
7
7
7
7
7
7
5
2
6
6
6
6
6
6
6
6
6
4
2:5
1:207
0:5
0:207
0:5
0:207
0:5
1:207
3
7
7
7
7
7
7
7
7
7
5
=
2
6
6
6
6
6
6
6
6
6
4
2:5\0
1:207\0
0:5\180
0:207\180
0:5\0
0:207\180
0:5\180
1:207\0
3
7
7
7
7
7
7
7
7
7
5
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 80 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
The unit sample response of the rst order recursive lter is given ash(n) =a
n
u(n)
i) H(!)
ii)
iii) H(!) andH(k)
H(!) =
1
X
n=1
h(n)e
j!n
=
1
X
n=1
a
n
u(n)e
j!n
=
1
X
n=0
(ae
j!)
n
*u(n) = 0for n<0
N1
X
k=0
a
k
=
(
N for a = 1
1a
N
1a
for a6= 1
H(!) =
(ae
j!
)
0
(ae
j!
)
1+1
1ae
j!
=
1
1ae
j!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 81 / 91
The unit sample response of the rst order recursive lter is given ash(n) =a
n
u(n)
i) H(!)
ii)
iii) H(!) andH(k)
H(!) =
1
X
n=1
h(n)e
j!n
=
1
X
n=1
a
n
u(n)e
j!n
=
1
X
n=0
(ae
j!)
n
*u(n) = 0for n<0
N1
X
k=0
a
k
=
(
N for a = 1
1a
N
1a
for a6= 1
H(!) =
(ae
j!
)
0
(ae
j!
)
1+1
1ae
j!
=
1
1ae
j!
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 81 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
The DFT ofh(n) andhp(n) is
h(n)
DFT
$H(k) hp(n)
DFT
$H(k)
wherehp(n) is related as
hp(n) =
1
X
l=1
h(nlN)
Consider l=-p
hp(n) =
1
X
l=1
h(n+pN) hp(n) =
1
X
l=1
h(n+pN)
N point DFT H(k) in terms ofhp(n) is
H(k) =
N1
X
n=0
h(n)e
j
2
N
kn
H(k) =
N1
X
n=0
2
4
1
X
n=1
h(n+pN)
3
5e
j
2
N
kn
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 82 / 91
The DFT ofh(n) andhp(n) is
h(n)
DFT
$H(k) hp(n)
DFT
$H(k)
wherehp(n) is related as
hp(n) =
1
X
l=1
h(nlN)
Consider l=-p
hp(n) =
1
X
l=1
h(n+pN) hp(n) =
1
X
l=1
h(n+pN)
N point DFT H(k) in terms ofhp(n) is
H(k) =
N1
X
n=0
h(n)e
j
2
N
kn
H(k) =
N1
X
n=0
2
4
1
X
n=1
h(n+pN)
3
5e
j
2
N
kn
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 82 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
H(k) =
N1
X
n=0
2
4
1
X
n=1
a
(n+pN)
u(n+pN)
3
5e
j
2
N
kn
=
N1
X
n=0
"
1
X
n=0
a
(n+pN)
#
e
j
2
N
kn
*u(n) = 0for n<0
=
N1
X
n=0
"
1
X
n=0
a
n
a
pN
#
e
j
2
N
kn
Interchanging the summations
H(k) =
1
X
n=0
a
pN
N1
X
n=0
a
n
e
j
2
N
kn
N
X
k=0
a
k
=
1a
N
1a
1
X
p=0
a
pN
=
1
X
p=0
a
N
p
=
1(a
N
)
1+1
1a
N
=
1
1a
N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 83 / 91
H(k) =
N1
X
n=0
2
4
1
X
n=1
a
(n+pN)
u(n+pN)
3
5e
j
2
N
kn
=
N1
X
n=0
"
1
X
n=0
a
(n+pN)
#
e
j
2
N
kn
*u(n) = 0for n<0
=
N1
X
n=0
"
1
X
n=0
a
n
a
pN
#
e
j
2
N
kn
Interchanging the summations
H(k) =
1
X
n=0
a
pN
N1
X
n=0
a
n
e
j
2
N
kn
N
X
k=0
a
k
=
1a
N
1a
1
X
p=0
a
pN
=
1
X
p=0
a
N
p
=
1(a
N
)
1+1
1a
N
=
1
1a
N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 83 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
N1
X
n=0
a
n
e
j
2
N
kn
=
N1
X
n=0
(ae
j
2
N
k)
n
=
(ae
j2k=N
)
0
(ae
j2k=N
)
N
1(ae
j2k=N
)
N1
X
n=0
(ae
j
2
N
k)
n
=
1a
N
e
j2k
1(ae
j2k=N
)
=
1a
N
1(ae
j2k=N
)
*e
j2k
= 1
H(k) =
1
1a
N
1a
N
1(ae
j2k=N
)
=
1
1(ae
j2k=N
)
H(!) = =
1
1ae
j!
and H(k) =
1
1(ae
j2k=N
)
H(k) =H(!)j
!=2k=N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 84 / 91
N1
X
n=0
a
n
e
j
2
N
kn
=
N1
X
n=0
(ae
j
2
N
k)
n
=
(ae
j2k=N
)
0
(ae
j2k=N
)
N
1(ae
j2k=N
)
N1
X
n=0
(ae
j
2
N
k)
n
=
1a
N
e
j2k
1(ae
j2k=N
)
=
1a
N
1(ae
j2k=N
)
*e
j2k
= 1
H(k) =
1
1a
N
1a
N
1(ae
j2k=N
)
=
1
1(ae
j2k=N
)
H(!) = =
1
1ae
j!
and H(k) =
1
1(ae
j2k=N
)
H(k) =H(!)j
!=2k=N
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 84 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
Compute the DFT of the following nite length sequence of length Nx(n) =u(n)u(nN)u(n)
01234N-3N-2N-1NN+1N+2… n
Unit step sequence u(n)
u(n-N)
01234N-3N-2N-1NN+1N+2… n
Unit step sequence delayed by N samples
x(n)=u(n)-u(n-N)
01234N-3N-2N-1NN+1N+2… n
Subtraction of u(n-N) from u(n)
Figure 41: Generation ofx(n) =u(n)u(nN)
The value of x(n) as shown in Figure is represented as
x(n) =
1 0nN1
0Otherwise
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 85 / 91
Compute the DFT of the following nite length sequence of length Nx(n) =u(n)u(nN)u(n)
01234N-3N-2N-1NN+1N+2… n
Unit step sequence u(n)
u(n-N)
01234N-3N-2N-1NN+1N+2… n
Unit step sequence delayed by N samples
x(n)=u(n)-u(n-N)
01234N-3N-2N-1NN+1N+2… n
Subtraction of u(n-N) from u(n)
Figure 41: Generation ofx(n) =u(n)u(nN)
The value of x(n) as shown in Figure is represented as
x(n) =
1 0nN1
0Otherwise
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 85 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
DFT expression is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1
=
N1
X
n=0
1e
j2kn=N
=
N1
X
n=0
(e
j2k=N
)
n
(1)
"
N1
X
k=0
a
k
=
1a
N
1a
#
X(k) =
1e
j2k
e
j2k=N
=
11
e
j2k=N
= 0
When k=0 From the expression (1)
X(k) =
N1
X
n=0
(1)
n
=N
X(k) =
0when k6= 0
N when k= 0
X(k) =N(k)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 86 / 91
DFT expression is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
k= 0;1; : : :N1
=
N1
X
n=0
1e
j2kn=N
=
N1
X
n=0
(e
j2k=N
)
n
(1)
"
N1
X
k=0
a
k
=
1a
N
1a
#
X(k) =
1e
j2k
e
j2k=N
=
11
e
j2k=N
= 0
When k=0 From the expression (1)
X(k) =
N1
X
n=0
(1)
n
=N
X(k) =
0when k6= 0
N when k= 0
X(k) =N(k)
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 86 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
If x(n)=[1,2,0,3,-2, 4,7,5] evaluate the following
7P
k=0
X(k) iv)
7P
k=0
jX(k)j
2
X(0) is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
with k=0 and N=8
X(0) =
N1
X
n=0
x(n) = 1 + 2 + 0 + 32 + 4 + 7 + 5 = 20
X(4) is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
with k=4 and N=8
X(4) =
N1
X
n=0
x(n)e
j24n=8
=
N1
X
n=0
x(n)e
jn
=
N1
X
n=0
x(n)(1)
n
X(4) == 12 + 0324 + 75 =8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 87 / 91
If x(n)=[1,2,0,3,-2, 4,7,5] evaluate the following
7P
k=0
X(k) iv)
7P
k=0
jX(k)j
2
X(0) is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
with k=0 and N=8
X(0) =
N1
X
n=0
x(n) = 1 + 2 + 0 + 32 + 4 + 7 + 5 = 20
X(4) is
X(k) =
N1
X
n=0
x(n)e
j2kn=N
with k=4 and N=8
X(4) =
N1
X
n=0
x(n)e
j24n=8
=
N1
X
n=0
x(n)e
jn
=
N1
X
n=0
x(n)(1)
n
X(4) == 12 + 0324 + 75 =8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 87 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
iii)
7P
k=0
X(k)
We Know the IDFT expression as
x(n) =
1
N
N1
X
n=0
X(k)e
j2kn=N
With n=0 and N=8 it becomes
x(0) =
1
8
N1
X
n=0
X(k)
)
N1
X
n=0
X(k) = 8x(0) = 81 = 8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 88 / 91
iii)
7P
k=0
X(k)
We Know the IDFT expression as
x(n) =
1
N
N1
X
n=0
X(k)e
j2kn=N
With n=0 and N=8 it becomes
x(0) =
1
8
N1
X
n=0
X(k)
)
N1
X
n=0
X(k) = 8x(0) = 81 = 8
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 88 / 91
Problems and Solutions on DFTProblems and Solutions on DFT
The value of
7P
k=0
jX(k)j
2
is
The expression for Parseval's theorem is
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
7P
k=0
jX(k)j
2
is related as
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
N=8 Then
7
X
n=0
jx(n)j
2
=
1
8
7
X
k=0
jX(k)j
2
7
X
k=0
jX(k)j
2
= 8
7
X
n=0
jx(n)j
2
= 8[1 + 4 + 0 + 94 + 4 + 49 + 25] = 864
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 89 / 91
The value of
7P
k=0
jX(k)j
2
is
The expression for Parseval's theorem is
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
7P
k=0
jX(k)j
2
is related as
N1
X
n=0
jx(n)j
2
=
1
N
N1
X
k=0
jX(k)j
2
N=8 Then
7
X
n=0
jx(n)j
2
=
1
8
7
X
k=0
jX(k)j
2
7
X
k=0
jX(k)j
2
= 8
7
X
n=0
jx(n)j
2
= 8[1 + 4 + 0 + 94 + 4 + 49 + 25] = 864
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 89 / 91
Thank You
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 90 / 91
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 90 / 91
References
J. G. Proakis and D. G. Monalakis,Digital signal processing Principles Algorithms&
Applications, 4th ed. Pearson education, 2007.
Oppenheim and Schaer,Discrete Time Signal Processing. Pearson education, Prentice
Hall, 2003.
S. K. Mitra,Digital Signal Processing. Tata Mc-Graw Hill, 2004.
L. Tan,Digital Signal Processing. Elsivier publications, 2007.
J. S. Chitode,Digital signal processing. Technical Pulications.
B. Forouzan,Data Communication and Networking, 4th ed. McGraw-Hill, 2006.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 91 / 91
J. G. Proakis and D. G. Monalakis,Digital signal processing Principles Algorithms&
Applications, 4th ed. Pearson education, 2007.
Oppenheim and Schaer,Discrete Time Signal Processing. Pearson education, Prentice
Hall, 2003.
S. K. Mitra,Digital Signal Processing. Tata Mc-Graw Hill, 2004.
L. Tan,Digital Signal Processing. Elsivier publications, 2007.
J. S. Chitode,Digital signal processing. Technical Pulications.
B. Forouzan,Data Communication and Networking, 4th ed. McGraw-Hill, 2006.
Dr. Manjunatha. P (JNNCE) UNIT - 1: Discrete Fourier Transforms (DFT)[1, 2, 3, 4, 5] September 11, 2014 91 / 91
Tags
Categories
GeneralDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 10
- Slides 91
- Age 268 days
Related Slideshows
22
Pray For The Peace Of Jerusalem and You Will Prosper
RodolfoMoralesMarcuc
32 views
26
Don_t_Waste_Your_Life_God.....powerpoint
chalobrido8
33 views
31
VILLASUR_FACTORS_TO_CONSIDER_IN_PLATING_SALAD_10-13.pdf
JaiJai148317
31 views
14
Fertility awareness methods for women in the society
Isaiah47
30 views
35
Chapter 5 Arithmetic Functions Computer Organisation and Architecture
RitikSharma297999
27 views
5
syakira bhasa inggris (1) (1).pptx.......
ourcommunity56
30 views