Manuel S.
Enverga University Foundation
Lucena City, Philippines
Granted Autonomous Status
CHED CEB Res. 076-2009
Discrete Fourier
Transform
(As applied to Discrete-Time Signals)
Part III
Sherwin C. Lagrama.,RECE,MMEM
College Of Engineering and Technical Department
1st Sem 2011-2012
COLLEGE OF ENGINEERING AND TECHNICAL DEPARTMENT
Telefax No. (042) 710-3151; e-mail:engg.dept_mseuf@yahoo.com.ph
Objectives
1. To compare time-domain and frequency-
domain representation of signals
2. To represent signals as infinite sum of sine
and cosine waves
3. To investigates discrete Fourier transform
(DFT)
4. To understand DFT using problem solving
and calculation
The Fourier Transform
I. Introduction
A. Joseph Fourier
B. The Fourier series
C. Time domain vs. Frequency domain
II. Discrete Fourier Transform
III. Fast Fourier Transform
Introduction
JOSEPH FOURIER
Jean Baptiste Joseph
Fourier (21 March 1768 –
16 May 1830) was a French
mathematician and
physicist best known for
initiating the investigation of
Fourier series and their
applications to problems of
heat transfer and vibrations.
The Fourier transform and
Fourier's Law are also
named in his honour.
Fourier is also generally
credited with the discovery
of the greenhouse effect.
The Fourier Series
A periodic signal x(t) of period T can be
expressed as a Fourier series, that is, an
infinite sum of sine and cosine waves and
expressed as
The Fourier Series
• α(n) and β(n) = unknown amplitudes of the
cosine and sine terms
• n/T = nth harmonic of the fundamental
frequency f = 1/T
• Each of the sine and cosine functions in the
equations are called basis functions.
Time domain vs. Frequency Domain
Consider a signal x(t)=sin(t) for 0≤t≤2π
. Its time domain and frequency domain
plots, respectively, are
1 2
1.8
1.6
1.4
1.2
0 1
0.8
0.6
0.4
-1 0.2
0 1 2 3 4 5 6 7 0
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
5
x 10
Time domain vs. Frequency Domain
Most of the time, it is more convenient to represent signals in the
frequency domain, such in the case of the following example.
The TD plot barely carries 2.5
1.5
valuable information of 1
0.5
the signal. The FD plot -0.5
-1
however, explains that
-1.5
-2
-2.5
0 1 2 3 4 5 6 7
5
the signal is a sum of
x 10
sinusoids having integral
multiples of frequency. 0.8
0.7
0.6
0.5
0.4
x(t)=sin(t)+sin(2t) + sin(3t) 0.3
0.2
0.1
0
-4 -3 -2 -1 0 1 2 3 4
Fourier Transform
Consider an arbitrary signal nonperiodic
discrete time signal x[n]. The Fourier
transform of x[n] is given by
Fourier Transform
• The Fourier transform is a mathematical operation that decomposes a signal into its
constituent frequencies. Thus the Fourier transform of a musical chord is a
mathematical representation of the amplitudes of the individual notes that make it up.
The original signal depends on time, and therefore is called the time domain
representation of the signal, whereas the Fourier transform depends on frequency
and is called the frequency domain representation of the signal. The term Fourier
transform refers both to the frequency domain representation of the signal and the
process that transforms the signal to its frequency domain representation.
• In mathematical terms, the Fourier transform 'transforms' one complex-valued
function of a real variable into another. In effect, the Fourier transform decomposes a
function into oscillatory functions. The Fourier transform and its generalizations are
the subject of Fourier analysis. In this specific case, both the time and frequency
domains are unbounded linear continua. It is possible to define the Fourier transform
of a function of several variables, which is important for instance in the physical study
of wave motion and optics. It is also possible to generalize the Fourier transform on
discrete structures such as finite groups.
Discrete Fourier Transform
The DFT is the most useful computational tool in all
of signals and systems theory. It transforms an N-point
data sequence x[0],x[1],x[2],…,x[N-1] into an N-point
X[0],X[1],…,X[N-1].
The Discrete Fourier transform (DFT) of x[n] is given by:
Where
N = number of samples
Discrete Fourier Transform
Discrete Fourier Transform
• Development of
DFT
Discrete Fourier Transform
Discrete Fourier Transform
Discrete Fourier Transform
Discrete Fourier Transform
Example
a) Calculate the 4-point DFT X₁(k) of x₁(n) = {1, 1, 0, 0} for k = 0,1,2,3.
b) Calculate the 4-point DFT X₂(k) of x₂(n) = {1, 0, 0, 1} for k = 0,1,2,3.
c) Calculate the magnitudes of |X₁(k)| and |X₂(k)| for k = 0,1,2,3.
d) Are |X₁(k)| different from |X₂(k)|? Why?
Discrete Fourier Transform
a. When N = 4, k = 0, 1, 2, 3
3 2𝜋𝑘𝑛
−𝑗
X(k) = xn𝑒 4
𝑛=0
2𝜋𝑘 4𝜋𝑘 6𝜋𝑘
−𝑗 −𝑗 −𝑗
= x(0) + x(1)𝑒 4 + x(2)𝑒 4 + x(3)𝑒 4
This results in:
X(0) = 1 + 1 + 0 + 0 = 2
2𝜋
−𝑗
X(1) = 1 + 𝑒 4 =1–j
4𝜋
−𝑗
X(2) = 1 + 𝑒 4 =1–1=0
6𝜋
−𝑗
X(3) = 1 + 𝑒 4 =1+j
Discrete Fourier Transform
a. When N = 4, k = 0, 1, 2, 3
3 2𝜋𝑘𝑛
X(k) = x n 𝑒 −𝑗 4
𝑛=0
2𝜋𝑘 4𝜋𝑘 6𝜋𝑘
−𝑗 −𝑗 −𝑗
= x(0) + x(1)𝑒 4 + x(2)𝑒 4 + x(3)𝑒 4
This results in:
X(0) = 1 + 0 + 0 + 1 = 2
6𝜋
−𝑗
X(1) = 1 + 𝑒 4 =1+j
12𝜋
−𝑗
X(2) = 1 + 𝑒 4 =1–1=0
18𝜋
−𝑗
X(3) = 1 + 𝑒 4 =1–j
Discrete Fourier Transform
• Calculate the magnitudes of |X₁(k)| and |X₂(k)| for k = 0,1,2,3
|X₁(k)|: |X₂(k)|
X(0)=2 X(0)=2
X(1)=1-j=1.414 [-45°] X(1)=1+j=1.414 [45°]
X(2)=0 X(2)=0
X(3)=1+j=1.414 [45°] X(3)=1-j=1.414 [-45°]
Discrete Fourier Transform
• Are |X₁(k)| different from |X₂(k)|? Why?
¡ similar in real magnitude but different in
phase
In calculating trigonometric equations use radian mode
In converting rectangular form to polar form use degree mode
Thank you
Instructional materials by
Engr. SCLagrama.,RECE,MMEM
