EECE 301
Signals & Systems
Prof. Mark Fowler
Note Set #20
D-T Signals: Definition of DFT Numerical FT Analysis
1/13
Discrete Fourier Transform (DFT)
Weve seen that the DTFT is a good analytical tool for D-T signals (and systems
as well see later)
Namely X ()
jn
x
[
n
]
e
(DTFT) can be computed analytically
(at least in principle) when we have an equation model for x[n]
Q: Well why cant we use a computer to compute the DTFT from Data?
A: There are two reasons why we cant!!
1. The DTFT requires an infinite number of terms to be summed over n =
, -3, -2, -1, 0, 1, 2, 3,
2. The DTFT must be evaluated at an infinite number of points over the
interval (, ]
-The first one (infinite # of terms) isnt a problem if x[n] has finite duration
-The second one (infinitely many points) is always a problem!!
Well maybe we can just compute the DTFT at a finite set of points!!
2/13
Lets explore this possibility it will lead us to the Discrete Fourier Transform
Suppose we have a finite duration signal: x[n] = 0 for n < 0 and n N
Then the DTFT of this finite duration signal is:
X ()
x[n]e
jn
N 1
x[n]e jn
n 0
we can leave out
terms that are zero
If we could compute this at every value it might look like this:
X ()
-3
-2
-/2
/2
We are only interested in this range
Everywhere else it just repeats periodically
3/13
Now suppose we take the numerical data x[n] for n = 0, , N-1
and just compute this DTFT at a finite number of values (8 points here
but in practice wed do it MANY more points thousands of points!)
X ()
-3
-2
-/2
/2
Region of Interest
We leave this point out
because it is always the
same value as at = !!
4/13
Now, even though we are interested in the - to range,
we now play a trick to make the later equations easier
But, instead compute their
mirror images at values
between and 2
We dont compute points at
negative values
Dont need
same as = 0
X ()
-3
-2
-/2
/2
So say we want to compute the DTFT at M points, then choose
2
k k
, for k 0,1, 2, ..., M 1
M
Spacing between computed values
In otherwords:
0 0,
2
,
1
M
2
,
2 2
M
...
2
, M 1 ( M 1)
M
5/13
Thus mathematically what we have computed for our finite-duration signal is:
N 1
X ( k ) x[n ]e
jn k
n 0
N 1
x[n ]e
jnk 2M
for k 0, 1, 2, , M 1
n 0
There is just one last step to get the official definition of
the Discrete Fourier Transform (DFT):
We must set M = N
Done for a few mathematical reasons later well learn
a trick called zero-padding to get around this!
In other words: Compute as many frequency points as signal points
So
Given N signal data points x[n] for n = 0, , N-1
Compute N DFT points using:
N 1
X [k ] x[n ]e
n 0
j 2kn / N
Definition
k 0,1, 2, ..., N 1
of the DFT
k k
2
N
6/13
Plotting the DFT (well say more about this later..)
N = 8 case
We often plot the DFT vs. the DFT index k (integers)
Dont need
same as k = 0
X [k ]
X ()
But we know
that these points
can be tied back
to the true D-T
frequency :
0 1
2 3 4 5 6
7 8
-/2
/2
Spacing between computed values
2
2
N
8
4
7/13
1. So far weve defined the DFT
a. We based this on the motivation of wanting to compute the DTFT at
a finite number of points
b. Later well look more closely at the general relationship between
the DFT and the DTFT
2. For now we want to understand a few properties of the DFT
a. There a more properties if you take a DSP class youll learn them
there.
Properties of the DFT
1. Symmetry of the DFT
We arrived at the DFT via the DTFT so it should be no surprise that the DFT
inherits some sort of symmetry from the DTFT.
X [ N k ] X [k ], k 0,1, 2, ..., N 1
8/13
Illustration of DFT Symmetry
In this example
we dont see the
effect of the
conjugate because
we made the DFT
real-valued for
ease
X [ N k ] X [k ], k 0,1, 2, ..., N 1
N = 8 case
X ()
0 1
2 3 4 5 6
7 8
Because the upper DFT points are just like the negative index DFT points
this DFT symmetry property is exactly the same as the DTFT symmetry around the
origin:
X ()
0 1
2 3 4 5 6
7 8
9/13
2. Inverse DFT
Recall that the DTFT can be inverted given X() you can find the signal x[n]
Because we arrived at the DFT via the DTFT it should be no surprise that the
DFT inherits an inverse property from the DTFT.
Actually, we needed to force M = N to enable
the DFT inverse property to hold!!
So
Given N DFT points X[k] for k = 0, , N-1
Compute N signal data points using:
1
x[n ]
N
N 1
X [k ]e
j 2kn / N
n 0,1, 2, ..., N 1
n 0
Inverse DFT
(IDFT)
Compare to the DFT a remarkably similar structure:
N 1
X [k ] x[n ]e j 2kn / N
k 0,1, 2, ..., N 1
DFT
n 0
10/13
FFT Algorithm (We wont delve into HOW/WHY this works)
FFT = Fast Fourier Transform
The FFT is not a new thing to compute (the DFT is a thing we compute)
The FFT is just an efficient algorithm for computing the DFT
If you code the DFT algorithm in the obvious way it takes:
about N2 multiples, and N2 additions.
The FFT is a trick to compute the DFT more efficiently it takes:
N
2 log 2 ( N ) multiples
about
N log ( N ) additions
2
2
Similar ideas hold for computing the inverse DFT.
Note: The most common FFT algorithm requires that the number of samples
put into it be a power of two later well talk about how to zero-pad up
to a power of two!
11/13
The following plot shows the drastic improvement the FFT gives
over the DFT:
Note log scales
12/13
DFT Summary What We Know So Far!
Given N signal data points we can compute the DFT
And we can do this efficiently using the FFT algorithm
Given N DFT points we can get back the N signal data points
And we can do this efficiently using the IFFT algorithm
We know that there is a symmetry property
We know that we can move the upper DFT points down to
represent the negative frequencies
this will be essential in practical uses of the DFT
Remember we ended up with the upper DFT points only to make the
indexing by k easy!!!
It is just to make the DFT equation easy to write!!
Now
We need to explore the connections between the DFT and the DTFT
Then understand the relation between the CTFT, DTFT, & DFT
13/13
